Illustrative examples of a phenomenon in the logic of mathematical induction

Question

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

Answer 1

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$

Answer 2

Example:

You can prove

$$ \frac{1}{2}\cdot\frac{3}{4}\cdot\ldots\cdot\frac{2n-1}{2n} < \sqrt{\frac{1}{3n}} $$

by strengthening to

$$ \frac{1}{2}\cdot\frac{3}{4}\cdot\ldots\cdot\frac{2n-1}{2n} < \sqrt{\frac{1}{3n+1}} $$

and using plain induction; this is the simplest example I know (you can make the inequality even shorter using the double factorial notation). In fact some time ago there was a post here about it, but I couldn't find it.

I hope this helps ;-)

Edit:

I've just seen even simpler example in this question, that is,

Prove that $0 \leq a_n < 1$ for all $n \in \mathbb{N}$ where $a_0 = 0$ and $ a_n = a_{n-1}^2 + \frac{1}{4} $ for $n > 0$.

which can be easily solved by proving $0 \leq a_n < \frac{1}{2}$ (in the original post @DanielFischer was first to give this hint).

Answer 3

I claim that one can prove by induction that $\sum_{n=1}^{\infty} \frac{1}{n^2}$ converges: or, if you want a statement which doesn't use anything from the theory of infinite series, that there is $A \in \mathbb{R}$ such that $\sum_{k=1}^n \frac{1}{k^2} \leq A$ for all $n \in \mathbb{Z}^+$.

Are you having trouble showing this by induction? I'll make it harder by asking you to prove that you can take $A = 2$.

Are you having at least as much trouble as before? I'll make it much harder.

Show that for all $n \in \mathbb{Z}^+$, $\sum_{k=1}^n \frac{1}{k^2} \leq 2- \frac{1}{n}$.

But in fact the last statement is very straightforward to prove by induction (see e.g. Proposition II.2.7 here for the details, but any reader who is moderately familiar with induction proofs will have no trouble supplying them herself).

The last inequality is one of my standard examples when teaching mathematical induction. I think it's a good example of the sort of phenomenon you're asking about. Unfortunately it is also a good example of the sort of "found theorem" that students are asked to prove using induction. In other words, suppose that we were actually trying to solve the first question by induction. How would we know or figure out to strengthen the inequality in this particular way? (Even more standard examples of "found theorems" are the ubiquitous power sum identities, e.g. $\sum_{k=1}^n k^3 = \left( \frac{n(n+1)}{2}\right)^2$.)

Answer 4

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>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.

Answer 5

Suppose that $P(n)$ and $Q(n)$ are two predicates indexed by the positive integers, and one wants to prove that both hold for all positive integers. A natural first try is to prove

$P(1)$ and $\forall n \in \mathbb{Z}^+, P(n) \implies P(n+1)$

and then prove

Q(1) and $\forall n \in \mathbb{Z}^+, Q(n) \implies Q(n+1)$.

But when $P(n)$ and $Q(n)$ are sufficiently closely related, it often turns out to be easier to prove

$P(1)$ and $Q(1)$ and $\forall n \in \mathbb{Z}^+$, ($P(n)$ and $Q(n)$) $\implies$ ($P(n+1)$ and $Q(n+1)$).

I would say that this happens to me during a positive proportion of all the induction proofs I see / write. It seems easy to give complicated examples, so we should look for simple ones. One such occurs in Lemma 3 of this note written for beginning undergraduate algebra students.

Answer 6

I have always thought about this issue using the following logic example (the induction is over the length of the propositional formula):

• Every propositional formula built using just $\neg, \land, \lor$ is equivalent to a formula (only using $\neg, \land, \lor$) where $\neg$ only affects propositional variables.

A direct proof of the previous statement using induction does not seem to work. On the other hand, a proof (using induction) of the following stronger claim is almost trivial:

• For every propositional formula $\varphi$ built using just $\neg, \land, \lor$ , it holds that: 1) $\varphi$ is equivalent to a formula (only using $\neg, \land, \lor$) where $\neg$ only affects propositional variables, and 2) $\neg \varphi$ is equivalent to a formula (only using $\neg, \land, \lor$) where $\neg$ only affects propositional variables.

Answer 7

Isn't "strong induction" an example of this? Instead of proving $(\forall n) P(n)$ one proves $(\forall n)(\forall m \leq n) P(m)$ which gives additional strength in the inductive hypothesis.

Answer 8

Here is another example.

Suppose $s_1=1$ and for $n=1,2,3,\ldots,$ $s_{n+1} = \sqrt{2s_n+2}.$

Show that for all $n,$ $s_n<s_{n+1}.$

The difficulty is that it is not the case that for all real $s\ge 1,$ $s<\sqrt{2s+2}.$ Nonetheless the proposition to be proved is true.

Instead, one may prove that if $1\le s<1+\sqrt 3$ then $1\le s < \sqrt{2s+2} < 1+\sqrt3,$ and use that in a proof by induction.

The fact that $s_n<1+\sqrt3$ becomes a part of the induction hypothesis and can then be used in the proof.