<s>[INST] Evaluate and prove by induction: $\sum k{n\choose k},\sum \frac{1}{k(k+1)}$ 
*

*$\displaystyle
  0\cdot \binom{n}{0} + 1\cdot \binom{n}{1} + 2\binom{n}{2}+\cdots+(n-1)\cdot \binom{n}{n-1}+n\cdot \binom{n}{n}$

*$\displaystyle\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3}+\frac{1}{3\cdot 4} +\cdots+\frac{1}{(n-1)\cdot n}$
How do you find the sum of these and prove it by induction? Can someone help me get through this?
 [/INST] One way to do this:
1) You are looking for $\sum_{k=0}^n k\binom{n}{k}$.
First, look at $f(x)=(1+x)^n=\sum_{k=0}^n \binom{n}{k}x^k$, (by Newton's binomial theorem). Hence $2^n=\sum_{k=0}^n \binom{n}{k}$, by calculating $f(1)$. Now, define $g(x)=\sum_{k=0}^n k\binom{n}{k}x^k$. What you need is $g(1)$. Try expressing $g(x)$ through $f(x)$. (Hint: what is $g'(x)$?)
2) Notice that $\frac{1}{(k-1)k}=\frac{1}{k-1}-\frac{1}{k}$. Hence:
$\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3}+\frac{1}{3\cdot 4} +\cdots+\frac{1}{(n-1)\cdot n}=\left(\frac{1}{1}-\frac{1}{2}\right)+\left(\frac{1}{2}-\frac{1}{3}\right)+\cdots+\left(\frac{1}{n-1}-\frac{1}{n}\right)$
</s>