<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] If you don't have to use induction, you can do this:
1)
$$
\sum_k k\binom{n}{k} = \sum_k k \frac{n(n-1)\cdots(n-k+1)}{k!} = n\sum_k \binom{n-1}{k-1} = n \sum_k \binom{n-1}{k} = n2^{n-1}
$$
Here $k$ runs over all integers and by convention $\binom{n}{k}$ is defined as zero if $k<0$ or $k > n$. The last equality follows from the fact that $\binom{n-1}{k}$ counts the $k$-element subsets of $\{1,\ldots,n-1\}$, so $\sum_k \binom{n-1}{k}$ counts the number of all subsets which is $2^{n-1}$.
2) Note that $\frac{1}{k(k+1)} = \frac{1}{k}-\frac{1}{k+1}$ so the sum is a telescope sum:
$$\sum_{k=1}^{n-1} \frac{1}{k(k+1)} = \sum_{k=1}^{n-1}\left( \frac{1}{k} - \frac{1}{k+1}\right) = 1 - \frac{1}{n}$$
</s>