2
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ One can use the Pascal Identity $\binom{p+1}{k}=\binom{p}{k}+\binom{p}{k-1}$. $\endgroup$ – André Nicolas Jan 24 '15 at 2:51
  • $\begingroup$ Oh right!That works $\endgroup$ – user137720 Jan 24 '15 at 3:01
  • 1
    $\begingroup$ The suggestion was for an induction proof. There are better non-induction proofs. $\endgroup$ – André Nicolas Jan 24 '15 at 3:06
  • $\begingroup$ Differentiate $(1+x)^{n}$ and then replace $x$ by $1$ to find sum of coefficients. $\endgroup$ – AvZ Jan 24 '15 at 5:11
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I like this proof, but it does not answer the question of the OP: to complete the induction. $\endgroup$ – awllower Jan 24 '15 at 3:08
  • 1
    $\begingroup$ Yeah I know that, But as for the induction proof @André Nicolas has answered it perfectly. $\endgroup$ – Vim Jan 24 '15 at 3:12
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

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