# Proof By Strong Induction

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

Quentin Pleplé
March 2013