How to show that $\sum_{i=1}^n i^2$ is a polynomial in $n$? How can I show that the following expression:
$$\sum_{i=1}^n i^2$$
Is a polynomial in $n$?
I approached this problem as follows:
$$i^2=(n-(n-i))^2$$
$$\therefore \sum_{i=1}^n i^2=\sum_{i=1}^n (n-(n-i))^2$$
$$=-n^3+\sum_{i=1}^n 2in +\sum_{i=1}^n (n-i)^2$$
And at first I thought this is a polynomial in itself; however, later I realized how this might be quite redundant considering how if I were to expand the other summation signs, that will just cancel out all the terms and leave me with $\sum_{i=1}^n i^2$.
 A: If you know some linear algebra, you can do the following. Let $P_k$ be the set of all polynomials of degree at most $k$. Because these are determined by $k+1$ coefficients, $P_k$ is a $k+1$-dimensional vector space.
Let $\Delta:P_k\to P_{k-1}$ by the map that sends the polynomial $f(x)$ to the polynomial $f(x)-f(x-1)$. (Check that this makes sense by showing that $\Delta f$ is always has lower degree than $f$.) Show that the kernel $\ker\Delta$ (the set of things that $\Delta$ sends to zero) is the set of constant functions. Thus, $\ker\Delta$ is a one-dimensional vector space.
We want to show that $\Delta$ is surjective, meaning that $\operatorname{im}\Delta$ (the image of $\Delta$) equals $P_{k-1}$.
The rank-nullity theorem states that
$$\dim(\operatorname{im}\Delta)+\dim(\ker\Delta)=\dim P_k$$
Thus, $\dim(\operatorname{im}\Delta)+1=k-1$, so $\dim(\operatorname{im}\Delta)=k-2=\dim P_{k-1}$. Thus, $\Delta$ is surjective.
Letting $k=3$, this means $\Delta:P_3\to P_2$ is surjective, so there is some polynomial $f$ such that $\Delta f=x^2$, or $f(x)-f(x-1)=x^2$. Finally,
$$\sum_{i=1}^n i^2=\sum_{i=1}^n f(i)-f(i-1)=f(n)-f(0)$$
is a polynomial.

(So far, this is just an existence proof. For bonus points, show how we can find $f$ by inverting the matrix $\begin{bmatrix}3&0&0\\3&2&0\\1&1&1\end{bmatrix}$.)
A: In the context of the calculus problem, it is useful to note that
$$
\lim_{n \rightarrow \infty} \frac{\sum_{i=1}^{n} i^2}{n^3}= \lim_{n \rightarrow \infty} \frac{1}{n} \sum_{i=1}^{n} \left(\frac{i}{n} \right)^2 = \int_0^1 n^2 \mathrm{d} n = \frac{1}{3}
$$
by Riemann sums: in particular, each term in the sum calculates the $i$th rectangle with width $\frac{1}{n}$ and height $\frac{i}{n}^2$, or an approximation of the area under the curve $n^2$ between $x = \frac{i}{n}$ and $x = \frac{i+1}{n}$.
To find the exact value of the sum, we can use repeated applications of the hockey stick identity:
$$
\sum_{i=1}^{n} i^2 = \sum_{i=1}^{n} \left(2\binom{i}{2} + \binom{i}{1}\right) = 2\binom{n+1}{3} + \binom{n+1}{2} = \frac{n(n+1)(2n+1)}{6}.
$$
A: The method demonstrated is
\begin{align}
S_{n} &= \sum_{j=0}^{n} j^2 = \sum_{j=0}^{n} (n - (n-j))^2 \\
&= \sum_{j=0}^{n} ( n^2 - 2 \, n \, (n-j) + (n-j)^2 ) \\
&= n^2 \, \sum_{j=0}^{n} (1) - 2 \, n \, \sum_{j}^{n} (n-j) + \sum_{j=0}^{n} (n-j)^2 \\
&= n^2 \, (n+1) - 2 \, n \, \sum_{j=0}^{n} j + \sum_{j=0}^{n} j^2 \\
&= n^2 \, (n+1) - 2 \, n \, \sum_{j=0}^{n} j + S_{n} \\
0 &= n \, (n+1) - 2 \, \sum_{j=0}^{n} j \\
\sum_{j=0}^{n} j &= \binom{n+1}{2}.
\end{align}
One method to show the desried value is to use
$$ \sum_{j=0}^{n} t^j = \frac{1 - t^{n+1}}{1-t} $$
and use the operator $t \frac{d}{dt}$ twice on both sides to obtain
$$ \sum_{j=0}^{n} j^2 \, t^j = \frac{t + t^2 - (n+1)^2 \, t^{n+1} + (2 n^2 + 2 n -1) \, t^{n+2} - n^2 \, t^{n+3}}{(1 - t)^3}. $$
Now, but using L'Hospital's rule three times, while $t \to 1$, leads to
$$ \sum_{j=0}^{n} j^2 = \frac{n \, (n+1) \, (2 n + 1)}{6}. $$
A: Here we use elementary techniques and a little trick to prove the assertion. We start with the presentation of a somewhat larger task, namely the calculation of
\begin{align*}
\color{blue}{S_m(n)=\sum_{k=0}^{n-1}k^m\qquad\qquad m\geq 0}
\end{align*}
$m=0$:
\begin{align*}
S_0(n)=\sum_{k=0}^{n-1}1=n\tag{1}
\end{align*}
$m=1$:
\begin{align*}
2S_1(n)&=2\sum_{k=0}^{n-1}k=\sum_{k=1}^{n-1}\left(k+(n-k)\right)=n(n-1)\\
S_1(n)&=\frac{1}{2}n(n-1)\tag{2}
\end{align*}
$m=2$:

We use a cute trick and start with $S_3(n)$ instead of $S_2(n)$. We obtain
\begin{align*}
\color{blue}{S_3(n)+n^3}&=\sum_{k=1}^n k^3=\sum_{k=0}^{n-1}(k+1)^3\\
&=\sum_{k=0}^{n-1}\left(k^3+3k^2+3k+1\right)\\
&\,\,\color{blue}{=S_3(n)+3S_2(n)+3S_1(n)+S_0(n)}\tag{3}
\end{align*}
We observe $S_3(n)$ cancels and we get from (1), (2) and (3):
\begin{align*}
\color{blue}{S_2(n)}&=\frac{1}{3}\left(n^3-3S_1(n)-S_0(n)\right)\\
&=\frac{1}{3}\left(n^3-\frac{3}{2}n(n-1)-n\right)\\
&\,\,\color{blue}{=\frac{1}{6}n(n-1)(2n-1)}
\end{align*}
and the claim follows.

Note: This derivation comes from the script Konkrete Analysis (2004) by J. Cigler.
