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