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.
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?
Best Answer
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...