Prove $ \sum_{1\leq k < n} k^{\underline{m}}=\frac{n^{\underline{m+1}}}{m+1} $ by induction on $m$ I want to prove by induction the following sum:
$$ \sum_{1\leq k < n} k^{\underline{m}}=\frac{n^{\underline{m+1}}}{m+1} $$
but induction should be on $m$. Any hint will be helpful.
EDIT: $ k^{\underline{m}}= k (k-1) \cdots (k-m+1)$
 A: The finite difference operator $\Delta$ on sequences $f: \mathbb{N} \to \mathbb{R}$ is defined by $\Delta(f)(n) = f(n+1) - f(n)$. This operator has inverse given by the "definite-sum" operator $\Sigma$, taking a sequence $g$ to the sequence $\Sigma(g)(n) := \sum_{k = 0}^{n-1} g(k)$. We have that $\Delta \circ \Sigma$ is the identity operator, and the fact that $\Sigma\circ \Delta$ acts as the identity on functions $f$ with $f(0) = 0$ is essentially the method of telescoping sums. 
Let $\binom{x}{k} = \frac{x^{\underline k}}{k!}$ be the $k^{th}$ binomial coefficient polynomial. Then the Pascal triangle identity says that as a function of $n$ we have 
$$\Delta \binom{n}{k} = \binom{n+1}{k} - \binom{n}{k} = \binom{n}{k-1}$$ 
or if you like $\Delta \frac{x^{\underline k}}{k!} = \frac{x^{\underline{k-1}}}{(k-1)!}$, or 
$$\Delta \frac{x^{\underline{m+1}}}{m+1} = x^{\underline m}$$  
after a change of variable. This leads to 
$$\frac{n^{\underline{m+1}}}{m+1} = \Sigma (x^{\underline m})|_{x=n} = \sum_{k=0}^{n-1} k^{\underline m}$$ 
as claimed. 
But if you really want to see $\Delta x^{\underline{m+1}} = (m+1)x^{\underline m}$ by an induction on $m$, I would write 
$$x^{\underline{m+1}} = x^{\underline m}(x-m)$$ 
and then apply the product rule $\Delta(f g)(n) = \Delta(f)(n) g(n+1) + f(n)\Delta(g)(n)$, together with induction on $m$. 
A: Note that there is a very simple algebraic proof. The left is
$$[z^{(n-1)-m}] \frac{1}{1-z} 
\left(\frac{d}{dz}\right)^m \frac{1}{1-z}.$$
The right is
$$\frac{1}{m+1} [z^{n-(m+1)}] \left(\frac{d}{dz}\right)^{m+1}  \frac{1}{1-z}.$$
Now observe that
$$ \left(\frac{d}{dz}\right)^m \frac{1}{1-z}
= m! \frac{1}{(1-z)^{m+1}}$$
which you may prove by induction if desired.
This gives for the left side,
$$[z^{(n-1)-m}] \frac{1}{1-z} m! \frac{1}{(1-z)^{m+1}} =
[z^{n-1-m}] m! \frac{1}{(1-z)^{m+2}},$$
and for the right side
$$ \frac{1}{m+1} [z^{n-(m+1)}] (m+1)!  \frac{1}{(1-z)^{m+2}}
= [z^{n-1-m}] m! \frac{1}{(1-z)^{m+2}}.$$
The two are the same, QED.
We have used the fact that the generating function of the sum of the first $n$ terms of a sequence is obtained from the generating function of that sequence through multiplication by $1/(1-z).$
