Proof By Strong Induction
Mar 11th, 2013This is an example of a proof by induction. I believe that by reading other people mistakes, we are more able to tell if we have really understand a concept.
This problem was given in the midterm exam of the first class of Discrete Math in a Computer Science degree (CSE 20 at UCSD), that I TAed in Winter 2013. The common mistakes are what I saw in the 280+ papers I graded.
Define the sequence $a_n$ as:
- $a_1 = 2$
- $a_2 = 4$
- $\forall n \geq 3,\ a_{n} = a_{n-1} + 2a_{n-2}$
Prove: $\forall n \geq 1,\ a_n \geq 2^n$
Base case
We have to check two base cases:
- $a_1 = 2 \geq 2^1$, ok
- $a_2= 4 \geq 2^2$, ok
Common mistake: use only one base case instead of two. We need two base cases because in the inductive step, we use the two previous levels to prove the next one.
Inductive step
Assume for $n \geq 3$ fixed but random: $a_{n-1} \geq 2^{n-1}$ and $a_{n-2} \geq 2^{n-2}$.
Common mistake: use weak induction (by just writing “Assume for $n \geq 3$ fixed but random $a_{n-1} \geq 2^{n-1}$.”) instead of strong induction. We need strong induction because in the inductive step, we not only use the fact that $a_{n-1} \geq 2^{n-1}$ but also $a_{n-2} \geq 2^{n-2}$.
Common mistake: use wrong indices, for example writing “Assume $\forall k \leq n,\ a_{n} \geq 2^n$” instead of “Assume $\forall k \leq n,\ a_{k} \geq 2^k$”.
What To Show (WTS): $a_n \geq 2^n$.
$a_{n} = a_{n-1} + 2a_{n-2}$ by the recurrence relation definition
$a_{n} \geq 2^{n-1} + 2 \times 2^{n-2}$ by the inductive hypothesis at levels $n-1$ and $n-2$
$a_n \geq 2^{n-1} + 2^{n-1} = 2 \times 2^{n-1} = 2^{n}$
Common mistake: algebra mistake using powers to get $2^n + 2 \times 2^{n-1} = 2^{n+1}$
Common mistake: to prove the WTS, start by the WTS, derive something true (for eg, $2^n \geq 2^n$) and conclude the WTS is true. We can’t start by the whole WTS! We have to start by, say, the left-hand side of the WTS and get the right-hand side. Or the opposite.
Conclusion
By strong induction, $\forall n \geq 1,\ a_{n} \geq 2^n$.