Proof by induction, binomial coefficient

Question

I have to make the following proof: $${\sum\limits_{k=1}^n}{k}{n\choose k} = n2^{n-1}$$

Base case, $n = 1$:

$${\sum\limits_{k=1}^{1}}{k}{1\choose k} = 1 = 1\cdot2^0=1$$ Inductive Hypothesis:

for int $p = n$ $${\sum\limits_{k=1}^p}{k}{p\choose k} = p2^{p-1}$$

Inductive Step; here is where I am having some trouble.... Can I get any hints to where I can take this? $${\sum\limits_{k=1}^{p+1}}{k}{{p+1}\choose k} = p2^{p}$$ Expansion:

$${{p+1}\choose 1} + \cdots + {p}{{p+1}\choose p} + (p+1){{p+1}\choose {p+1}} $$

Answer 1

Hint: $$(1+x)^n=1+C_{n}^{1}x+C_{n}^{2}x^2+\cdots+C_{n}^{n-1}x^{n-1}+x^n$$ Differentiate both sides in terms of $x$ $$n(1+x)^{n-1}=C_{n}^{1}+2C_{n}^{2}x+3C_{n}^{3}x^2+\cdots+(n-1)C_{n}^{n-1}x^{n-2}+nx^{n-1}$$ And let $x=1$.

Answer 2

Another non-inductive proof:

If $s =\sum\limits_{k=1}^p{k}{p\choose k} $, then $s =\sum\limits_{k=0}^p{k}{p\choose k} =\sum\limits_{k=0}^p(p-k){p\choose p-k} =\sum\limits_{k=0}^p(p-k){p\choose k} $ so $2s =\sum\limits_{k=0}^p{k}{p\choose k} +\sum\limits_{k=0}^p(p-k){p\choose k} =\sum\limits_{k=0}^p(k+(p-k)){p\choose k} =\sum\limits_{k=0}^p p{p\choose k} =p\sum\limits_{k=0}^p {p\choose k} =p2^p $.

Answer 3

Basic non-inductive proof:

For $k\ge1,$ $$k\cdot\binom nk=k\cdot\frac{n!}{n!\cdot k!}=k\cdot\frac{n\cdot(n-1)!}{\{(n-1)-(k-1)\}!\cdot k\cdot(k-1)!}=n\binom{n-1}{k-1}$$

$$\implies S=\sum_{k=1}^nk\binom nk=\sum_{k=1}^nn\binom{n-1}{k-1}$$

Set $k-1=r$ $$\implies S=n\sum_{r=0}^{n-1}\binom{n-1}r=n(1+1)^{n-1}$$