i have a recurrence relation $a_n = 2a_{n-1} + a_{n-2}$ with the inital conditions $a_0 = 0$ and $a_1 = 1$
From this, i know the characteristic equation is: $x^2 - 2x -1$ however this poses a problem because the roots are not whole numbers, rather, they are $1 + \sqrt{2}$ and $1 - \sqrt{2}$. Is there another way to solve these sorts of recurrence relations? Thanks!
Let $a_n = c_1 (1+\sqrt{2})^n + c_2 (1-\sqrt{2})^n$. We then have
$$c_1 (1+\sqrt{2})^0 + c_2 (1-\sqrt{2})^0 = c_1 + c_2 = 0$$ $$c_1 (1+\sqrt{2})^1 + c_2 (1-\sqrt{2})^1 = c_1 (1+\sqrt{2}) + c_2 (1-\sqrt{2})= 1$$
So $c_1 = \frac{1}{2\sqrt{2}}$ and $c_2 = -\frac{1}{2\sqrt{2}}$. So then
$$ a_n = \frac{1}{2\sqrt{2}} (1+\sqrt{2})^n - \frac{1}{2\sqrt{2}}(1-\sqrt{2})^n $$
Try it for yourself and plug in values of $n$. Even though the roots of characteristic were irrational, you will get integer values. (Even better, can you think of a proof that $a_n$ will always be an integer.)