$$a_0 = 0, a_1 = 1 \quad \text{ and } \quad a_n = a_{n-1} + 2a_{n-2}\quad \text{ for }n\geq 2$$
a) Find $a_2,a_3,a_4,a_5$
b) Find a closed form-formula for $a_n$
I found the value to be $(a_n)_{n\in \Bbb N} = \{0, 1, 1, 3 , 5, 11, …\}$
I have not the slightest clue how to find a closed form formula, so if anyone could help me out with this I would be greatly appreciated.
I've seen similar questions with answers talking about finding a geometric series, but I can assure that this question should not require knowledge of such since we have not done anything of the sort in class.
Is it just trial and error to find such a formula? Or is there a set method to follow?
I noticed that the formula is very similar to the Fibonacci sequence:
$$F(n) = F(n-1) + F(n-2)$$
Thanks.
Best Answer
Without any of the usual theoretical tools, you’ll need to do a bit of pattern-recognition. Notice the following pattern:
$$\begin{align*} a_0=0&\\ a_1=1&=2\cdot0+1\\ a_2=1&=2\cdot1-1\\ a_3=3&=2\cdot1+1\\ a_4=5&=2\cdot3-1\\ a_5=11&=2\cdot5+1\\ a_6=21&=2\cdot11-1 \end{align*}$$
This suggests the first-order recurrence $a_n=2a_{n-1}+(-1)^{n-1}$. You can prove by induction that it follows from your second-order recurrence and initial conditions, but let’s hold off on that: it looks like a pretty solid guess, so let’s see what we can do with it. Specifically, we’ll try ‘unwinding’ it:
$$\begin{align*} a_n&=2a_{n-1}+(-1)^{n-1}\\ &=2\left(2a_{n-2}+(-1)^{n-2}\right)+(-1)^{n-1}\\ &=2^2a_{n-2}+2(-1)^{n-2}+(-1)^{n-1}\\ &=2^2\left(2a_{n-3}+(-1)^{n-3}\right)+2(-1)^{n-2}+(-1)^{n-1}\\ &=2^3a_{n-3}+2^2(-1)^{n-3}+2(-1)^{n-2}+(-1)^{n-1}\\ &\;\vdots\\ &=2^ka_{n-k}+\sum_{i=1}^k2^{i-1}(-1)^i\\ &\;\vdots\\ &=2^na_0+\sum_{i=1}^n2^{i-1}(-1)^i\\ &=\sum_{i=1}^n2^{i-1}(-1)^i\;, \end{align*}$$
since $a_0=0$. Finally,
$$\sum_{i=1}^n2^{i-1}(-1)^i=\sum_{i=0}^{n-1}2^i(-1)^{i+1}=-\sum_{i=0}^{n-1}(-2)^i\;,$$
which is just a geometric series, for which you should know a closed form. Once you have that, you should prove by induction that it actually does satisfy your original recurrence.
This ‘unwinding’ technique works surprisingly often with simple first-order recurrences.