Problem source

Let $S_k(n) \equiv \sum\limits_{r=0}^n r^k\,$, where $k$ is a positive integer, so that
\[
S_1(n) \equiv  \tfrac12 n(n+1)
\text{  and  }
S_2(n) \equiv \tfrac16 n(n+1)(2n+1)\,.
\]
\begin{questionparts}
\item
By considering $\sum\limits_{r=0}^n \left[ (r+1)^k-r^k\right]\, $,
show that 
\[
kS_{k-1}(n)=(n+1)^k -(n+1) -  
\binom{k}{2} S_{k-2}(n) 
- \binom {k}{3} S_{k-3}(n) - \cdots
- \binom{k}{k-1} S_{1}(n)
\;.
\tag{$*$}
\] 
Obtain simplified expressions for $S_3(n)$ and $S_4(n)$.
\item
Explain, using $(*)$, why $S_k(n)$ is a polynomial of degree $k+1$ in $n$.   Show that in this polynomial the constant term is zero and  the sum of the coefficients is 1.
\end{questionparts}

Solution source

\begin{questionparts}
\item \begin{align*}
&&(n+1)^k &= \sum_{r=0}^n \left [ (r+1)^k - r^k \right] \\
&&&= \sum_{r=0}^n \left [ \left ( \binom{k}{0}r^k+\binom{k}1r^{k-1} + \binom{k}{2}r^{k-2} + \cdots + \binom{k}{k} 1  \right)  - r^k\right] \\
&&&= \sum_{r=0}^n  \left ( \binom{k}1r^{k-1} + \binom{k}{2}r^{k-2} + \cdots + \binom{k}{k} 1  \right)  \\ 
&&&=k \sum_{r=0}^n  r^{k-1} + \binom{k}{2}\sum_{r=0}^nr^{k-2} + \cdots + \binom{k}{k} \sum_{r=0}^n 1   \\
&&&= kS_{k-1}(n) + \binom{k}2 S_{k-2}(n) + \cdots +\binom{k}{k-1}S_1(n) + (n+1) \\
\Rightarrow && k S_{k-1}(n) &= (n+1)^k -(n+1) -\binom{k}2 S_{k-2}(n) - \cdots -\binom{k}{k-1}S_1(n)   \\
&& 4S_3(n) &= (n+1)^4-(n+1) - \binom{4}{2} \frac{n(n+1)(2n+1)}{6} - \binom{4}{3} \frac{n(n+1)}{2} \\
&&&= (n+1) \left ( (n+1)^3-1 - n(2n+1)-2n \right) \\
&&&= (n+1) \left ( n^3+3n^2+3n+1-1 - 2n^2-3n \right) \\
&&&= (n+1) \left ( n^3+n^2 \right) \\
&&&= n^2(n+1)^2 \\
\Rightarrow && S_3(n) &= \frac{n^2(n+1)^2}{4} \\
\\
&&5S_4(n) &=(n+1)^5-(n+1) - \binom{5}{2} \frac{n^2(n+1)^2}4 - \binom{5}{3} \frac{n(n+1)(2n+1)}{6} - \binom{5}{4} \frac{n(n+1)}{2} \\
&&&=  (n+1) \left ((n+1)^4 - 1-\frac{5n^2(n+1)}{2} - \frac{5n(2n+1)}{3} -\frac{5n}{2}\right)\\
&&&= \frac{n+1}{6} \left (6(n+1)^4-6-15n^2(n+1)-10n(2n+1)-15n \right)  \\
&&&= \frac{n+1}{6} \left (6n^4+24n^3+36n^2+24n+6 -6-15n^3-15n^2-20n^2-10n-15n\right) \\
&&&= \frac{n+1}{6} \left (6n^4+9n^3+n^2-n\right) \\
&&&= \frac{(n+1)n(2n+1)(3n^2+3n-1)}{6} \\
\Rightarrow && S_4(n) &= \frac{(n+1)n(2n+1)(3n^2+3n-1)}{30}
\end{align*}

\item Proceeding by induction, since $S_k(n)$ is a polynomial of degree $k+1$ for small $k$, we can see that 
\[ (k+1)S_k(n) = \underbrace{(n+1)^{k+1}}_{\text{poly deg }=k+1} - \underbrace{(n+1)}_{\text{poly deg}=1} - \underbrace{\binom{k+1}{2}S_{k-1}(n)}_{\text{poly deg}=k} - \underbrace{\cdots}_{\text{polys deg}< k} - \underbrace{\binom{k+1}{k} S_1(n)}_{\text{poly deg}=1}\]
therefore $S_k(n)$ is a polynomial of degree $k+1$ (in fact with leading coefficient $\frac{1}{k+1}$. Since $S_k(0) = \sum_{r=0}^{0} r^k = 0$ there is no constant term, and since $S_k(1) = \sum_{r=0}^1 r^k = 1$ the sum of the coefficients is $1$
\end{questionparts}