\problemdata      
        {summations-4} % latex-friendly label for the prob.
        {Summations} % The topic(s) of the problem content.
        {?} % Source (if known)
        {S02 PS6; S01, PS5} % Usage (list ones you are aware of).
        {Christos Kapoutsis, S02} % Last revision info (author, date).


\begin{problem}
\bparts

\ppart
Find a closed form solution for $\sum_{i=1}^n i^2x^i$.

\solution{
From Course Notes~6 we know that
\[
\sum_{i=1}^n ix^i = 
\frac{x - (n+1)x^{n+1} + nx^{n+2}}{(1-x)^2}.
\]
Differentiating (with respect to $x$) the two sides of the equation we have
\begin{equation*}
\sum_{i=1}^n i^2x^{i-1}  =
\frac{1+x-(n+1)^2x^{n}+(2n^2+2n-1)x^{n+1}-n^2x^{n+2}}{(1-x)^3}.
\end{equation*}
Then multiplying by $x$
\begin{equation*}
\sum_{i=1}^n i^2x^i  =
\frac{x+x^2-(n+1)^2x^{n+1}+(2n^2+2n-1)x^{n+2}-n^2x^{n+3}}{(1-x)^3},
\end{equation*}
which is the closed form we were after.
}

\ppart Find a closed form formula for $\sum_{i=1}^n i^3$.
\solution{
One way to do this is by guessing that the solution is of the form
$a_4 n^4+a_3n^3+\cdots +a_1n+a_0$, then evaluating the sum at
$n=0,1,\dots,4$, then solving the resulting system of linear
equations for $a_4,a_3,\dots,a_0$, and finally checking by
induction that the resulting formula is correct. 

Here is another way: Start by noting that 
$$
k^4 - (k-1)^4 = 4k^3 - 6k^2 + 4k -1,
$$
and hence 
$$
k^3 = \tfrac{1}{4} \bigl( k^4 - (k-1)^4 + 6k^2 - 4k + 1 \bigr),
$$
for all $k\geq 1$. Summing both sides of this latter equation from~1
upto~n, we get 
\begin{align}
\nonumber
\sum_{k=1}^n k^3 
&= \sum_{k=1}^n \Bigl[
	\tfrac{1}{4} \bigl( k^4 - (k-1)^4 + 6k^2 - 4k + 1 \bigr)
   \Bigr]
\\ \label{eq:tocalc}
&= \tfrac{1}{4} \Bigl[ 
	\sum_{k=1}^n \bigl( k^4 - (k-1)^4 \bigr) + 
	6\sum_{k=1}^n k^2 - 
	4\sum_{k=1}^n k + 
	\sum_{k=1}^n 1 
   \Bigr].
\end{align}
Using the known facts
$$
\sum_{k=1}^n 1   = n, \qquad
\sum_{k=1}^n k   = \tfrac{1}{2}n(n+1), \qquad
\sum_{k=1}^n k^2 = \tfrac{1}{6}n(n+1)(2n+1),
$$
and the easy observation that the first of the right hand side sums
\emph{telescopes}, 
\begin{align*}
\sum_{k=1}^n \bigl( k^4 - (k-1)^4 \bigr)   
&= \sum_{k=1}^n k^4 - \sum_{k=1}^n (k-1)^4  \\
&= \sum_{k=1}^n k^4 - \sum_{k=0}^{n-1} k^4  \\
&= n^4 - 0^4                                \\
&= n^4,
\end{align*}
we conclude that Equation~\eqref{eq:tocalc} can be written as 
\begin{align*}
\sum_{k=1}^n k^3 
&= \tfrac{1}{4} [ n^4 + n(n+1)(2n+1) - 2n(n+1) + n ] \\
&= \tfrac{1}{4} [ n^4 + 2n^3 + n^2 ] \\
&= \tfrac{1}{4} n^2 [ n^2 + 2n + 1 ] \\
&= \tfrac{1}{4} n^2 (n + 1)^2 \\
&= \Bigl( \tfrac{ n(n + 1) }{2} \Bigr)^2.
\end{align*}
Note that this implies 
$\sum_{k=1}^n k^3 = \bigl( \sum_{k=1}^n k \bigr)^2$. Also note 
the standard general technique which we have applied here: To find a
closed form for $\sum_{k=1}^n k^a$, first express this sum in terms of 
\begin{itemize}
\item a telescoping sum of powers $a+1$ (which will always evaluate to
$n^{a+1}$), and
\item sums of smaller powers (which will always evaluate to
known closed forms);
\end{itemize}
then do the algebra to find the closed form you are after.
}
\eparts
\end{problem}

