# 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$?
-
In proving some of the basic properties of the convergents of simple continued fractions, it is handy to have an extra parameter $t$ to make the induction go through. And in a recent post I used an extra parameter for an induction proof of the fact that the denominator of $\frac{1}{\sqrt{a_1}+\cdots+\sqrt{a_n}}$ can be rationalized. – André Nicolas Jul 21 '13 at 19:18
I don't follow that so far, but if you make it into an answer and expand on it a bit, maybe I will. – Michael Hardy Jul 21 '13 at 19:28
This is nearly identical to the binomial coefficients question, though the statement is even weaker. – cats Jul 21 '13 at 20:14
Re: the logician's viewpoint: it sounds a bit wishful. For starters you would have to formalize what it means for one provable-by-induction statement to be "weaker" than another. Intuitively -- sure, I know exactly what you mean -- but formally? That already sounds hard. – Pete L. Clark Jul 22 '13 at 2:10

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$

-
@MichaelHardy: Thank you for the edit, \langle, \rangle are the right delimiters. – André Nicolas Jul 21 '13 at 23:46

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

-
Did you learn this from the lovely "Art and Craft of Problem Solving", by Zeitz? Having read the same in that book, I came into this thread to give this very example! – Chris Jul 22 '13 at 17:18
@user1296727 I have no idea where it comes from, I saw it in one of the questions here, at Math.SE. I remembered it as I liked it very much. Maybe it does come from your book, but it also might be a math folklore. I don't know. – dtldarek Jul 22 '13 at 17:31

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

-
I see now that this example is already alluded to in Andre Nicholas's answer. Nevertheless, I think it deserves an answer of its own. – Pete L. Clark Jul 21 '13 at 21:14
It's alluded to in my original question too. (But I've up-voted it.) – Michael Hardy Jul 21 '13 at 23:41
@Michael: thanks, I not followed the link in your question previously. I do think though that this is a strong answer: the extra "$\frac{-1}{n}$" gives you something to grab onto inductively, whereas -- as Andre points out -- trying to inductively show that $a_1 + \ldots + a_n \leq A \implies a_1 + \ldots + a_n + a_{n+1} \leq A$ is patently doomed. – Pete L. Clark Jul 22 '13 at 1:55
The power sum identity that you quote is not a 'found theorem'. It can be obtained by repeated application of Gauss's summation formula. – Mike Jones Oct 29 '15 at 18:08
@Mike Jones: By a "found theorem" I mean that it is a statement that students are given in undergraduate courses and asked to prove using induction. My point is that their task is being "made easier" by not asking them to come up with the statement of the result...a phenomenon which I regard as having negative pedagogical effects. I am certainly aware that closed form evaluation of power sums is a very old result, going back to Johann Faulhaber: en.wikipedia.org/wiki/Faulhaber's_formula. – Pete L. Clark Oct 29 '15 at 20:42

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

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.

-
When I first saw this question that was my immediate reaction. But when I thought more about it, it sort of slid away from me. In strong induction -- as traditionally construed -- we're loading more into the hypothesis and keeping the conclusion the same. So really we're weakening the implication that we have to prove (and this is more obviously helpful than strengthening it...). – Pete L. Clark Jul 23 '13 at 1:12
@Pete L. Clark: yes, that is true in the "textbook" version of strong induction, which I have little sympathy for. If we only assume the regular principle of induction (which is all that we have in PA, anyway), we still have "strong induction" if we prove $(\forall n)\phi(n)$ by instead proving the stronger formula $(\forall n)(\forall m \leq n)\phi(m)$, where the latter is proved by "ordinary" induction. That is the perspective I intended in the answer. – Carl Mummert Jul 23 '13 at 1:15
OK, then in that sense I agree. Still, because the "textbook" version of strong induction is different, the example may not be the best one, pedagogically speaking...(Or maybe it is. Anyway, I upvoted it.) – Pete L. Clark Jul 23 '13 at 1:17

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 undegraduate algebra students.

-

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.

-
What does the capital C mean? – Michael Hardy Jul 22 '13 at 2:42
This is the old Polish style of writing logic that for obvious reasons is not considered today. In this setting $C$ refers to the material implication. To illustrate it with some examples, 1) $Cpq$ is what we nowadays write as $p \to q$, 2) $CpCqp$ is what we write as $p \to (q \to p)$, 3) $CsCrCpCqp$ is what we write as $s \to ( r \to (p \to (q \to p)))$, etc – boumol Jul 22 '13 at 8:44
@boumol: many users of this site, myself included, have conducted similar dialogues with Mr. Spoonwood in the past. In brief summary: yes, he really does seem to hold ideas about notation which, at first glance, are sufficiently eccentric that you would think he could not be serious. I have regretted some of the time I spent engaging him on this. I think you should be happy that you can parse what he writes (up to parentheses!): he doesn't seem to understand that most people are not willing to learn a now little-used notation just to understand him. – Pete L. Clark Jul 22 '13 at 19:09
"But, I have no need to communicate with most people who study mathematics or logic at present." Well, that's a striking statement to hear from someone who has left 227 answers and 37 questions on this math Q&A site. It is certainly not the default assumption. Maybe you should consider putting that on your userpage. Seriously -- it would avoid a lot of people wasting their time. – Pete L. Clark Jul 23 '13 at 0:43
@Doug: I simply don't believe that the original intent of your comment is the same as your later, obnoxiously literal explication of it. In other words, I have lost my default assumption that you are even attempting to communicate in a sincere, good faith manner. Because of this I have no desire to communicate further with you. Please do not direct any future comments to me. – Pete L. Clark Jul 24 '13 at 2:00