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

Question

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.

Answer 1

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.

Answer 2

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