I'm trying to solve: $a_{n+1}-a_n=n^2$, $n\le0$ , $a_0=1$ using generating functions.
Step 1) Multiply by $x^{n+1}$
$$a_{n+1}x^{n+1}-a_nx^{n+1}=n^2x^{n+1}$$
Step 2) Take the infinite sums
$$\sum_{n\ge0}^{\infty}a_{n+1}x^{n+1}-\sum_{n\ge0}^{\infty}a_nx^{n+1}=\sum_{n\ge0}^{\infty}n^2x^{n+1}$$
Our prof gave us the identity: $$\sum_{n\ge0}^{\infty}n^2x^n= \frac{x+x^2}{{1-x}^3}$$
So I factored out an $x^1$ from my RHS(to use the identity) and simplified the LHS to get:
$$(f(x)-a_0)-xf(x)=x\left(\frac{x+x^2}{{1-x}^3}\right)$$
therefore: $$f(x)=x\left(\frac{x+x^2}{{(1-x)}^4}\right)+\frac{1}{(1-x)}=\frac{x(x+x^2)+(1-x)^3}{(1-x)^4}$$
Step 3) Decompose the function by partial fractions
Saving you all the gory details I got:
$$f(x)=\frac{4}{(1-x)^2}-\frac{5}{(1-x)^3}+\frac{2}{(1-x)^4}$$
Step 4) Finding the coefficient of $x^n$ in each term:
I recognized that each term was a derivative of the the power series $\frac{1}{(1-x)}$ to get:
$$4[x^n]\sum(n+1)(x^n)-5\frac12[x^n]\sum(n+2)(n+1)(x^n)+2\frac13[x^n]\sum(n+3)(n+2)(n+1)(x^n)$$
So that whole thing = $a_n$ which equals:
$$4(n+1)-5\frac12(n+2)(n+1)+2\frac13(n+3)(n+2)(n+1)$$
However the answer is: $a_n=1+[n(n-1)(2n-1)\frac16]$
I tried multiplying out to see if they were the same but they're not(I checked on wolfram too).
Could anyone tell me where I went wrong?
Thank you.
Best Answer
Consider the difference equation $a_{n+1} - a_{n} = n^{2}$ where $n \geq 0$ and $a_{0} = 1$. It can be quickly determined that \begin{align} \sum_{n=0}^{\infty} n^{2} x^{n} = \frac{x(1+x)}{(1-x)^{3}} \end{align} for which \begin{align} \sum_{n=0}^{\infty} a_{n+1} x^{n} - \sum_{n=0}^{\infty} a_{n} x^{n} &= \frac{x(1+x)}{(1-x)^{3}} \\ \frac{1}{x} \cdot \sum_{n=0}^{\infty} a_{n+1} x^{n+1} - \sum_{n=0}^{\infty} a_{n} x^{n} &= \\ \frac{1}{x} \sum_{n=1}^{\infty} a_{n} x^{n} - \sum_{n=0}^{\infty} a_{n} x^{n} &= \\ \frac{1}{x} \left( - a_{0} + \sum_{n=0}^{\infty} a_{n} x^{n} \right) - \sum_{n=0}^{\infty} a_{n} x^{n} &= \\ - 1 + (1-x) \sum_{n=0}^{\infty} a_{n} x^{n} &= \frac{x^{2} (1+x)}{(1-x)^{3}}. \end{align} This leads to \begin{align} \sum_{n=0}^{\infty} a_{n} x^{n} = \frac{2 - 5(1-x) + 4 (1-x)^{2}}{(1-x)^{4}} \end{align} which can be seen in the form \begin{align} \sum_{n=0}^{\infty} a_{n} x^{n} = \sum_{n=0}^{\infty} \left[ \frac{1}{3} (n+1)(n+2)(n+3) - \frac{5}{2} (n+1)(n+2) + 4 (n+1) \right] x^{n} \end{align} which yields \begin{align} a_{n} &= \frac{1}{3} (n+1)(n+2)(n+3) - \frac{5}{2} (n+1)(n+2) + 4 (n+1) \\ &= \frac{n+1}{6} \left( 2(n+2)(n+3) - 15(n+2) + 24 \right) \\ &= \frac{n+1}{6} ( 2n^{2} - 5n + 6) \\ &= \frac{1}{6} ( 2 n^{3} - 3n^{2} + n + 6) \\ &= \frac{n(n-1)(2n-1)}{6} + 1. \end{align}