Simple Solutions to Homogeneous Recursions Let $b_n - 2b_{n-2} + b_{n-3} = 0$ be a linear homogeneous recursion.  I was able to solve this using a characteristic equation but deriving coefficients became incredibly messy.  However, I thought this should be a very simple recursion to solve.  Does anyone have alternative suggestions for how to avoid messy algebra?
 A: Use the technique in Wilf's "generatingfunctionology". Define the generating function $B(z) = \sum_{n \ge 0} b_n z^n$, and write:
$$
b_{n + 3} - 2 b_{n + 1} + b_n = 0
$$
Then:
$$
\frac{B(z) - b_0 - b_1 z - b_2 z^2}{z^3} 
  - 2 \frac{B(z) - b_0}{z}
  + B(z) = 0
$$
This gives as partial fractions:
$$
B(z) = \frac{2 b_0 - b_1 - b_2 + (3 b_0 - b_1 - 2 b_2) z}{1 - z - z^2}
         - \frac{b_0 -  b_1 - b_2}{1 - z}
$$
Now:
$$
\frac{z}{1 - z - z^2}
$$
is the generating function for the Fibonacci numbers $F_n$, while
$$
\frac{1}{1 - z - z^2}
$$
turns out to be the generating function for the Fibonacci numbers displaced by 1, $F_{n + 1}$. So:
$$
b_n = (3 b_0 - b_1 - 2 b_2) F_n 
        + (2 b_0 - b_1 - b_2) F_{n + 1}
        - (b_0 -  b_1 - b_2)
$$
A: Try to make use of:
$$b_n-b_{n-1} = -(b_{n-1}-b_{n-2}) + (b_{n-2}-b_{n-3}) $$
This will lead you to a slightly simpler and more elegant solution.
A: This answer is just a worked out version of my previous answer. My intention is to show that in this case the solution can also be found without the need to deal with a third order polynomial.
We have
$$b_n = 2b_{n-2} - b_{n-3},\quad n=0,1,2,... $$
The initial conditions $b_{-3}, b_{-2}, b_{-1}$ must be given. We can rewrite the recurrence as follows:
$$b_n - b_{n-1} = -(b_{n-1}-b_{n-2}) + (b_{n-2}-b_{n-3})$$
Defining $c_n=b_n-b_{n-1}$ we get
$$c_n = -c_{n-1}+c_{n-2}$$
with initial conditions $c_{-1}=b_{-1}-b_{-2}$ and $c_{-2}=b_{-2}-b_{-3}$. We obtain the generating function
$$C(z) = \frac{c_{-1}z - (c_{-1}-c_{-2})z^2}{z^2+z-1} = \frac{a_1z}{z-z_1} + \frac{a_2z}{z-z_2}$$ with
$$ z_1 = \frac{-1+\sqrt{5}}{2},z_2 = \frac{-1-\sqrt{5}}{2},
a_1=\frac{c_{-1}-(c_{-1}-c_{-2})z_1}{z_1-z_2},
a_2=\frac{c_{-1}-(c_{-1}-c_{-2})z_2}{z_2-z_1}$$
The resulting sequence is
$$c_n = a_1z_1^n + a_2z_2^n, \quad n=0,1,2,...$$
Finally, we can obtain the sequence $b_n$ by summing over $c_n$:
$$b_n = \sum_{k=0}^n c_k + b_{-1} =
a_1\frac{1-z_1^{n+1}}{1-z_1} + a_2\frac{1-z_2^{n+1}}{1-z_2} + b_{-1}, \quad n=0,1,2,...$$
