Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
  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?

share|improve this question
    
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
add comment

6 Answers

up vote 4 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.