1
$\begingroup$

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?

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

2 Answers 2

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ so its true because i proved that $a_n$ is equal to $4^n$ for all $n≥0$ by doing that working out? $\endgroup$
    – joseph
    Commented May 4, 2015 at 3:43
  • $\begingroup$ $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$. $\endgroup$
    – DeepSea
    Commented May 4, 2015 at 3:47
0
$\begingroup$

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$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .