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 !

  • $\begingroup$ You didn't finish plugging in $x=1$ at the end. $\endgroup$ – Simply Beautiful Art Oct 14 '16 at 22:49
  • $\begingroup$ You are right. I just I fixed it. However I am still missing $$\frac{1}{x^k}$$ $\endgroup$ – ADAM Oct 14 '16 at 22:54
  • $\begingroup$ Instead of plugging in $x=1$, plug in $x=1/n$. $\endgroup$ – Simply Beautiful Art Oct 14 '16 at 22:58

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*}$$

| cite | improve this answer | |
  • $\begingroup$ It took me too long to type my answer -- you beat me to it :) . $\endgroup$ – Mitchell Spector Oct 15 '16 at 0:34

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


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

| cite | improve this answer | |

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.


| cite | improve this answer | |
  • $\begingroup$ Thank you so much ! would you explain for me what happen from $$ (n+1)^n-n^n-1-\frac1{n+1}\sum_{k=1}^{n-1} \binom{n+1}{k+1} n^{n-k}$$ to $$(n+1)^n-n^n-1-\frac1{n+1}\sum_{k=2}^{n} \binom{n+1}{k} n^{n-k+1}$$ what I meant how the index and the limit of the summation work! Thank you ! $\endgroup$ – ADAM Oct 30 '16 at 17:51
  • 1
    $\begingroup$ Instead of letting $k$ run from $1$ to $n-1,$ we let $k$ run from $2$ to $n$ (one higher all the way through), but then we have to use $k-1$ instead of $k.$ So replace $k$ with $k-1$ in the terms being added. This doesn't change the value of the sum because you're literally adding the same numbers (we're just labelling them with numbers from $2$ to $n$ instead of with numbers from $1$ to $n-1,$ but the actual numbers being added are the same). $\endgroup$ – Mitchell Spector Oct 30 '16 at 18:45
  • $\begingroup$ I got it ! Thank you ! $\endgroup$ – ADAM Oct 30 '16 at 19:30
  • $\begingroup$ Sorry for asking but how $$\sum_{j=0}^{n+1} \binom{n+1}{j} n^j=(n+1)^{n+1}$$Thank you so much ! $\endgroup$ – ADAM Oct 30 '16 at 21:04
  • 1
    $\begingroup$ That's from the binomial theorem: $$(a+b)^k=\sum_{j=0}^{k}\binom{k}{j}a^jb^{k-j}.$$ Set $k$ equal to $n+1,$ set $a$ equal to $n,$ and set $b$ equal to $1.$ $\endgroup$ – Mitchell Spector Oct 30 '16 at 21:09

$$ \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} $$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.