Recurrence problem for $a_5$ Assume that the sequence $\{a_0,a_1,a_2,\ldots\}$ satisﬁes the recurrence $a_{n+1} = a_n + 2a_{n−1}$. We know that $a_0 = 4$ and $a_2 = 13$. What is $a_5$?
 A: You can solve this like a differential equation. Set up the characteristic equation: $\lambda^{2} - \lambda - 2 = 0$. Then solve $\lambda = -2, 1$. So $a_{n} = c_{1} + c_{2}(-2)^{n}$. Solve for $c_{1}$ and $c_{2}$ using your initial constraints.
A: First find $a_1$: using the equation with $n=1$:
$$
13 = a_1 + 2\times 4\implies a_1 = 5
$$
Then compute $a_3, a_4, a_5$:
$$
a_3 = 13 + 2\times 5 = 23;\\
a_4 = 23 + 2\times 13 = 49;\\
a_5 = 49 + 2\times 23 = 95.\\
$$

Another solution is to find $a_n$ for each $n$: the caracteristic equation
is $r^2 - r- 2 = 0$, hence
$$
a_n = A(-1)^n + B2^n;\\
\begin{cases}
13 &=& A+4B\\
4 &=& A+B \end{cases}\implies (A,B) = (1,3)\\
a_5 = -1 + 3\times 2^5=95.
$$
A: Hint Let $n=1$. Then your recurrence says that $a_2=a_1+2a_0$. Solve for $a_1$ then use the recurrence relation with $n=2,3,4$ to get $a_5$.
A: Rearranging the recurrence relation gives $a_n = a_{n+1} - 2a_{n-1}$, so that $a_1 = 13 - 2 \cdot 4 = 5$. Now that we know $a_0,a_1$ and $a_2$ you are good to go by simply applying the recursion repeatedly until you get to the fifth term. 
A: From the recurrence you get $a_1=5$. Write the recurrence as:
$$
a_{n + 2} = a_{n + 1} + 2 a_n \qquad a_0 = 4, a_1 = 5
$$
Define the generating function:
$$
A(z) = \sum_{n \ge 0} a_n z^n
$$
Multiply the recurrence by $z^n$ and sum over $n \ge 0$. Notice that:
\begin{align}
\sum_{n \ge 0} a_{n + 1} z^n &= \frac{A(z) - a_0}{z} \\
\sum_{n \ge 0} a_{n + 2} z^n &= \frac{A(z) - a_0 - a_1 z}{z^2} \\
\end{align}
to get:
$$
\frac{A(z) - 4 - 5 z}{z^2} = \frac{A(z) - 4}{z} + 2 A(z)
$$
Solving this equation for $A(z)$, and splitting into partial fractions:
$$
A(z) = \frac{4 + z}{1 - z - 2 z^2} = \frac{1}{1 + z} + \frac{3}{1 - 2 z}
$$
This are just geometric series:
$$
a_n = (-1)^n + 3 \cdot 2^n
$$
So the value sought is $a_5 = (-1)^5 + 3 \cdot 2^5 = 95$
