Proving the generating function of $n^2$

Question

I've been given an assignment question that says this:

Show that the ordinary generating function for the sequence $\{a_n\}_{n\geq0}$ where $a_n = n^2$ is

$$g(t) = \frac{t(1+t)}{(1-t)^3}$$

I'm not sure how to start and was wondering if anyone could give me some suggestions as to where to begin. Many thanks for any help.

Answer 1

First note the identity $$ n^2=\binom{n+1}{2}+\binom{n}{2}\tag{1} $$ and recall the binomial theorem $$ (1+x)^{\alpha}=\sum_{n=0}^\infty \binom{\alpha}{n}x^n.\quad (\alpha\in\mathbb{C}) $$ which converges absolutely for $\lvert x\rvert <1$. In particular $$ (1-x)^{-3}=\sum_{n=0}^\infty \binom{-3}{n}(-x)^n =\sum_{n=0}^\infty \binom{n+2}{2} x^n\tag{2}. $$ The identity (1) together with (2) imply that $$ [x^n]\left(\frac{x(1+x)}{(1-x)^3}\right) =[x^n]\left(\frac{x}{(1-x)^3}\right)+[x^n]\left(\frac{x^2}{(1-x)^3}\right) =\binom{n+1}{2}+\binom{n}{2} =n^2. $$ where $[x^n]$ extracts the coefficient of $x^n$ in the generating function.

Answer 2

Start with $$\dfrac{1}{1-t} = \sum_{n=0}^\infty t^n$$ Differentiate term by term...

Answer 3

Suggestions you said?

Start with the generating function of the sequence $(1,1,1,\ldots)$, that is, the geometric series $$ \frac1{1-t}=1+t+t^2+\cdots=\sum_{n=0}^\infty t^n. $$ Differentiate term wise to get $$ \frac1{(1-t)^2}=\sum_{n=1}^\infty nt^{n-1}. $$ Multiply by $t$ to get the generating the function of $(0,1,2,3,\ldots)$ $$ \frac{t}{(1-t)^2}=\sum_{n=1}^\infty nt^n. $$ Repeat the last two steps to get what you need.

Answer 4

You can approach this from two ends, one is finding an expression for the ordinary generating series of $(n^2)_{n\in\Bbb N}$, and the other is to find the general term of the generating series with expression $\frac{t(1+t)}{(1-t)^3}$. I'll do the latter direction here. A third approach would be to translate the generating series expression into a recurrence relation with initial conditions on the coefficients of the series, and to show that $(n^2)_{n\in\Bbb N}$ satisfies both.

Given the generating series expression $\frac{t(1+t)}{(1-t)^3}$, it will clearly help to know the generating series for $\frac1{(1-t)^3}$, which is given by the binomial series with exponent $-3$, as $$ (1-t)^{-3}=\sum_{i\in\Bbb N}\binom{-3}i(-t)^i =\sum_{i\in\Bbb N}(-1)^i\binom{-3}it^i =\sum_{i\in\Bbb N}\binom{i+3-1}it^i =\sum_{i\in\Bbb N}\binom{i+2}2t^i. $$ This series has general coefficient $c_n=\binom{n+2}2=\frac{(n+1)(n+2)}2$. But you need to multiply it by the numerator $t(1+t)=t+t^2$, and multiplying the series by $t^k$ shifts the coefficients to the right $k$ places, so gives a series with coefficient $c_{n-k}$ at position$~n$ (with the convention that $c_i=0$ is $i<0$). Therefore the whole fraction has general term $\frac{n(n+1)}2+\frac{(n-1)n}2=\frac{((n-1)+(n+1))n}2=n^2$ as desired.