13
$\begingroup$

Proof that $\suṃ̣_{k=1}^{n}k {n \choose k}$ for $n \in \mathbb N$ is equal to $n2^{n-1}$.

As a hint I got that $k {n \choose k} = n {n-1\choose k-1} $.

I tried solving this by induction but, in the inductive step I'm not arriving to the correct result.

$\endgroup$
  • 1
    $\begingroup$ Factor out the $n$ using given identity and adjust the remaining sum so that you can use the known sum of binomial coefficients. $\endgroup$ – Marcin Łoś Feb 20 '14 at 17:05
14
$\begingroup$

Just change the index $s=k-1$

$$\sum_{k=1}^{n}k {n \choose k} = n\sum_{k=1}^{n} {n-1\choose k-1}= n\sum_{s=0}^{n-1} {n-1\choose s} =n2^{n-1}$$

$\endgroup$
5
$\begingroup$

One possible proof:

Because $$(1+x)^n = \sum_{k=0}^n {n \choose k} x^k,$$ then by taking derivative, $$n(1+x)^{n-1} = \sum_{k=1}^n k{n \choose k} x^{k-1}. $$ Let $x=1$, we obtain that $$n2^{n-1} = \sum_{k=1}^n k {n \choose k}.$$

$\endgroup$
5
$\begingroup$

\begin{align*} &A = \sum_{k\geq1}^{n}k\cdot \binom{n}{k} \\ \end{align*}

$A $ is the no of ways to form a committee of $k \geq 1$ people out of $n$ available individuals and select one head for the selected committee.

Empty committee is not possible. Therefore we select the head first in $n$ ways and then any subset out of $(n-1)$ remaining people in $2^{n-1} $ ways.

\begin{align*} &A =n\cdot2^{n-1} \\ \end{align*}

$\endgroup$
4
$\begingroup$

Another way to do this is to differentiate the identity $$(1 + x)^n = \sum_{k=0}^n \binom{n}{k}x^k $$ and then put $x = 1$.

$\endgroup$

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.