4
$\begingroup$

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

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

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

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

  • 0
    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.2012-05-26

2 Answers 2

6

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.

  • 0
    Oh, I see now, I've misread it. silly me.2012-05-26
7

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

  • 0
    The polynomial $p(x)$ is indeed the anti-derivative (or primitive, it means the same) of the polynomial $(x+1)^m$. You can see that it's indeed an anti-derivative by computing it's derivative.2012-05-27