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