How does backwards induction work to prove a property for all naturals?
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:
- $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
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.$