Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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!
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.
