Recurrence relationship where the difference of two consecutive terms is polynomial. Solution by generating functions.

Question

I have this recurrence relation

$$h_{n} = h_{n-1} + 4n(n-1) \ \text{for} \ n \geq 1 \ \text{with} \ h_{0} = 0, h_{1} = 0$$

I am asked to find $h_{9}$.

I have attempted to solve this by generating functions and ended up with a closed form solution as:
$g(x) = \frac{4x}{(1-x)^3} - \frac{4x}{(1-x)^2}$
I feel like this is correct, though I'm not totally sure. I then rewrote these as infinite sums so I can find the coefficient of $x^n$ more easily:
$4x \Sigma^{\infty}_{n=0}\binom{n+2}{2}x^n - 4x\Sigma^{\infty}_{n=0}nx^n$
for every value of $n$ the coefficient is $+4$ more than the actual answer, I've looked at my working for a while but not sure how the answer is so close to the solution?
Thanks

Answer 1

I realised my mistake, it was in the second series, the coefficient of $x^n$ is $n+1$ not $n$!

Answer 2

You don't need the generating method which is often used for much harder problem. For this one, observer that: $h_n = (h_n - h_{n-1})+(h_{n-1} - h_{n-2})+...+(h_1 - h_0) + h_0 = 4n^2 - 4n + 4(n-1)^2 - 4(n-1) +...+ 4\cdot 2^2 - 4\cdot 2+4\cdot 1^2 - 4\cdot 1+0= 4(1^2+2^2+...+n^2) -4(1+2+...+n)= 4\cdot \dfrac{n(n+1)(2n+1)}{6}-4\cdot \dfrac{n(n+1)}{2}$. From this you can find any term and just plug $n = 9$ in the formula to get $h_9$.