Simple Solutions to Homogeneous Recursions

Question

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?

Answer 1

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) $$

Answer 2

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.

Answer 3

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,...$$