Illustrative examples of a phenomenon in the logic of mathematical induction It is said (and I myself have said) that in some cases the easiest way to prove a statement by mathematical induction is to prove a stronger statement by mathematical induction, because then one has a stronger induction hypothesis to use.

But then I ask myself: if a bright student were to ask me for some typical examples of that phenomenon, what would I say?

The only example that came to mind immediately when I thought of this question is Łos's theorem: A first-order sentence $\varphi$ is true in an ultraproduct $\left(\prod_{i\in I} A_i\right)/F$, where $F$ is an ultrafilter on the index set $I$, if and only if the set $\{i\in I : \varphi\text{ is true in}A_i\}$ is a member of $F$.  The stronger statement speaks of first-order formulas (which may contain free variables) rather than of first-order sentences (which have no free variables).  The proof is by induction on the formation of first order formulas, and it works since the class of first-order formulas is closed under certain operations and the class of first-order sentences is not.

That's not a great example for the situation I imagined.

Looking around m.s.e. a bit, I find Steven Stadnicki's answer to this question and my answer to this question, and maybe Martin Brandenburg's answer to this question.

This is not a great list of examples for illustrative purposes at an elementary level (although Steven Stadnick's answer would fit into such a list).


If the purpose is to illustrate this phenomenon, which examples should be used, both at the most elementary levels and at more advanced levels?
Is there a logician's viewpoint on this phenomenon?  Might there be, for example, some idempotent mapping $T$ from the class of statements-that-are-weaker-versions-of-things-provable-by-induction to the class of things-provable-by-induction, where $T\varphi$ is in each case a generalization of $\varphi$?
Consider the simple continued fraction $\langle a_0;a_1,a_2,\dots\rangle$, where all the $a_i$ are integers, and all positive except possibly $a_0$.

Define the sequences $p_i$, $q_i$ by 

$p_{-1}=0$, $p_0=a_0$, and $p_k=a_kp_{k-1}+p_{k-2}$, and

$q_{-1}=0$, $q_0=1$, and $q_k=a_kq_{k-1}+q_{k-2}$.

We want to show that $\langle a_0;a_1,\dots,a_k\rangle=\frac{p_k}{q_k}$.

The standard way to prove the result by induction is to prove the stronger result that for any positive $x$,
$$\langle a_0;a_1,\dots,a_{k-1},x\rangle=\frac{xp_{k-1}+p_{k-2}}{xq_{k-1}+q_{k-2}}.$$

As a small additional example, a recent question asked for a proof that the denominator of 
$\frac{1}{\sqrt{a_1}+\sqrt{a_2}+\cdots+\sqrt{a_n}}$ can be rationalized. An induction proof used the stronger induction hypothesis that $\frac{1}{\sqrt{a_1}+\sqrt{a_2}+\cdots+\sqrt{a_n}+t}$ can be rationalized, where $t$ is a free parameter.

For early induction arguments, however, I think inequalities are quite persuasive, since it is clear that for example knowing that $1+\frac{1}{2^2}+\frac{1}{n^2}\lt 2$ cannot by itself imply that $1+\frac{1}{2^2}+\frac{1}{n^2}+\frac{1}{(n+1)^2}\lt 2$
Formation rules:

1) Each lower case letter of the Latin alphabet qualifies as a formula.

2) If $\alpha$ as well as $\beta$ qualify as a formula, so does C$\alpha$$\beta$.

3) Nothing else will get consider as a formula for the following.

Since I'll only talk about something in two-valued logic here, C will stand for material implication.  That said, what gets stated applies to more than just two-valued logic.

Suppose we wanted to prove that in classical propositional logic with substitution and detachment, (1) if $\vdash CsCrCpCqp$, then $\vdash C\alpha_n C\alpha_{(n-1)} \dots C\alpha_2C\alpha_1\alpha_2$, where $n&gt;1$, lower case letters are atomic formulas, and subscripted $\alpha$'s indicate any formulas.  We could do this, but it comes as easier to prove the stronger meta-statement that (2) if $\vdash CpCqp$, then $\vdash C\alpha_n C\alpha_{(n-1)} \dots C\alpha_2 C\alpha_1\alpha_2$ first, and it then quickly follows that if $\vdash CsCrCpCqp$, then $\vdash C\alpha_n C\alpha_{(n-1)} \dots C\alpha_2 C\alpha_1 \alpha_2$.  Or at least proving if $\vdash CsCrCpCqp$, then $\vdash C\alpha_n C\alpha_{(n-1)} \dots C\alpha_2 C\alpha_1\alpha_2$ takes longer to do than the other case.

Also, I do think that logicians would regard $\vdash$CpCqp as a stronger statement than $\vdash CsCrCpCqp$ (which implies 2) stronger than 1)), since CpCqp qualifies as an organic theorem in that it has no proper subformulas which qualify as tautologies.  On the other hand, $CsCrCpCqp$ qualifies as non-organic since it has a proper subformula which qualifies as a tautology.