# Induction on a sum

The left hand side has terms involving $\binom{n}{m}= \dfrac{n!}{(n-m)!m!}$

$$1+\dfrac{1}{2}\binom{n}{1} +\frac{1}{3}\binom{n}{2}+...........+\frac{1}{n+1}\binom{n}{n} = \dfrac{2^{n+1}-1}{n+1}$$

I've done induction and proved $P(0)$ holds and also $P(1),P(2)$ holds (Just in case)

Now I've found $P(K+1)$ so the sum on the left is going to equal $\dfrac{2^{n+1}-1}{n+1}$ + $\dfrac{1}{n+2}$

and the right hand side is going to equal $\dfrac{2^{n+2}-1}{n+2}$

My problem is coming with the algebra though. I can't get those sides to equal. I can't get rid of the $n+1$ in the denominator.

Anyone have any ideas for me? They'd be much appreciated!

P.S. Someone gave me a hint and said that you can use the binomial theorem to solve this.

• Not exactly. Note than when you go from $N$ to $N+1$, it is not just about adding one term in the LHS, almost every term gets affected. – Macavity Sep 24 '13 at 13:57

Recall that $$(1+x)^n = \sum_{k=0}^n \dbinom{n}k x^k$$ Integrating this from $0$ to $1$, gives us $$\left. \dfrac{(1+x)^{n+1}}{n+1} \right \vert_{0}^1 = \sum_{k=0}^n \dbinom{n}k \left. \dfrac{x^{k+1}}{k+1} \right \vert_0^1$$ Hence, we get what you want.
Hint: you could note that $$(n+1)\cdot \frac{1}{m+1}\binom{n}{m} = \dfrac{(n+1)!}{(n-m)!(m+1)!} = \binom{n+1}{m+1}$$
Hence you can rewrite $P(n)$ equivalently as $$\sum_{0\le m\le n} \binom{n+1}{m+1} = 2^{n+1}- 1$$
or equivalently, $\displaystyle \sum_{m = 0}^n \binom{n}{m} = 2^n$ by a change of index.