# Strong Induction (proof of inequality from linear recurrence)

Define a recursive sequence $$a_0, a_1, a_2,\ldots$$ by

$$a_0 =1$$, $$a_1 =3$$, $$a_n = 2a_{n−1} + 8a_{n−2}$$ for all integers $$n≥2$$

Prove by strong induction that $$a_n ≤ 4^n$$ for all integers $$n ≥ 0$$

Do I start by proving it for the base case?

• Yes, starting with the base case is always a good idea when proving something with an inductive argument. Commented May 4, 2015 at 1:38
• do you mean $a_n \le 4^n$? Commented May 4, 2015 at 1:45
• yep sorry, my mistake Commented May 4, 2015 at 1:46

$a_0 = 1 \leq 4^0$ is a true sentence,hence the claim is true for $n = 0$. Assume it is true for all $0 \leq k < n$, you prove it true for $n$: $a_n = 2a_{n-1}+8a_{n-2} \leq 2\cdot 4^{n-1}+8\cdot 4^{n-2} = \dfrac{4^n}{2}+ \dfrac{4^n}{2} = 4^n$, thus it is true for all $n \geq 0$ as claimed.
• so its true because i proved that $a_n$ is equal to $4^n$ for all $n≥0$ by doing that working out? Commented May 4, 2015 at 3:43
• $a_n$ is not equal to $4^n$, its less than or equal to $4^n$. I used the inductive step at two places: $a_{n-1} \leq 4^{n-1}$ and $a_{n-2} \leq 4^{n-2}$ to get to $a_n \leq 4^n$. Commented May 4, 2015 at 3:47
Hint $\$ Equivalently it sufficies to show that $\,c_n = a_n/4^n \le 1.\,$ The recurrence becomes $\, c_n = (c_{n-1}+c_{n-2})/2\,$ so by induction $\,c_{n-1},c_{n-2}\le1 \,\Rightarrow\, c_n \le (1\!+\!1)/2 = 1$