Find a closed form for the recurrence $g(n+2)= 5g(n+1)-5g(n)+g(n-1)$

Question

More specifically use the initial values $g(1)=0, \ g(2)=0, \ g(3)=1$. I know several methods for solving order two recurrences but this being an order three would include having to evaluate a cubic polynomial and then solve for the initial values.
The first several numbers are $0,0,1,5,20,76...$
Is there a nice shortcut of a method?

Answer 1

The shortest method is definitely to use sage or some other computer algebra system. I solve a lot of recurrences, and my sage startup script makes it particularly easy for me. In particular:

sage: eqn = T(n+3) == 5*T(n+2) - 5*T(n+1) + T(n)
sage: rsolve(eqn,n,[0,0,1])
1/12*(-sqrt(3) + 2)^n*(sqrt(3) + 3) - 1/12*(sqrt(3) + 2)^n*(sqrt(3) - 3) - 1/2

We can, of course, display this more nicely using the latex command:

$$ \frac{1}{12} \, {\left(-\sqrt{3} + 2\right)}^{n} {\left(\sqrt{3} + 3\right)} - \frac{1}{12} \, {\left(\sqrt{3} + 2\right)}^{n} {\left(\sqrt{3} - 3\right)} - \frac{1}{2} $$

---

Of course, there's something to be said for solving these kinds of equations by hand. I'm personally partial to generating functions for this task, but there's lots of approaches. I don't know of any "shortcuts" to do these kinds of problem in general. Much like taking derivatives of nested functions, the process is tedious, but not hard:

We start by writing $G(z) = \sum g_n z^n$, then by multiplying your recurrence by $z^n$ and summing we find

$$ \frac{G - g_2 z^2 - g_1 z - g_0}{z^3} = 5 \frac{G - g_1 z - g_0}{z^2} - 5 \frac{G - g_0}{z} + G $$

But we know $g_0 = 1$, $g_1 = g_2 = 0$. So we can plug these in and solve for

$$ G = \frac{1 - 5z + 5z^2}{1 - 5z + 5z^2 - z^3} $$

then using partial fractions, we can write this as

$$ G = \frac{\sqrt{3} + 3}{12} \frac{1}{1 - (- \sqrt{3} + 2) z} - \frac{\sqrt{3} - 3}{12} \frac{1}{1 - ( \sqrt{3} + 2) z} - \frac{1}{2} \frac{1}{1-z}. $$

Then using the formula for a geometric series on the right hand side, and remembering $g(n)$ is the coefficient of $z^n$ in $G$, we can get the formula that sage got for us earlier.

If you want to read more about this technique, you might be interested in the excellent book generatingfunctionology which is available for free at that link!

---

I hope this helps ^_^