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/ (Wayback Machine)
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?
Solution 1:
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$.
Solution 2:
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:
- $P(1)$ is true;
- $P(n)$ implies $P(2n)$;
- $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 even, 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 odd, 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.
Useful links:
- Cauchy induction at AoPS
- Proof of AM-GM using this type of induction at Wikipedia (current revision). They call this technique forward-backward-induction.
- One section of Pete L. Clark's notes on induction (Wayback Machine) is devoted to this type of induction. He calls it upward-downward induction.
AM-GM inequality is indeed the most frequent application used to illustrate the Cauchy induction. You can find some proofs using Cauchy induction and some useful links e.g. in these answers:
- AM-GM inequality
- AM-GM inequality
- midpoint convexity and rational convexity
Solution 3:
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.$