0
$\begingroup$

Given the recurrence relation $a_n = 2a_{n-1} + a_{n-2}$

$a_0 = 1$ and $a_1=1$

Is it true that $a_n < 6a_{n-2}$ for all $n\ge4$

I'm not really sure how to go about solving this problem. I've tried to replace $a_n$ in the inequality and solve and I've also tried solving the finding the close form solution but I don't seem to be getting anywhere. If someone could point me in the right direction I would appreciate it. Thanks!

$\endgroup$
3
$\begingroup$

It’s not true without more information. Suppose, for instance, that $a_0=a_1=0$; then you can show by induction that $a_n=0$ for all $n$, and it’s certainly not true that $0<6\cdot0$.

However, you can show that

$$\begin{align*} a_n&=2a_{n-1}+a_{n-2}\\ &=2(2a_{n-2}+a_{n-3})+a_{n-2}\\ &=5a_{n-2}+a_{n-3}\;, \end{align*}\tag{1}$$

and if your initial conditions allow you to show that $a_4>6a_2$ and $\langle a_n:n\in\Bbb N\rangle$ is increasing for $n\ge 2$, so that $a_{n-2}>a_{n-3}$ and hence $5a_{n-2}+a_{n-3}<6a_{n-2}$ when $n\ge 5$, then you can use $(1)$ to show by induction that $a_n<6a_{n-2}$ for all $n\ge 4$.

Added: Now we have the initial conditions $a_0=a_1=1$. Thus, $a_2=3$, $a_3=7$, and $a_4=17$. By a trivial induction each $a_n>0$, since (by the induction hypothesis) it’s the sum of two positive numbers. Another very easy induction then shows that $a_n>a_{n-1}$ for all $n\ge 2$, since $$a_n=2a_{n-1}+a_{n-2}=a_{n-1}+(a_{n-1}+a_{n-2})>a_{n-1}\;.$$ Finally, $a_4=17<18=6a_2$, so the main induction does indeed get off the ground.

$\endgroup$
  • $\begingroup$ Whoops I'm sorry a0 and 1 both equal 1. I updated my question. I think this is exactly the right hint I needed though thanks! $\endgroup$ – Nathan Schwermann Feb 12 '13 at 3:04
  • $\begingroup$ @schwiz: You’re welcome! I’ve added a bit to the answer to take into account the added information. $\endgroup$ – Brian M. Scott Feb 12 '13 at 3:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.