Friday, 7 February 2014

combinatorics - Proof by induction, binomial coefficient




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



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


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...