Proof that $\sum_{k=0}^m \binom{m}{k}\frac{1}{k+1} = \frac{2^{m+1}-1}{m+1}$ [duplicate]

Recently I needed to compute $E[\frac{1}{X+1}]$ where $X\sim Bin(m, \frac 1 2)$. While expanding, I came across the sum $\sum_{k=0}^m \binom{m}{k}\frac{1}{k+1}$, which I was unable to solve. Plugging into Mathematica gives $\frac{2^{m+1}-1}{m+1}$, but I don't see how to derive this result.

Can anyone give a proof of this identity or an alternate way to compute $E[\frac{1}{X+1}]$?

-

marked as duplicate by user17762, Amzoti, 23rd, Julian Kuelshammer, Dennis GulkoMay 12 '13 at 6:27

It’s easier if you multiply through by $m+1$:

$$(m+1)\sum_{k=0}^m\binom{m}k\frac1{k+1}=\sum_{k=0}^m\binom{m}k\frac{m+1}{k+1}=\sum_{k=0}^m\binom{m+1}{k+1}=\sum_{k=1}^{m+1}\binom{m+1}k=2^{m+1}-1\;.$$

-

A related problem. We start with the identity $$\sum_{k=0}^m \binom{m}{k}x^k = (1+x)^m.$$

Integrating both sides of the above equation with respect to $x$ form $0$ t0 $1$, the desired result follows

$$\sum_{k=0}^m \binom{m}{k}\frac{1}{k+1} = \int_{0}^{1}(1+x)^m dx = \frac{(1+x)^{m+1}}{m+1}\Big|_{x=0}^{x=1}=\frac{2^{m+1}-1}{m+1}.$$

-

HINT:

$$\binom mk \frac1{k+1}=\frac{m!}{(k+1)\cdot k! (m-k)!}=\frac1{m+1}\cdot \frac{(m+1)\cdot m!}{(k+1)!\{(m+1)-(k+1)\}!}=\frac1{m+1}\cdot \binom {m+1}{k+1}$$

So, $$\sum_{0\le k\le m}\frac1{k+1}\cdot \binom mk=\frac1{m+1}\cdot \sum_{0\le k\le m}\binom {m+1}{k+1}=\frac1{m+1}\cdot\sum_{1\le k\le m+1}\binom {m+1}k$$

Now, $$\sum_{1\le k\le n}\binom nk=(1+1)^n-1$$

-