Generating functions $a_{n} =n^{2}$

Question

Derive a generating function for the sequence $a_n = n^2$

I know the power series for $n^2$ is $${x(x+1)}\over{(1-x)^3}$$ However I am struggling to connect the two with the proof. Any help would be greatly appreciated thanks!

Answer 1

The trick to this problem is to see it in terms of generating functions that you already know. Take $1/(1-x)^3=(1+x+x^2+...)^3$. The coefficient of $x^n$ in this generating function is the number of compositions of $n$ into $3$ parts, or $\binom{n+2}{2}=(n+2)(n+1)/2=(n^2+3n+2)/2$. This is useful to us, as there is an $n^2$ term in there. The denominator of $2$ there is kind of confusing, so let's just multiply by $2$ to get rid of it, giving us the generating function $2/(1-x)^3$ with coefficients $n^2+3n+2$ for $x^n$.

Our next step is to eliminate $3n$ (as you will see, this changes the constant term, which we will eliminate next). Now we want a generating function with linear coefficients, so we'll try $1/(1-x)^2$. Similar to the first one we used, this counts compositions of $n$ into two parts, so the coefficient of $x^n$ is $\binom{n+1}{1}=n+1$. However, we wanted to eliminate $3n$, so we multiply this generating function by $-3$ to get $-3/(1-x)^2$, so our coefficient of $x^n$ is now $n^2+3n+2-3n-3=n^2-1$. And so, our final step is to add back $1$ to get $n^2$, so we use the generating function with coefficient $1$ for each term, which I'm sure you know is $1/(1-x)$. By taking the sum of these generating functions, you'll get your desired answer.