Consider the recurrence relation $a_n = 5a_{n-1}-8a_{n-2}+4a_{n-3}$ and $a_0 = 0$, $a_1 = 0$, $a_2 = 1$. Find a closed form expression for $a_n$.
I have computed the OGF $A(z)$ of $(a_n)_n$ as
$$A(z) = \frac{z^2}{1-5z+8z^2-4z^3}.$$
According to Wolfram Alpha this has the following partial fraction decomposition:
$$= \frac{-3}{2(1-2z)} + \frac{1}{2(1-2z)^2} + \frac{1}{1-z}$$
and using the Generalised Binomial Theorem yields:
$$= -\frac{3}{2} \sum_{n = 0}^\infty 2^nz^n + \frac{1}{2} \sum_{n=0}^\infty \binom{-2}{n}2^nz^n + \sum_{n=0}^\infty z^n.$$
Thus we should have
$$a_n = [z^n]A(z) = -\frac{3}{2}2^n + \frac{1}{2} \binom{-2}{n}2^n +1 = -3 \cdot 2^{n-1} + \binom{-2}{n}2^{n-1} +1 $$
However, this does not seem to be true. Could you please tell me what I am doing wrong?
Best Answer
Starting from $$\frac{z^2}{1-5z+8z^2-4z^3}$$ then \begin{align} \sum_{n=0}^{\infty} a_{n} \, x^n &= \frac{x^2}{1-5x+8x^2-4x^3} = \frac{x^2}{(1-x)(1-2 x)^2} \\ &= \frac{1}{1 - x} - \frac{3}{2 (1 - 2 x)} + \frac{1}{2 \, (1 - 2 x)^2} \\ &= \sum_{n} x^n - \frac{3}{2} \, \sum_{n} 2^n \, x^n + \frac{1}{2} \, \sum_{n} 2^n (n+1) \, x^n \\ &= \sum_{n=0}^{\infty} \left(1 - 3 \cdot 2^{n-1} + 2^{n-1} \, (n+1) \right) \, x^n \\ &= \sum_{n=0}^{\infty} \left(1 + 2^{n-1} \, (n-2) \right) \, x^n \end{align} which gives $$ a_{n} = 1 + 2^{n-1} \, (n-2). $$
As a check: \begin{align} \phi_{n} &= 5 \, a_{n-1} - 8 \, a_{n-2} + 4 \, a_{n-3} \\ &= (5 - 8 + 4) + 2^{n-4} \, (5 \cdot 4 \, (n-3) - 8 \cdot 2 \, (n-4) + 4 \, (n-5)) \\ &= 1 + 2^{n-1} \, (n-2) = a_{n} \end{align} which is the expected result.