Strong Induction (proof of inequality from linear recurrence)

Question

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$

Not sure how to go about this

Do I start by proving it for the base case?

Answer 1

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$

Answer 2

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