Prove $ \sum_{1\leq k < n} k^{\underline{m}}=\frac{n^{\underline{m+1}}}{m+1} $ by induction on $m$

Question

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)$

Answer 1

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$.

Answer 2

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).$