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
    Maybe (4) in http://en.wikipedia.org/wiki/Binomial_coefficient2012-05-26
  • 3
    This is almost identical to this question: [How can I compute $\sum\limits_{k = 1}^n \frac{1} {k + 1}\binom{n}{k}$?](http://math.stackexchange.com/questions/66118/how-can-i-compute-sum-limits-k-1n-frac1-k-1-binomnk) (The only difference is that in the other question one term are omitted.)2012-05-26
  • 0
    @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).2012-05-26
  • 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
    Nice that we give completely different hints :)2012-05-26
  • 0
    I've counted and it's not even an integer, the result that is... http://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.2012-05-26
  • 0
    @Egbert: Indeed. :-)2012-05-26
  • 0
    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 :(2012-05-26
  • 0
    @wvxvw Simulations are not needed, just follow the hints in my answer.2012-05-26
  • 0
    The first identity is direct, using the expression of every binomial coefficient as a ratio of factorials.2012-05-26
  • 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
    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.2012-05-26
  • 0
    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)2012-05-26
  • 0
    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.2012-05-26
  • 0
    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.2012-05-26
  • 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