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?
 A: The answer from lhf has already dealt with the second question posed here.  Here is a Wikipedia article about it.
Here's a probabilistic approach to the first question.  When you toss a coin $n$ times, the probability that a "head" appears exactly $k$ times is $\dbinom n k (1/2)^n$.  The average number of times a "head" appears is therefore
$$
\left( \binom n 0 \cdot 0 + \binom n 1 \cdot 1 + \binom n 2 \cdot 2 + \cdots + \binom n k \cdot k + \cdots + \binom n n \cdot n \right) \left(\frac 1 2 \right)^n.
$$
But the average number of times a "head" appears is obviously $n/2$.  Therefore
$$
\left( \binom n 0 \cdot 0 + \binom n 1 \cdot 1 + \binom n 2 \cdot 2 + \cdots + \binom n k \cdot k + \cdots + \binom n n \cdot n \right) \left(\frac 1 2 \right)^n = \frac n 2.
$$
Consequently
$$
\binom n 0 \cdot 0 + \binom n 1 \cdot 1 + \binom n 2 \cdot 2 + \cdots + \binom n k \cdot k + \cdots + \binom n n \cdot n = n 2^{n-1} .
$$
A: 1) Take $\displaystyle f(x)= \sum_{i=0}^n\binom{n}{i} x^i=(x+1)^n$. Now consider $f'(1)$.
2) Use that $\frac{1}{(k-1)\cdot k} = \frac{1}{k-1} -\frac{1}{k}$.
A: 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}$$
A: For the first one, you're asked to find
$$\sum\limits_{k=0}^n k{n \choose k}$$
Since the binomial coefficients have the $n-k$ symmetry, we can put
$$\sum\limits_{k=0}^n (n-k){n \choose n-k}$$
thus
$$S_n = \sum\limits_{k=0}^n k{n \choose k}=\sum\limits_{k=0}^n (n-k){n \choose n-k}$$
But the RHS is
$$n\sum\limits_{k=0}^n {n \choose n-k}-\sum\limits_{k=0}^n k{n \choose n-k}$$
Now
$$S_n=n\sum\limits_{k=0}^n {n \choose k}-\sum\limits_{k=0}^n k{n \choose k}$$
or
$$S_n=n\sum\limits_{k=0}^n {n \choose k}-S_n$$
$$S_n=n2^n-S_n$$
$$2 S_n=n2^n $$
$$S_n=n2^{n-1} $$
The second one becomes easy once you make use of the telescoping property you've been suggested already.
A: Some different ways to prove $\sum_k k\binom{n}{k} = n2^{n-1}$ were suggested. I'll add a combinatorial proof by double counting. Consider pairs $(a,A)$ were $A$ is a subset of $\{1,\ldots,n\}$ and $a \in A$. The number of such pairs is $\sum_k k\binom{n}{k}$ since there are $\binom{n}{k}$ ways to choose a $k$-element subset $A$ and then $k$ possibilities to choose $a \in A$. On the other hand, you can first choose $a \in \{1,\ldots,n\}$ and then add any subset of the remaining $n-1$ elements to make $A$, so this gives $n2^{n-1}$ possibilities. Comparing the two results shows that $\sum_k k\binom{n}{k} = n2^{n-1}$.
A: 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)$
A: 1)
$$S_n=\sum_{k=0}^nk\frac{n!}{k!(n-k)!}=n\sum_{k=1}^n\frac{(n-1)!}{(k-1)!(n-k)!}=n\sum_{k=0}^{n-1}\binom{n-1}k=n2^{n-1}.$$
Then the inductive proof by $S_0=0,S_n-S_{n-1}=T_n$, is a little tedious:
$$S_n-S_{n-1}
=\sum_{k=0}^nk\binom nk-\sum_{k=0}^{n-1}k\binom {n-1}k=n\binom nn+\sum_{k=0}^{n-1}k\left(\binom nk-\binom{n-1}k\right)\\
=n+\sum_{k=1}^{n-1}k\binom{n-1}{k-1}
=n+\sum_{k=1}^{n-1}(k-1)\binom{n-1}{k-1}+\sum_{k=1}^{n-1}\binom{n-1}{k-1}\\
=n+\sum_{k=1}^{n-1}(k-1)\binom{n-1}{k-1}+\sum_{k=1}^{n-1}\binom{n-1}{k-1}\\
=n+\sum_{k=0}^{n-2}k\binom{n-1}k+\sum_{k=0}^{n-2}\binom{n-1}{k}\\
=n+S_{n-1}-(n-1)+2^{n-1}-1=S_{n-1}+2^{n-1}.$$
And on the other hand
$$T_n=S_n-S_{n-1}=n2^{n-1}-(n-1)2^{n-2}=(n-1)2^{n-2}+2^{n-1}$$
2)
As $\dfrac1{k(k+1)}=\dfrac1k-\dfrac1{k+1}$, the sum telescopes as
$$S_n=\frac1{n+1}-1.$$
This time, the proof by induction is trivial:
$$S_0=0,$$
$$T_n=S_n-S_{n-1}=\frac1{n+1}-1-\frac1n+1=\frac1{n(n+1)}.$$
