Let $n \in \mathbb{Z}^+$, prove the identity $ \sum_{k=1}^{n-1} \binom {n} {k} \frac{kn^{n-k}}{k+1}=\frac{n(n^{n}-1)}{n+1}$

Question

Let $n \in \mathbb{Z}^+$, prove the identity $$ \sum_{k=1}^{n-1} \binom {n} {k} \frac{kn^{n-k}}{k+1}=\frac{n(n^{n}-1)}{n+1}$$

First of all $$ \sum_{k=1}^{n-1} \binom {n} {k} \frac{kn^{n-k}}{k+1}=n^{n}\Bigg(\sum_{k=1}^{n-1} \binom {n} {k} \frac{kn^{-k}}{k+1} \Bigg)$$ $$=n^n\Bigg(\sum_{k=1}^{n-1} \binom {n}{k} \bigg(1-\frac{1}{k+1}\bigg)\bigg(\frac{1}{n^k}\bigg)\Bigg)$$ $$=n^n \sum_{k=1}^{n-1} \binom {n} {k} \frac{1}{n^k}-n^n \sum_{k=1}^{n-1} \binom {n}{k} \bigg( \frac{1}{k+1}\bigg)\bigg(\frac{1}{n^k} \bigg)$$

We have for the first sum $$(1+\frac{1}{x})^n = \sum_{k=0}^n \binom{n}{k}\frac{1}{x^k}.$$ For the second sum $$(1+x)^n = \sum_{k=0}^n \binom{n}{k}x^k.$$

Integrating both sides from $0$ to $x$, we see that

$$\frac{(1+x)^{n+1}-1}{n+1} = \sum_{k=0}^n \binom{n}{k}\frac{x^{k+1}}{k+1}.$$

Putting $x=1$ yields $$\frac{2^{n+1}-1}{n+1}=\sum_{k=0}^n \binom{n}{k}\frac{1}{k+1}$$

Here where I have stopped. I could not get them similar for what I have. Would someone help me out !

Answer 1

Suppose we seek to show that

$$\sum_{k=1}^{n-1} {n\choose k} \frac{k n^{n-k}}{k+1} = \frac{n(n^n-1)}{n+1}.$$

Multiply by $n+1$ to get

$$\sum_{k=1}^{n-1} {n+1\choose k+1} k n^{n-k} = n(n^n-1).$$

Extend to $k=n$ to obtain

$$\sum_{k=1}^{n} {n+1\choose k+1} k n^{n-k} = n^{n+1}.$$

In order to prove this we introduce

$$n^{n-k} = \frac{(n-k)!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-k+1}} \exp(nz) \; dz.$$

This yields

$$\frac{1}{(n-k)!} n^{n-k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-k+1}} \exp(nz) \; dz.$$

or

$${n+1\choose k+1} n^{n-k} = \frac{(n+1)!}{(k+1)!} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-k+1}} \exp(nz) \; dz.$$

Observe that this vanishes when $k\gt n$ so we may extend the sum to infinity, getting

