# Induction hypothesis when proving solution to linear homogeneous recurrence equation

I am looking at an example solution to a linear homogeneous recurrence equation of:

$T(0) = 0$

$T(1) = 2$

$T(n) = 4T(n-1) - 3T(n-2), n > 1$

And solving it you get $T(n) = 3^n - 1$

In the example, the induction proof has the base cases which are both correct:

$3^0 - 1 = 0$

$3^1 - 1 = 2$

For the induction hypothesis, it's now stated:

Assume for all n, $(1 <= n <= k)$, that $T(n) = 3^n - 1$

And the proof shows $T(k+1) = 3^{(k+1)} - 1$

My question is, wouldn't it make more sense to state:

Assume for all n, $(2 <= n <= k)$, that $T(n) = 3^n - 1$

The base cases have already been proven, so it seems redundant to state for all $1\leq n \leq k$, since we already showed it was true for $n = 1$.

Is there something I'm missing as to why the inductive hypothesis would include the last base case and not just assume true for the next case, or is this just a bad example?

Thanks.

• It doesn't make a difference. You need to show it for two values (in your case n=0 and $n=1$), and you need to show that $T(n+1) = 3^{n+1} - 1$, and this last equation I couldn't find in your question. Commented Apr 9, 2013 at 18:00
• Ah, it has just been edited to include the equation in my last comment. Thanks Ross B.! Commented Apr 9, 2013 at 18:00

Let us suppose that, as you report, the two base cases used are $n=0$ and $n=1$. Then the induction step in a proof structured along the given lines should really go like this:

"Assume that for all $n$, where $0\le n\le k$, we have $T(n)=3^n-1$. We show that $T(k+1)=3^{k+1}-1$." Call this the corrected induction hypothesis.

For suppose we have only proved that the case $k+1$ follows from the cases $1$ to $k$. Then we have not proved that $T(n)=3^n-1$ for $n=2$. So the induction hypothesis used in the quoted proof is not quite right. But it is not right in a direction opposite to your suggestion: instead of being too inclusive, it is not quite inclusive enough. (By the way, although the induction hypothesis quoted is not quite right for dealing with $n=2$, it is fine for all other $n$.)

We could replace the corrected induction hypothesis by an induction hypothesis that says the result holds at $k$ and $k-1$.

Think of the logic of the induction idea. We have proved the cases $0$ and $1$. So because everything is OK at $k=1$ and below, the result holds at $2$, and therefore everything is OK at $2$ and below.

But because everything is OK at $2$ and below, the result holds at $3$, and therefore everything is OK at $3$ and below.

But because everything is OK at $3$ and below, $\dots$.

The fact that you pointed out, that the result holds at $1$, doesn't mean that we don't need it in the induction hypothesis. In fact, we do need it, and do use it, both in proving the result at $2$ and the result at $3$.

• Thank you. This was an excellent explanation. Commented Apr 9, 2013 at 19:59
• You are welcome. It takes a fair while to really understand what's happening with induction. Even a half-dozen "perfect" answers to induction problems are not enough. Then, after a while, one realizes how simple it all is, one feels the process in the bones. Commented Apr 9, 2013 at 20:11