Finding a closed-form formula for a sequence that is defined recursively

Question

$$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.

Answer 1

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.

Answer 2

$a_n = a_{n-1} + 2a_{n-2} \to x^2 - x - 2 = 0 \to (x-2)(x+1) = 0 \to x = 2, -1 \to a_n = A2^n + B(-1)^n$. $a_0 = 0, a_1 = 1\to A+B=0, 2A-B=1 \to A = \dfrac{1}{3}, B = -\dfrac{1}{3} \to a_n = \dfrac{2^n -(-1)^n}{3}$.

Thus: $a_2 = \dfrac{2^2 - (-1)^2}{3} = 1, a_3 = 3, a_4 = 5, a_5 = 11$.

Answer 3

One way to do this is to use generating functions.

Let $G(x)=\sum_{n=0}^{\infty}a_nx^n$.

We have the relation : $a_n=a_{n-1}+2a_{n-2}$.

Multiply both sides by $x^n$ and summing from $n=2$ to $\infty$ we get:

$G(x)-a_0-a_1x=x(G(x)-a_0)+2x^2G(x)$.

Then we get: $G(x)(1-x-2x^2)=a_0-a_0x+a_1x=x$ (since $a_0=0,a_1=1$).

So

$\begin{align} G(x)&=\frac{x}{1-x-2x^2} \\ &=\frac{1}{3(1 - 2 z)} - \dfrac{1}{3 (1 + x)} \end{align}$.

We can read off the coeficients of two geometric series:

$\begin{align} a_n &= \frac{1}{3} \cdot 2^n - \frac{1}{3} (-1)^n \\ &= \frac{2^n - (-1)^n}{3} \end{align}$

Answer 4

Linear recurrence relations with constant coefficients produce exponentially growing terms in the sequence. Hence, we can assume the closed form solution to $a_n$ is some type of exponential function in $n$. Simply, let

$$a_n = r^n$$

for some constant $r$ to be determined. For the recurrence relation you provided, we can make a substitution:

$$r^n = r^{n-1} + 2r^{n-2}$$

Dividing both sides of the equation by $r^{n-2}$, knowing that $r^{n-2}$ is not zero for $n>2$, yields

$$r^2 = r + 2$$

Now the solution to $r$ is easier to find. This is known as the auxiliary equation or characteristic equation. So, we get $r = -1$ or $r = 2$. This makes it look like there are two solutions for $a_n$, one with $r=-1$ and the other with $r=2$, but really $a_n = r^n$ is some linear combination of the powers of each root (-1 and 2), which means

$$a_n = c_0 (-1)^n + c_1 (2)^n$$

where $c_0$ and $c_1$ are the linear coefficients. Make the substitutions $a_0=0$ and $a_1=1$ to get the following system of two equations:

$$0 = c_0 + c_1$$ $$1 = -c_0 + 2c_1$$

The solution for $c_0$ and $c_1$ gets plugged back into the expression for $a_n$ to get the final answer:

$$a_n = -\frac{1}{3}(-1)^n + \frac{1}{3}2^n$$

The method I just described here only works when there are two distinct characteristic roots (in this case, we had -1 and 2, which are different numbers, so this works). Otherwise, a minor change is needed to make it all work.