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$?
Best Answer
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$