Solve $a_{n+1} - a_n = n^2$ using generating functions

Question

The Full Question

Using the method of generating functions, solve $a_{n+1} - a_n = n^2$ where $a_0 = 1$

My Research

Scanned the website for similar answers, reviewed the following links:

Solve the following recurrences using generating functions.

can we use generating functions to solve the recurrence relation $a_n = a_{n-1} + a_{n-2}$, $a_1=1$, $a_2=2$?

Solving a recurrence equation using generating functions

Using Generating Functions to Solve Recursions

Solve the following recursive relation by using generating functions

Solve a recursion using generating functions?

Solving recurrences using generating functions

None of them would make my question a duplicate and none of them really addressed what I was having difficulty with.

My Work

If we multiply each side by $x^{n+1}$ and sum each of the possible cases $a_0,a_1,\dots$ we have:

$$\sum\limits_{j=0}^{\infty}{a_{n+1}x^{n+1}} - x\sum\limits_{j=0}^{\infty}a_nx^n = \sum\limits_{j=0}^{\infty}n^2x^{n+1}$$

If we let $f(x) = \sum\limits_{j=0}^{\infty}a_nx^n$ our equation transforms into:

$$f(x)-a_0 -xf(x) = \sum\limits_{j=0}^{\infty}n^2x^{n+1}$$

Factoring $f(x)$ and observing the LHS is a well known generating functions and using the fact that $a_0 = 1$, we get:

$$f(x)(1-x) = \frac{x(1+x)}{(1-x)^3} + 1 \implies f(x) = \frac{x(1+x)}{(1-x)^4} + \frac{1}{1-x}$$

We now need the coefficients of $x^n$ of these two functions we are adding. The right function it is well known that is has coefficients of $1$. We need partial fraction decomposition to obtain the coefficients of the left hand side.

$$\frac{x(1+x)}{(1-x)^4}= \frac{A}{1-x}+\frac{B}{(1-x)^2}+\frac{C}{(1-x)^3}+\frac{D}{(1-x)^4}$$

$\implies x(1+x)= A(1-x)^3+B(1-x)^2+C(1-x)+D$

Expanding this, we have

$Ax^3+3Ax^2 - 3Ax + A + Bx^2 -2Bx + B +C -Cx +D$

Which gives us the system of equations:

1) $A+B+C+D = 0$

2) $-3A-2B-C =1$

3) $3A+B = 1$

4) $A = 0$

5) $D = 0$

$3(0)+B=1 \implies B=1$ Using equations 3&4

$-3(0) -2 - C=1\implies C=3$ Using equations Using equations 2&1 and the result above

$0+1+3+0 = 0$ plugging in our results to equation 1

that is obviously not correct. Where did I make my mistake. I feel I'm very close and must have messed up the partial fraction decomposition somewhere, but maybe the mistake is somewhere else. Can anyone find where I went wrong?

Answer 1

You made a mistake in solving $$ x(1+x)= A(1-x)^3+B(1-x)^2+C(1-x)+D$$

A faster way to solve this is the following: $$x = 1 \Rightarrow D=2$$

Next derivate $$1+2x=-3A(1-x)^2-2B(1-x)-C$$ plug in $x=1$. Then derivate again, and plug in $x=1$. Continue...

Answer 2

Define the generating function $A(z) = \sum_{n \ge 0} a_n z^n$. Take the recurrence, multiply by $z^n$, sum over $n \ge 0$:

$$ \sum_{n \ge 0} a_{n + 1} z^n - \sum_{n \ge 0} a_n z^n = \sum_{n \ge 0} n^2 z^n $$

Recognize some sums, note that:

$\begin{align} \sum_{n \ge 0} z^n &= \frac{1}{1 - z} \\ \sum_{n \ge 0} n z^n &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - z} \\ &= \frac{z}{(1 - z)^2} \\ \sum_{n \ge 0} n^2 z^n &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{z}{(1 - z)^2} \\ &= \frac{z + z^2}{(1 - z)^3} \\ \end{align}$

$$ \frac{A(z) - a_0}{z} - A(z) = \frac{z + z^2}{(1 - z)^3} $$

Plug in $a_0 = 1$, solve for $A(z)$, split into partial fractions:

$\begin{align} A(z) &= \frac{1 - 3 z + 4 z^2}{1 - 4 z + 6 z^2 - 4 z^3 + z^4} \\ &= \frac{4}{(1 - z)^2} + \frac{5}{(1 - z)^3} + \frac{2}{(1 - z)^4} \end{align}$

Consider that:

$$ (1 - z)^{-r} = \sum_{n \ge 0} (-1)^n \binom{-r}{n} z^n = \sum_{n \ge 0} \binom{r + n - 1}{r - 1} z^n $$

Note that $\binom{n + r - 1}{r - 1}$ is a polynomial of degree $r - 1$ in $n$.

Pick the coefficient of $z^n$ of $A(z)$:

$\begin{align} a_n &= 4 \binom{n + 1}{1} + 5 \binom{n + 2}{2} + 2 \binom{n + 3}{3} \\ &= \frac{2 n^3 + 27 n^2 + 91 n + 66}{6} \end{align}$