# Identity to simplify sum with binomial coefficient

This is the homework, and it shouldn't be difficult, but I can't find the proper identity that would help me simplify the below:

$\displaystyle \sum_{n=0}^m \frac{1}{n+1}\binom{m}{n}$.

Through calculating the results, I can see that the simplified version is:

$\displaystyle \frac{2^m-1}{m+1}$

But I don't know how to transform the former into the later. You need not give the complete solution (although, that's welcomed too), but the identities needed for the simplification should suffice.

EDIT:

How I counted: $\frac{m!}{(n+1)!(m-n)!}$ repeated $m$ times while $n$ increases from 0 to $m$. You can also see the code here: http://pastebin.com/RJ9jd966

-
Maybe (4) in en.wikipedia.org/wiki/Binomial_coefficient – GEdgar May 26 '12 at 17:09
This is almost identical to this question: How can I compute $\sum\limits_{k = 1}^n \frac{1} {k + 1}\binom{n}{k}$? (The only difference is that in the other question one term are omitted.) – Martin Sleziak May 26 '12 at 21:20
@MartinSleziak That question explicitly didn't allow answers involving calculus, meaning that my answer wouldn't be valid there while it is here. So I'd say they are not the same questions (but I wouldn't be very sad if we still decide they're the same). – Egbert May 26 '12 at 21:29
Sorry, finding a question by the title "how can I compute" wouldn't be easy... but if questions need to be merged - I don't mind. – wvxvw May 26 '12 at 22:43

Hints:

• For every $0\leqslant n\leqslant m$, $\displaystyle\frac1{n+1}{m\choose n}=\frac1{m+1}{m+1\choose n+1}$.
• $\displaystyle\sum\limits_{n=0}^m{m+1\choose n+1}=2^{m+1}-1$.

Note: Hence the result is not $\dfrac{2^m-1}{m+1}$ but a slight modification.

-
Nice that we give completely different hints :) – Egbert May 26 '12 at 17:21
I've counted and it's not even an integer, the result that is... pastebin.com/RJ9jd966 here's how I counted. And these are the results for m 1..5: 3/2, 7/3, 15/4, 31/5, 63/6. – wvxvw May 26 '12 at 17:24
@Egbert: Indeed. :-) – Did May 26 '12 at 17:28
Regardless, can you tell where does the first identity come from? I'm afraid I'll have to prove it myself - it doesn't look familiar :( – wvxvw May 26 '12 at 17:29
@wvxvw Simulations are not needed, just follow the hints in my answer. – Did May 26 '12 at 17:29

Hint. Consider the function $$\sum_{n=0}^m\frac{1}{n+1}{m\choose n} x^{n+1}.\tag{1}$$ Differentiating it gives you something very familiar.

Since you've already accepted an answer, I'll work out my answer so that you can see another approach. Differentiating the above polynomial gives $$\sum_{n=0}^m{m\choose n}x^n$$ which may be recognized as a special case of Newton's binomial series: it is equal to $(x+1)^m$. The primitive of this polynomial is $p(x)=\frac{1}{m+1}(x+1)^{m+1}+c$, where we have to choose the constant such that $p$ agrees with (1). One way to do this, is by looking at the value at $0$. $$p(0)=\frac{1}{m+1}+c$$ while the function in (1) gives $0$ at $0$. This means that we must choose $c=-\frac{1}{m+1}$. So we obtain $$\sum_{n=0}^m\frac{1}{n+1}{m\choose n} x^{n+1}=\frac{(x+1)^{m+1}}{m+1}-\frac{1}{m+1}$$ evaluating the latter term at $1$ gives the answer: $$\frac{2^{m+1}-1}{m+1}.$$

-
+1.    – Did May 26 '12 at 17:51
I was at first trying to follow this one, but I got confused when I saw that what is made into $x^n$ is a harmonic number, and that no simple way to count it / relate to power of x. (We didn't study it yet, so that was my research on wiki...) I would need to read more on the binomial series to understand what's been done later - but thank you for the explanation. – wvxvw May 26 '12 at 22:20
Newton's binomial formula is simply that $(a+b)^n=\sum_{i=0}^n{n\choose i}a^ib^{n-i}$. You don't need harmonic numbers to see that. (Don't tell it any further: I'm a logician, I also don't know what harmonic numbers are :D) – Egbert May 26 '12 at 22:27
Well, my problem with this explanation that I don't know many components :( I don't know what is primitive of the polynomial, and wouldn't know how to differentiate a sum of polynomials - to be honest, I don't even know where to search for this, the textbook glossary is unaware of it. – wvxvw May 26 '12 at 22:46
Ah, sorry, I now realized that you meant to differentiate the polynomial and then sum, and I can follow from after you have the $p(x)$ function, but I've no idea how $p(x)$ function is constructed. Is it antideriviate of..? where did $1/(m+1)$ come from? Sorry, I probably had to take more time to think it over. – wvxvw May 26 '12 at 23:21