Find an explicit formula for a sequence

Question

I need to find an explicit formula for the following sequence:

$$ a_0=1,\quad a_1=2,\quad a_n=2a_{n-1}+a_{n-2},\ \hbox{for}\ n\ge2 $$ I tried using the characteristic sequence and elimination method which brought me to $a_n = 0.855(2.41^n) - 0.145(0.41^n)$ and an incorrect answer. Is there a different way to solve this problem?

Any help is appreciated.

Answer 1

One mistake that you've done is this: the characteristic equation has solutions $1 \pm \sqrt{2}$, which is approximately $2.414$ and $-0.414$. That means that the general solution to the recurrence relation is given by $$ A_n = c_1\cdot 2.414^n + c_2\cdot (-0.414)^n $$ where those brackets are essential. You don't have those, and I suspect that that's why you've gotten the wrong answer.

Another source of mistakes might be that you have rounded the results. I would personally prefer to keep it as $$ A_n = c_1\cdot (1+\sqrt2)^n + c_2\cdot (1-\sqrt2)^n $$ mostly because it makes the following calculations easier, and the resulting expression is more pleasing to the eye.

Answer 2

problem:

$$ y_{n} + p*y_{n-1} + q*y_{n-2} = 0 \\y_{0} = a, y_{1} = b $$

to find the solution:

let $\lambda_1 $ and $ \lambda_2 $ be the solution to:

$$ \lambda^{2} + p*\lambda + q = 0 $$

The solution is $$y_{n} = (c_{1}*n+c_{2})*(\lambda_1)^{n} $$

if $$\lambda_1 = \lambda_2 $$

else $$y_{n} = c_{1}*(\lambda_1)^{n} + c_{2}*(\lambda_2)^{n} $$

To find c1 and c2 you just use y0 and y1. In your case:

$$ c_{1}+c_{2} = a $$

$$ c_{1}*\lambda_1 + c_{2}*\lambda_2 = b $$

Do not use approximation and numerical values, keep it literal using square roots etc... It should work !