Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
This induction principle is applied to finite sets, not the infinite set of natural numbers. –  Michael Greinecker Jan 8 '12 at 11:15
1  
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
3  
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

4 Answers 4

up vote 11 down vote accepted

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

share|improve this answer

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.


Useful links:

  • 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:

share|improve this answer
    
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.$

share|improve this answer

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.