Lesson 3

First, find the generating function of the sequence \(s=(0,1,4,9,16,\dotsc)\) (\(s_{n}=n^{2}\)). Start with the already known generating function of the sequence \((1,2,3,4,\dotsc)\): \[(1,2,3,4,\dotsc)=\frac{1}{(1-x)^2}\ .\] Multiply by \(x\) to shift one position to the right: \[(0,1,2,3,\dotsc)=\frac{x}{(1-x)^2}\ .\] Differentiate to multiply the \(n\)-th coefficient by \(n\) and shift left: \[(1,4,9,16,\dotsc)=\frac{d}{dx}\frac{x}{(1-x)^2}=\frac{1+x}{(1-x)^3}\ .\] Multiply by \(x\) to shift one position to the right: \[(0,1,4,9,\dotsc)=\frac{x(1+x)}{(1-x)^3}\ .\] Multiply by \((1,1,1,\dotsc)=\frac{1}{1-x}\) to get the partial sums: \[(0,1,5,14,\dotsc)=\frac{x(1+x)}{(1-x)^4}\ .\] Finally, use the formula \[\frac{1}{(1-x)^k}=\sum_{n=0}^{\infty}\binom{n+k-1}{n}x^{n},\] to find the coefficient we need: \[\begin{align*}[x^{n}]\frac{x(1+x)}{(1-x)^4}&=[x^{n}]\frac{x}{(1-x)^4}+[x^{n}]\frac{x^2}{(1-x)^4}=\\&=[x^{n-1}]\frac{1}{(1-x)^4}+[x^{n-2}]\frac{1}{(1-x)^4}=\\&=\binom{n+2}{n-1}+\binom{n+1}{n-2}=\\&=\frac{(n+2)(n+1)n}{6}+\frac{(n+1)n(n-1)}{6}=\\&=\frac{n(n+1)(2n+1)}{6}\ .\end{align*}\]