4
$\begingroup$
  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?

$\endgroup$
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Where's the induction ? $\endgroup$ – Yves Daoust Nov 28 '16 at 10:40
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Liked the fast solution. I was tempted to use that but I used a different procedure, which uses the same result you do. \ $\endgroup$ – Pedro Tamaroff Mar 23 '12 at 16:54
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

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