# 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

## 2 Answers

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.

• I understand what you did to manipulate the Left side, but how does that equal the right side? Or we're you just showing that's the proper step of induction that I did wrong. – Fmonkey2001 Sep 24 '13 at 14:24
• @JerryWillette I do not understand your question. I took the binomial theorem and integrated both sides to get what you wanted. – user17762 Sep 24 '13 at 15:05

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.

Now this must be familiar to you from the binomial theorem as the expression for the sum of binomial coefficients. Prove it by induction if you have to...