# Difference between two methods of induction for proving the correctness of recurrence equation solution

Suppose you have the recurrence equation

$T(0) = 0$

$T(n) = 2T(n-1) + 1, n > 0$

The closed form of this equation appears to be $T(n) = 2^n - 1$

To prove this is correct using induction, we have a base case:

$2^0 - 1 = 0$, so this is correct

Now I've seen two different approaches to the inductive step and am wondering what exactly is the difference between them. One is to have an induction hypothesis where it's assumed that

$T(n) = 2^n - 1$ for all $n < M$ and we want to show that $T(M) = 2^M - 1$

Therefore we have

$T(M) = 2T(M-1) + 1$, and $M-1$ is $< M$ so we can substitute in the induction hypothesis

$T(M) = 2[2^(M-1) - 1] + 1$

$T(M) = 2^M - 2 + 1$

$T(M) = 2^M -1$

The second form I've seen of the inductive step is to assume that $T(n) = 2^n - 1$ and to show that $T(n+1) = 2^(n+1) - 1$

$T(n+1) = 2T(n) + 1$, then substitute in the inductive hypothesis for $T(n)$

$T(n+1) = 2(2^n - 1) + 1$

$T(n+1) = 2^(n+1) - 2 + 1$

$T(n+1) = 2^(n+1) - 1$

My question is there any significant difference between these two inductive steps? Is there a reason to use one over the other? Thank you.

• Welcome to MSE! It really helps readability if you format your questions using MathJax. Regards Commented Mar 20, 2013 at 17:28
• One is sometimes called strong induction, as opposed to the "ordinary" $n$ to $n+1$ induction. However, any strong induction proof can be mechanically turned into an ordinary induction proof. Strong induction, or more generally structural induction, often feels more natural. Commented Mar 20, 2013 at 17:35

The first form of induction that you described is sometimes called strong induction, or complete induction, or course of values induction. You may be interested in the following Wikipedia article, which is OK but not outstanding.

The term "strong induction" is a bit of a misnomer. One can prove precisely the same results by ordinary induction as by strong induction, no more, no less.

As an illustration, we sketch a proof by (i) strong induction, and (ii) ordinary induction that every integer $\ge 2$ can be expressed as a finite product of primes. Note that we are proving only existence, not the more difficult uniqueness.

Proof by Strong Induction: Let $A(n)$ be the assertion that $n$ is a prime or can be expressed as a product of primes. Certainly $A(2)$ is true. Suppose that $A(k)$ is true for all $k\lt n$. We show that $A(n)$ is true.

If $n$ is prime, then $A(n)$ is true. If $n$ is not prime, then there exist integers $a$ and $b$, with $2\le a\lt n$ and $2\le b\lt n$, such that $n=ab$. By the induction hypothesis, each of $a$ and $b$ is a product of a finite number of primes, and therefore so is $ab$.

Proof by Weak Induction: Let $B(n)$ be the assertion that every integer $k$ in the interval $2\le k\le n-1$ is a product of primes. We show by weak induction that $B(n)$ is true for all integers $n\ge 2$.

Certainly $B(2)$ is true. Suppose that for some given $n$, we know that $B(n)$ is true. we want to show that $B(n+1)$ is true. So we know that every integer $k$, with $2\le k\lt n$ is a prime or product of primes, and we want to show that the same is true for $2\le k\lt n+1$. So all we need to do is to show that $n$ is prime or a product of primes. If $n$ is prime we are finished. Otherwise, assume $n=ab$, where $a,b \ge 2$. We have $a, b\lt n$. But by the induction hypothesis $B(n)$, that means $a$ and $b$ are each prime or a product of primes, and we are finished.

The translation from the first proof to the second involved only a mechanical change in the statement of the result, and hence in the induction hypothesis/ The same kind of translation process always works.

Remark: Strong induction, and its deservedly popular cousin structural induction, are often more natural tools than ordinary induction.

Note for example that the first proof above reads more smoothly than the second proof.

One can always rewrite things in terms of ordinary induction, but the rewriting can be awkward, doing violence to the natural structure of the problem.

The difference between the two is that the first one is much stronger than the 2nd one. In some cases the first approach is only applicable.The first approach is known as the strong form of Induction and the 2nd one is known as the weak form. The problems that can be solved using the 2nd one can also be solved using the first one but not vice versa.

If you give it a little thought you can easily understand that the 2nd form is a subform of the first one(essentially the case when the proposition is true for n we prove it for n+1 , but in the first case we consider it to be true for all m< n+1 and prove it true for n+1). In this problem both these approaches result in the same thing but in some other problem it might not).

• Great answer! Thanks so much. Commented Mar 20, 2013 at 17:34
• It is not true. Every assertion that can be proved by strong induction can be proved by weak induction. Commented Mar 20, 2013 at 17:37
• @AndréNicolas why isnt it not true. Can you briefly explain (please)??? Commented Mar 20, 2013 at 17:38
• Briefly, suppose you have a proof by strong induction of the assertion "for all $n$, $A(n)$." Then by changing the induction hypothesis to $B(n)$, where $B(n)$ is the assertion that $A(k)$ holds for all $k\le n$, you can rewrite the strong induction proof as a weak induction proof of "for all $n$, \$B(n)." Commented Mar 20, 2013 at 17:42