\problemdata                                                             
        {Factorial Powers} % latex-friendly label for the prob.
        {Summations - proving closed form} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Tutorial 6, 5} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
We shall define the falling factorial powers as follows:
\begin{eqnarray*}
x^{\underline{m}} = x(x-1) \cdot \cdot \cdot (x - m + 1)  \quad \text{(for integer $m \geq 0$)}
\end{eqnarray*}

Prove that

$$\sum_{0 \le k < n} (k^{\underline{m}}) = \frac{n^{\underline{m+1}}}{m+1} \quad \text{(for integers $m,n \ge 0$)}$$
%=======
%$\sum_{0 \le k < n} (k^{\underline{m}}) = \frac{n^{\underline{m+1}}}{m+1} \quad$ \text{(for integers $m,n \ge 0$)}


\solution{
 \textbf{Solution:}
The crucial step is to rewrite $x^{\underline{m}}$ as $\frac{(x+1)^{\underline{m+1}} - x^{\underline{m+1}}}{m+1}$.

To see why this is:

$\begin{array}{lll}
(x+1)^{\underline{m+1}} - x^{\underline{m+1}} & =& (x+1)(x)(x-1) \cdot \cdot \cdot (x+1-(m+1)+1) - (x)(x-1)(x-2) \cdot \cdot \cdot (x-(m+1)+1) \\
& =& (x+1)(x)(x-1) \cdot \cdot \cdot (x-m+1) - (x)(x-1)(x-2) \cdot \cdot \cdot (x-m) \\
& =& (x+1-(x-m))(x)(x-1)(x-2)....(x-m+1) \\
& =& (x+1-(x-m)) x^{\underline{m}} \\
& =& (m+1) x^{\underline{m}} \\
\end{array}$

\begin{eqnarray*}
x^{\underline{m}}  &=& \frac{(x+1)^{\underline{m+1}} - x^{\underline{m+1}}}{m+1}\\
\end{eqnarray*}

Now that we have established this relationship, we can use it to find the 
summation.
$\begin{array}{lll}
\sum_{0 \le k < n}(k^{\underline{m}}) & =& \sum_{0 \le k < n} (\frac{(k+1)^{\underline{m+1}} - k^{\underline{m+1}}}{m+1})\\
& =&  \frac{1}{m+1} (1^{\underline{m+1}} - 0^{\underline{m+1}}) + (2^{\underline{m+1}} - 1^{\underline{m+1}}) + (3^{\underline{m+1}} - 2^{\underline{m+1}}) + \cdot \cdot \cdot\\
& +&  ((n-1)^{\underline{m+1}} - (n-2)^{\underline{m+1}}) + (n^{\underline{m+1}} - (n-1)^{\underline{m+1}}) \\
& = &  \frac{1}{m+1} (n^{\underline{m+1}} - 0^{\underline{m+1}}) \\
& = &\frac{n^{\underline{m+1}}}{m+1} \\
\end{array}$
}

\end{problem}
                                 