Zugdichte2r

2022-01-24

Find the value of $\sum _{k=1}^{n}k\left(\begin{array}{c}n\\ k\end{array}\right)$?

Damian Roberts

From the binomial theorem, we have
${\left(1+x\right)}^{n}=\sum _{k=0}^{n}\left(\begin{array}{c}n\\ k\end{array}\right){x}^{k}$ (1)
Differentiating (1) reveals
$n{\left(1+x\right)}^{n-1}=\sum _{k=0}^{n}\left(\begin{array}{c}n\\ k\end{array}\right)k{x}^{k-1}$ (2)
Setting $x=1$ in (2) yields
$n{2}^{n-1}=\sum _{k=0}^{n}\left(\begin{array}{c}n\\ k\end{array}\right)k$
And we are done!

Deegan Mullen

We have
$\sum _{k=0}^{n}k\left(\begin{array}{c}n\\ k\end{array}\right)=\sum _{k=1}^{n}k\left(\begin{array}{c}n\\ k\end{array}\right)$
$n=\sum _{k=1}^{n}\frac{\left(n-1\right)!}{\left(k-1\right)!\left(n-k\right)!}$
$n\sum _{l=0}^{n-1}\frac{\left(n-1\right)!}{l\left(\left(n-1\right)-l\right)!}$
$=n\sum _{l=0}^{n-1}\left(\begin{array}{c}n-1\\ l\end{array}\right)$
$=n{2}^{n-1}$

RizerMix

Proof without derivatives: $\sum _{k=1}^{n}k\left(\left(n\right),\left(k\right)\right)=\sum _{k=1}^{n}k\frac{n!}{\left(n-k\right)!k!}$ $=\sum _{k=1}^{n}\frac{n!}{\left(n-k\right)!\left(k-1\right)!}$ $=\sum _{k=1}^{n}\frac{n\left(n-1\right)!}{\left(n-k\right)!\left(k-1\right)!}$ $=\sum _{k=1}^{n}n\left(\left(n-1\right),\left(k-1\right)\right)$ $=n\sum _{k=0}^{n-1}\left(\left(n-1\right),\left(k\right)\right)=n{2}^{n-1}$ Alternate proof via probability theory: Toss a fair coin n times, find the expected no of heads. Let N be the random variable denoting the number of heads. Then $E\left[N\right]=n/2$ because N is the sum of n bernoulli random variables with probability 1/2. But we also know that N has a binomial distribution. Hence $E\left[N\right]=\sum _{k=1}^{n}k\left(\left(n\right),\left(k\right)\right){2}^{-n}$ Rearrange to get your answer.