# How does backwards induction work to prove a property for all naturals?

I was reading a blogpost here: http://mzargar.wordpress.com/2009/07/19/cauchys-method-of-induction/

One thing that threw me off was that after the first four large displayed equations, there is the statement "it is sufficient to prove that if the theorem holds for $n=m+1$, then it holds for $n=m$."

How is this type of induction valid? I browsed around for things like backward induction, reverse induction, and Cauchy induction, but couldn't find a justification for how this is valid.

With the usual forward induction of verifying a base case and proving $P(n)\implies P(n+1)$, it's easy to intuitively understand how induction will show a property holds for all natural numbers (or at least starting at the base case). But with this reverse induction, it seems to me that if you prove $P(m+1)\implies P(m)$, then if you were able to verify a specific case like $P(15)$, then you would only know it's true for numbers up to $15$. How does it actually prove the property for all naturals?

-
This induction principle is applied to finite sets, not the infinite set of natural numbers. –  Michael Greinecker Jan 8 '12 at 11:15
I never thought it was applied to infinite sets, but isn't induction used to prove certain properties hold for all naturals? As in $2^n>n$ for all $n$? I'm just asking how you could draw the same conclusion from a different induction scheme. –  Nawlins Jan 8 '12 at 11:28
You left out the first part of the sentence! "Now that we have the case when n is a power of 2 settled, it is sufficient to prove...." The short answer is that you also prove that for any n, you can find N >= n for which it is true, usually by proving it true for some infinite set. –  Old Pro May 19 '12 at 8:04

As the OP rightly points out, $P(m+1) \Rightarrow P(m)$ alone does not imply that the property holds for all natural numbers. The proposed method needs two conditions:

• The property holds for infinitely many natural numbers; i.e., it holds for an infinite subsequence $n_1 < n_2 < \cdots < n_k < \cdots$. This is like the “base step” of the proof.

• $P(m+1)$ implies $P(m)$. This is the “induction step”.

A textbook example of this method is Cauchy’s proof of the AM-GM inequality. Martin’s answer links to a proof of “midpoint convexity implies convexity” using a similar idea.

Proof of correctness. The intuition behind this is that the base step identifies infinitely many numbers for which the property holds. But these numbers might contain gaps; we then work to fill these gaps in the induction step.

Let us make that a formal proof. Assume that the property $P$ fails to hold for at least one value of $n$, say $N$. Then rewriting the second hypothesis contrapositively as $\lnot P(m) \Rightarrow \lnot P(m+1)$ and applying standard mathematical induction to the hypothesis $\lnot P$, we conclude that $\lnot P(n)$ holds for all $n \geqslant N$; in other words, the property $P$ fails to hold eventually. But this contradicts the first assumption. $\quad\diamond$

I end with a methodological remark. Notice that what I dubbed the base step in fact requires us to prove the proposition $Q(k) := P(n_k)$ for infinitely many $k$. This is reminiscent of standard induction, and unsurprisingly we often resort to it in this step. For instance, in the AM-GM proof, it is easy to prove that the AM-GM inequality holds for $2K$ numbers assuming it always holds for $K$ numbers; setting $K = 2^k$ gives a standard induction proof that $Q(k) := P(2^k)$ is true for all $k$.

-

Cauchy induction consists of the following parts.

We want to show that $P(n)$ holds for any $n=1,2,3,\ldots$. To do this we show:

1. $P(1)$ is true;
2. $P(n)$ implies $P(2n)$;
3. $P(m+1)$ implies $P(m)$.

If all of the above conditions are true, then $P(n)$ holds for all integers.

Intuition behind this: By steps of the type $n\to 2n$ and $m+1\to m$ we can get from $1$ to any integer. E.g. if we want to get to the number $5$ we can do it like this:
$1\to2\to4\to8\to7\to6\to5$.
A different possibility:
$1\to2\to4\to3\to6\to5$.

Formal proof: Suppose that the above conditions are true. We will show by strong induction that $P(n)$ is true for each $n$.

$1^\circ$ For $n=1$ we have validity of $P(1)$.

$2^\circ$ Suppose that $n\ge 2$ and $P(k)$ is true for each $k$ such that $1\le k<n$.

If $n$ is odd, we can use 2: Since $k=n/2<n$, we know that $P(k)$ is true, and thus $P(2k)=P(n)$ is true.

If $n$ is even, we can use 3: Since $k=(n+1)/2<n$, we know that $P(k)$ is true. This implies that $P(2k)=P(n+1)$ is true. Now using 3 we get that $P(n)$ is true as well.

• Cauchy induction at AoPS
• Proof of AM-GM using this type of induction at Wikipedia. They call this technique forward-backward-induction.
• One section of Pete L. Clark's notes on induction is devoted to this type of induction. He calls it upward-downward induction.

AM-GM inequality is indeed the most frequent application of Cauchy induction. You can find some proofs using Cauchy induction and some useful links e.g. in these answers:

-
This is a nice way to look at this idea: if we write $P(a) \Rightarrow P(b)$ as a directed edge from $a$ to $b$, then as long as there is a finite-length path from $1$ to $n$, we can conclude that $P(n)$ is true (assuming, of course, that we already proved $P(1)$). –  Srivatsan Jan 8 '12 at 11:46
Well I tried to include something about intuition, too. Anyway, now that I've had a better look at your answer, I think I should have written about more general version. (I.e. $n_k$ instead of $2^k$, as in your answer.) –  Martin Sleziak Jan 8 '12 at 11:52

Hint $\$ This can be viewed as a sort of interval (or segment) induction.

Lemma $\rm\ S\subset \mathbb N\:$ satisfies $\rm\:n+1\in S\:\!\Rightarrow n \in S\:$ iff $\rm\:S\:$ is an initial segment of $\:\mathbb N$

Proof  (hint)  If $\rm\:S\ne \mathbb N\:$ then $\rm\:S = [0,m)\:$ for the least $\rm\:m\not\in S,\:$ since by induction, nonmembership ascends from $\rm\:m\:$ by $\rm\:n\not\in S\:\Rightarrow\:n+1\not\in S.\:$

Corollary  If, additionally, $\rm\:S\:$ is unbounded then $\rm\:S = \mathbb N$

In your case $\rm\: S\ne \{\ \}\:$ is unbounded via the hypothesis $\rm\:n\in S\:\Rightarrow\:2\:\!n\in S.$

-

You seem to be confused with the method of infinite descent which is used to prove that something is FALSE : If $P(0)$ is false and if $P(n)$ implies that there exists a $m < n$ such that $P(m)$, then $P(n)$ is false for all $n$. This correspond to prove the anteposition of the standard recurrence principle. (The anteposition of an implication $A\Rightarrow B$ is $\text{not} B \Rightarrow \text{not} A$.)

-
But that's not the situation in the blogpost. The claim is that $P(m+1)\implies P(m)$ is sufficient to show an inequality holds for all $n$. There is no question of proving something false. –  Nawlins Jan 8 '12 at 11:24