The sequence $(a_0,a_1,a_2,\cdots,)$ satisfies $ a_{n+1}=a_n+2a_{n−1}$. What is $a_5$?

Question

Assume that the sequence $(a_0,a_1,a_2,\cdots,)$ satisfies the recurrence $\displaystyle a_{n+1}=a_n+2a_{n−1}$. We know that $a_0=4$ and $a_2=13$. What is $a_5$?

I got $a_1=5, a_3=23, a_4=49, a_5=95$

Answer 1

If you want to calculate the $n$-th term, here is how:

$a_{n+1} - a_n - 2a_{n-1} = 0 \to x^2 - x - 2 = 0 \to (x-2)(x+1) = 0 \to x = -1, 2$. Thus the

$a_n = A(-1)^n + B2^n$. We have that: $a_0 = 4 \to a_1 = a_2 - 2a_0 = 13 - 2(4) = 5$. So:

$5 = a_1 = A(-1)^1 + B2^1 = -A + 2B$, and

$13 = a_2 = A(-1)^2 + B2^2 = A + 4B$.

Adding these equations we find $B = 3$, and solve for $A = 13 - 4(3) = 1$. Thus:

$a_n = (-1)^n + 3\cdot 2^n$.

Check that $a_5 = (-1)^5 + 3\cdot 2^5 = -1 + 96 = 95$ !

Answer 2

For just the 5th term this is overkill, but anyway.

Define the generating function:

$\begin{align*} A(z) &= \sum_{n \ge 0} a_n z^n \end{align*}$

Write the recurrence shifted (subtraction in indices gets nasty), multiply by $z^n$, sum over $n \ge 0$, recognise the sums:

$\begin{align*} \sum_{n \ge 0} a_{n + 2} z^n &= \sum_{n \ge 0} a_{n + 1} z^n + 2 \sum_{n \ge 0} a_n z^n \\ \frac{A(z) - a_0 - a_1 z}{z^2} &= \frac{A(z) - a_0}{z} + 2 A(z) \end{align*}$

Solve for $A(z)$, using initial values, write as partial fractions:

$\begin{align*} A(z) &= \frac{4 + 9 z}{(1 + z) (1 - 2 z)} \\ &= \frac{17}{3 (1 - 2 z)}- \frac{5}{3 (1 + z)} \end{align*}$

We are interested in the coefficients:

$\begin{align*} a_n &= [z^n] A(z) \\ &= \frac{17}{3} \cdot 2^n - \frac{5}{3} (-1)^n \\ &= \frac{17 \cdot 2^n - 5 \cdot (-1)^n}{3} \end{align*}$

Thus:

$\begin{align*} a_5 &= \frac{17 \cdot 2^5 - 5 \cdot (-1)^5}{3} \\ &= 183 \end{align*}$