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$
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$
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$ !
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*}$