$$\frac{(n+1)!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp(nz) \sum_{k\ge 1} \frac{k}{(k+1)!} z^k \; dz.$$

The sum term is

$$\sum_{k\ge 1} \frac{z^k}{k!} - \sum_{k\ge 1} \frac{z^k}{(k+1)!} = \exp(z) - 1 - \frac{1}{z} (\exp(z)-z-1) \\ = \exp(z) - \frac{1}{z} \exp(z) + \frac{1}{z}.$$

Extracting the coefficients we thus obtain

$$(n+1)! \left( \frac{(n+1)^n}{n!} - \frac{(n+1)^{n+1}}{(n+1)!} + \frac{n^{n+1}}{(n+1)!} \right) \\ = (n+1)^{n+1} - (n+1)^{n+1} + n^{n+1} = n^{n+1}.$$

This is the claim.

Answer 2

$$ \begin{align} \sum_{k=1}^n\binom{n}{k}\frac{kn^{n-k}}{k+1} &=n^n\sum_{k=1}^n\binom{n-1}{k-1}\frac1{k+1}\frac1{n^{k-1}}\\ &=n^n\int_0^1\sum_{k=1}^n\binom{n-1}{k-1}\frac{t^k}{n^{k-1}}\,\mathrm{d}t\\ &=n^n\int_0^1t\sum_{k=0}^{n-1}\binom{n-1}{k}\frac{t^k}{n^k}\,\mathrm{d}t\\ &=n^n\int_0^1t\,\left(1+\frac tn\right)^{n-1}\,\mathrm{d}t\\ &=n\int_0^1t\,(n+t)^{n-1}\,\mathrm{d}t\\ &=n\int_n^{n+1}(\color{#C00000}{t}-\color{#00A000}{n})\,t^{n-1}\,\mathrm{d}t\\ &=\color{#C00000}{\frac{n(n+1)^{n+1}-n^{n+2}}{n+1}}-\color{#00A000}{\left(n(n+1)^n-n^{n+1}\right)}\\ &=\frac{n^{n+1}}{n+1}\tag{1} \end{align} $$ Subtract the $k=n$ term from $(1)$ and we get $$ \sum_{k=1}^{n-1}\binom{n}{k}\frac{kn^{n-k}}{k+1}=\frac{n^{n+1}-n}{n+1}\tag{2} $$

Answer 3

There is a straightforward direct computational argument:

$$\begin{align*} \sum_{k=1}^{n-1}\binom{n}k\frac{kn^{n-k}}{k+1}&=\sum_{k=1}^{n-1}\binom{n}k\left(1-\frac{1}{k+1}\right)n^{n-k}\\ &=\sum_{k=1}^{n-1}\binom{n}kn^{n-k}-\sum_{k=1}^{n-1}\binom{n}k\frac{n^{n-k}}{k+1}\\ &=(n+1)^n-n^n-1-\frac{1}{n+1}\sum_{k=1}^{n-1}\binom{n+1}{k+1}n^{n-k}\\ &=(n+1)^n-n^n-1-\frac{1}{n+1}\sum_{k=2}^n\binom{n+1}kn^{n+1-k}\\ &=(n+1)^n-n^n-1-\frac{1}{n+1}\left((n+1)^{n+1}-n^{n+1}-(n+1)n^n-1\right)\\ &=-1+\frac{n^{n+1}+1}{n+1}\\ &=\frac{n(n^n-1)}{n+1} \end{align*}$$

Answer 4

Here's a direct proof (no integration, no induction, just the binomial theorem and algebra):

\begin{align}\sum_{k=1}^{n-1} \binom {n} {k} \frac{kn^{n-k}}{k+1}&=\sum_{k=1}^{n-1} \binom {n} {k} \big(1-\frac1{k+1}\big)n^{n-k} \\&=\sum_{k=1}^{n-1} \binom {n} {k} n^{n-k}-\sum_{k=1}^{n-1} \binom {n} {k} \frac1{k+1}n^{n-k} \\&=\Big(\sum_{k=0}^{n} \binom {n} {k} n^{n-k}\Big)-\binom{n}{0}n^{n-0}-\binom{n}{n}n^{n-n}-\sum_{k=1}^{n-1} \frac{n!}{k!\, (n-k)!} \frac1{k+1}n^{n-k} \\&=(1+n)^n-n^n-1-\sum_{k=1}^{n-1} \frac{n!}{(k+1)!\, (n-k)!} n^{n-k} \\&=(n+1)^n-n^n-1-\sum_{k=1}^{n-1} \frac{n!}{(k+1)!\, (n-k)!} n^{n-k} \\&=(n+1)^n-n^n-1-\sum_{k=1}^{n-1} \frac{(n+1)!/(n+1)}{(k+1)!\, (n-k)!} n^{n-k} \\&=(n+1)^n-n^n-1-\frac1{n+1}\sum_{k=1}^{n-1} \frac{(n+1)!}{(k+1)!\, ((n+1)-(k+1))!} n^{n-k} \\&=(n+1)^n-n^n-1-\frac1{n+1}\sum_{k=1}^{n-1} \binom{n+1}{k+1} n^{n-k} \\&=(n+1)^n-n^n-1-\frac1{n+1}\sum_{k=2}^{n} \binom{n+1}{k} n^{n-k+1} \\&=(n+1)^n-n^n-1-\frac1{n+1}\sum_{j=1}^{n-1} \binom{n+1}{n+1-j} n^j\scriptsize{\quad\text{(where }j=n-k+1)} \\&=(n+1)^n-n^n-1-\frac1{n+1}\sum_{j=1}^{n-1} \binom{n+1}{j} n^j \\&=(n+1)^n-n^n-1-\frac1{n+1}\left(-\binom{n+1}{0}n^0-\binom{n+1}{n}n^n-\binom{n+1}{n+1}n^{n+1}+\sum_{j=0}^{n+1} \binom{n+1}{j} n^j\right) \\&=(n+1)^n-n^n-1-\frac1{n+1}\Big(-1-(n+1)n^n-n^{n+1}+(n+1)^{n+1}\Big) \\&=(n+1)^n-n^n-1-\frac1{n+1}\Big(-1-n^{n+1}\Big)-\Big(-n^n+(n+1)^{n}\Big) \\&=\require{cancel}\cancel{(n+1)^n}-\bcancel{n^n}-1+\frac1{n+1}\Big(1+n^{n+1}\Big)+\bcancel{n^n}-\cancel{(n+1)^{n}} \\&=\frac{n^{n+1}+1}{n+1}-1 \\&=\frac{n(n^{n}-1)}{n+1}, \end{align}

as desired.

$$$$