Generating functions - deriving a formula for the sum $1^2 + 2^2 +\cdots+n^2$ I would like some help with deriving a formula for the sum $1^2 + 2^2 +\cdots+n^2$ using generating functions. 
I have managed to do this for $1^2 + 2^2 + 3^2 +\cdots$ by putting
$$f_0(x) = \frac{1}{1-x} = 1 + x + x^2 + x^3 +\cdots$$
$$f_1(x) = x \frac{d}{dx}[f_0(x)] = \frac{1}{(1-x)^2} = 0 + x + 2x^2 + 3x^3 +\cdots$$
$$f_2(x) = x \frac{d}{dx}[f_1(x)] = \frac{x^2+x}{(1-x)^3} = 0^2 + 1^2x + 2^2x^3 + 3^2x^3+\cdots,$$
and I assume I'm supposed to be able to do something similar in this case, but things get trickier when it's bounded by n and I keep getting stuck.
 A: Brute force:
$$f(x) \triangleq \sum_{r=0}^{n+1}x^r=\frac{x^{n+2}-1}{x-1} $$
$$f'(x) = \sum_{r=0}^{n+1}rx^{r-1} = \sum_{r=0}^{n}(r+1)x^r$$
$$f''(x) =  \sum_{r=0}^{n}r(r+1)x^{r-1} \therefore xf''(x)=\sum_{r=0}^{n}r(r+1)x^{r} = \sum_{r=0}^n\left(r^2+r\right)x^r$$
$$f'(x)-(f(x)-x^{n+1}) = \sum_{r=0}^{n}rx^r$$
So $$\sum_{r=1}^nr^2x^r =xf''(x) - (f'(x)-(f(x) - x^{n+1}))$$
Finally take the limit as $x \to 1$, which might get ugly, and Bob's your uncle.
[edit]
Changed $$\sum_{r=1}^nr^2x^r =f''(x) - (f'(x)-(f(x) - x^{n+1}))$$ to $$\sum_{r=1}^nr^2x^r =xf''(x) - (f'(x)-(f(x) - x^{n+1}))$$
A: Hint: The following perspective with focus on operator methods might also be useful.

We can successively apply the $\left(x\frac{d}{dx}\right)$-operator to a generating function
\begin{align*}
  A(x)=\sum_{n=0}^{\infty}a_nx^n
  \end{align*}
to obtain
\begin{align*}
  \left(x\frac{d}{dx}\right)A(x)&=\sum_{n=0}^{\infty}na_nx^n\\
  \left(x\frac{d}{dx}\right)^2A(x)&=\sum_{n=0}^{\infty}n^2a_nx^n
  \end{align*}

Multiplication of $A(x)$ with $\frac{1}{1-x}$ results in summing up the coefficients $a_n$
\begin{array}{crl}
  (a_n)_{n\geq 0}\qquad &\qquad A(x)=&\sum_{n=0}^{\infty}a_nx^n\\
  \left(\sum_{k=0}^{n}a_k\right)_{n\geq 0}\qquad&\qquad\frac{1}{1-x}A(x)=&\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}a_k\right)x^n
  \end{array}
It's also convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ in a generating series.

Putting all together and applying it to the geometric series $\frac{1}{1-x}=\sum_{n=0}^{\infty}x^n$ we finally obtain
\begin{align*}
  \sum_{k=0}^nk^2&=[x^n]\frac{1}{1-x}\left(x\frac{d}{dx}\right)^2\frac{1}{1-x}\\
  &=[x^n]\frac{x(1+x)}{(1-x)^4}\\
  &=\left([x^{n-1}+x^{n-2}]\right)\sum_{k=0}^{\infty}\binom{-4}{n}(-x)^n\tag{1}\\
  &=\left([x^{n-1}+x^{n-2}]\right)\sum_{k=0}^{\infty}\binom{n+3}{3}x^n\tag{2}\\
  &=\binom{n+2}{3}+\binom{n+1}{3}\\
  &=\frac{1}{6}n(n+1)(2n+1)
  \end{align*}

Comment:


*

*In (1) we use the binomial series expansion and $[x^n]x^kA(x)=[x^{n-k}]A(x)$

*In (2) we use $\binom{-n}{k}=\binom{n+k-1}{k}(-1)^k=\binom{n+k-1}{n-1}(-1)^k$
A: Given a generating function $f(x)$ for $a_n$, the generating function for $\sum_{i=0}^n a_i$ is $\sum_{n\geq 0} (\sum_{i=0}^n a_i)x^n = (\sum_{n\geq 0} x^n)(\sum_{n\geq 0} a_nx^n) = \frac{1}{1-x} f(x)$.
In this case, we have $f(x) = \frac{x(1+x)}{(1-x)^3}$ as you mention, so the desired generating function is $\frac{x(1+x)}{(1-x)^4}$.  This has a partial fraction expansion:
$$\frac{x(1+x)}{(1-x)^4} = \frac{1}{(1-x)^2} - \frac{3}{(1-x)^3} + \frac{2}{(1-x)^4}$$
Since $1/(1-x)^{k+1}$ is the generating function for ${n+k}\choose{k}$ (we can see this by repeatedly differentiating $\frac{1}{1-x}$), this gives us:
$$1^2+2^2+\cdots+n^2 = {{n+1}\choose 1} - 3{{n+2}\choose 2} + 2{{n+3}\choose 3} = \frac{n(n+1)(2n+1)}{6}$$

By the way, we can avoid all this work with a good choice of basis.  Since $n^2 = {n \choose 0} - 3{{n+1}\choose 1} + 2{{n+2}\choose 2}$, we have:
$$\sum_{i=0}^n i^2 = \sum_{i=0}^n \left({i \choose 0} - 3{{i+1}\choose 1} + 2{{i+2}\choose 2}\right) = {{n+1}\choose 1} - 3{{n+2}\choose 2} + 2{{n+3}\choose 3}$$
All we need here is the sum $\sum_{i=0}^n {{i+k}\choose k} = {{n+k+1}\choose {k+1}}$, which follows from the simple generating functions identity $\frac{1}{(1-x)^k}\cdot \frac{1}{1-x} = \frac{1}{(1-x)^{k+1}}$.
A: To answer otherwise, you can use the known fact that the sum of the first $n$ positive odd numbers is equal to $n^2$. So you have
$$\begin{cases}1=1^2\\1+3=2^2\\1+3+5=3^2\\1+3+5+7=4^2\\................\\1+3+5+…….+(2n-1)=n^2 \end{cases}$$  Therefore
 $$\sum_{i=1}^{i=n}n^2=n+(n-1)3+(n-2)5+(n-3)7+………+2(2n-3)+(2n-1)$$  That is to say
$$\sum_{i=1}^{n}n^2=\sum_{k=0}^{n-1}(n-k)(2k+1)=\frac{n(n+1)(2n+1)}{6}$$
NOTE.- Quite different story is the sequence of the corresponding inverse squares; one has the Euler’s formula  $$\sum_{n=1}^{\infty}\frac{1}{n^2}=\frac{(\pi)^2}{6}$$
