# Evaluate and prove by induction: $\sum k{n\choose k},\sum \frac{1}{k(k+1)}$

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

2. $\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?

-
Hi. Do you have to use induction or you can use other methods because there are easier ways to prove both results. –  Kolmo Mar 23 '12 at 16:29

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

-

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.

-

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

-

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

-
Liked the fast solution. I was tempted to use that but I used a different procedure, which uses the same result you do. \ –  Pedro Tamaroff Mar 23 '12 at 16:54

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

-

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

-