# Proof By Strong Induction

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