Showing that $\sum_{k=0}^{n}{m+k\choose m}^{-1}=\frac{m}{m-1}\left[1-{m+n\choose m-1}^{-1}\right],m>1.$

Question

Let $$S_{m,n}=\sum_{k=0}^{n}{m+k\choose m}^{-1}$$ Then $S_{0,n}=n+1, S_{1,n}=H_{n+1}.$

For $m>1$, let us consider the integral $$I_{m,k}=\int_{0}^{1} (1-x^{1/m})^k dx$$ which by using $x=\sin^{2m} t$ and Beta function, can be expressed as $$I_{m,k}=2m\int_{0}^{\frac{\pi}{2}}\sin^{2m-1} t ~ \cos^{2k+1} t~ dt= \frac{\Gamma(m+1) \Gamma(k+1)}{\Gamma(m+k+1)}={m+k\choose m}^{-1}.$$ Next, we can write $$S_{m,n}=\sum_{k=0}^{n} I_{m,k}=\int_{0}^{1}dx \sum_{k=0}^n (1-x^{1/m})^k=\int_{0}^{1} x^{-1/m}[1-(1-x^{1/m})^{n+1}]~ dx.$$ $$\implies S_{m,n}=\frac{m}{m-1}-\int_0^1 x^{-1/m}(1-x^{1/m})^{n+1} dx$$

Again by using $x=\sin^{2m} t$ and Beta-integral, we get $$S_{m.n}=\frac{m}{m-1}-2m\int_{0}^{\frac{\pi}{2}} \sin^{2m-3}~\cos^{2n+3} ~dt=\frac{m}{m-1}-\frac{\Gamma(m)\Gamma(n+2)}{\Gamma(m+m+1)}. $$ Upon simplification we have $$S_{m,n}=\frac{m}{m-1}\left[1-{m+n\choose m-1}^{-1}\right],m>1.$$

The question us how else this result can be obtained?

Answer 1

$$S_{m,n}(x)=\sum_{k=0}^{n}{m+k\choose m}^{-1} x^k=\Gamma(m+1)\sum_{k=0}^{n}\frac{ \Gamma (k+1)}{\Gamma (k+m+1)}x^k$$

$$S_{m,n}(x)=\, _2F_1(1,1;m+1;x)-\frac{\Gamma (m+1)\Gamma (n+2) }{\Gamma (m+n+2)} x^{n+1}\, _2F_1(1,n+2;m+n+2;x) $$

For $m \geq 2$ $$\, _2F_1(1,1;m+1;1)=\frac m{m-1}$$

Enjoy the simplification of

$$\frac{\Gamma (m+1)\Gamma (n+2) }{\Gamma (m+n+2)} \, _2F_1(1,n+2;m+n+2;1) $$

Answer 2

We seek to show that for $m\gt 1$

$$S_{m,n} = \sum_{k=0}^n {m+k\choose m}^{-1} = \frac{m}{m-1} \left[1-{m+n\choose m-1}^{-1}\right].$$

We have for the LHS using an Iverson bracket:

$$[w^n] \frac{1}{1-w} \sum_{k\ge 0} {m+k\choose m}^{-1} w^k.$$

Recall from MSE 4316307 that with $1\le k\le n$

$${n\choose k}^{-1} = k [z^n] \log\frac{1}{1-z} (z-1)^{n-k}.$$

We get with $m\ge 1$ as per requirement on $k$

$$m \; \underset{z}{\mathrm{res}} \; \frac{1}{z^{m+1}} \log\frac{1}{1-z} [w^n] \frac{1}{1-w} \sum_{k\ge 0} w^k z^{-k} (z-1)^k \\ = m \; \underset{z}{\mathrm{res}} \; \frac{1}{z^{m+1}} \log\frac{1}{1-z} [w^n] \frac{1}{1-w} \frac{1}{1-w(z-1)/z} \\ = m \; \underset{z}{\mathrm{res}} \; \frac{1}{z^{m}} \log\frac{1}{1-z} \; \underset{w}{\mathrm{res}} \; \frac{1}{w^{n+1}} \frac{1}{1-w} \frac{1}{z-w(z-1)}.$$

Now residues sum to zero and the residue at infinity in $w$ is zero by inspection, so we may evaluate by taking minus the residue at $w=1$ and minus the residue at $w=z/(z-1).$ For $w=1$ start by writing

$$- m \; \underset{z}{\mathrm{res}} \; \frac{1}{z^{m}} \log\frac{1}{1-z} \; \underset{w}{\mathrm{res}} \; \frac{1}{w^{n+1}} \frac{1}{w-1} \frac{1}{z-w(z-1)}.$$

The residue then leaves

$$- m \; \underset{z}{\mathrm{res}} \; \frac{1}{z^{m}} \log\frac{1}{1-z} = -m \frac{1}{m-1}.$$

On flipping the sign we get $m/(m-1)$ which is the first term so we are on the right track. Note that when $m=1$ this term will produce zero. For the residue at $w=z/(1-z)$ we write

$$- m \; \underset{z}{\mathrm{res}} \; \frac{1}{z^{m}} \frac{1}{z-1} \log\frac{1}{1-z} \; \underset{w}{\mathrm{res}} \; \frac{1}{w^{n+1}} \frac{1}{1-w} \frac{1}{w-z/(z-1)}.$$

Doing the evaluation of the residue yields

$$- m \; \underset{z}{\mathrm{res}} \; \frac{1}{z^{m}} \frac{1}{z-1} \log\frac{1}{1-z} \frac{(z-1)^{n+1}}{z^{n+1}} \frac{1}{1-z/(z-1)} \\ = m \; \underset{z}{\mathrm{res}} \; \frac{1}{z^{m+n+1}} \log\frac{1}{1-z} (z-1)^{n+1} \\ = m [z^{m+n}] \log\frac{1}{1-z} (z-1)^{n+1}.$$

Using the cited formula a second time we put $n := m+n$ and $k := m-1$ to get

$$m \frac{1}{m-1} {m+n\choose m-1}^{-1}.$$

On flipping the sign we get the second term as required and we have the claim.

Remark. In the above we have $m\gt 1.$ We get for $m=1$

$$[z^{n+1}] \log\frac{1}{1-z} (z-1)^{n+1} = \; \underset{z}{\mathrm{res}} \; \frac{1}{z^{n+2}} \log\frac{1}{1-z} (z-1)^{n+1}.$$

Now we put $z/(z-1) = v$ so that $z = v/(v-1)$ and $dz = -1/(v-1)^2 \; dv$ to get

$$- \; \underset{v}{\mathrm{res}} \; \frac{1}{v^{n+2}} \log\frac{1}{1-v/(v-1)} (v-1) \frac{1}{(1-v)^2} \\ = \; \underset{v}{\mathrm{res}} \; \frac{1}{v^{n+2}} \frac{1}{1-v} \log(1-v).$$

On flipping the sign we obtain

$$\; \underset{v}{\mathrm{res}} \; \frac{1}{v^{n+2}} \frac{1}{1-v} \log\frac{1}{1-v} = H_{n+1},$$

again as claimed. This particular value follows by inspection, of course.

Answer 3

Choose $x_1, x_2, \dots, x_{m+n}$ uniformly at random from $[0,1]$. Let $A_k$ be the event that in the set $\{x_1, x_2, \dots, x_{m+k}\}$, the subset $\{x_m, \dots, x_{m+k-1}\}$ has the $k$ highest values, but the subset $\{x_m, \dots, x_{m+k}\}$ does not have the $k+1$ highest values.

(We consider $k=0, 1, \dots, n+1$; $A_0$ only checks the second condition, since the first is vacuous, and $A_{n+1}$ only checks the first condition, since the second is vacuous.)

Then the probability of $A_k$ is exactly $\binom{m+k}{m}^{-1} \cdot \frac{m-1}{m}$ for all $k \le n$, while the probability of $A_{n+1}$ is just $\binom{m+n}{n-1}^{-1}$. So the statement we want to show is equivalent to $$ \sum_{k=0}^n \frac{m}{m-1}\Pr[A_k] = \frac{m}{m-1}(1 - \Pr[A_{n+1}]) \iff \sum_{k=0}^{n+1} \Pr[A_k] = 1. $$ To prove this, we show that exactly one of the events must happen:

• If $A_k$ happens, then one of the elements $x_1, \dots, x_{m-1}$ beats $x_{m+k}$, which prevents $\{x_m,\dots, x_{m+k'-1}\}$ from being the highest in $\{x_1, \dots, x_{m+k'}\}$ for any $k'>k$; then no $A_{k'}$ after $A_k$ can happen.
• Suppose $A_0$ does not happen; then $x_m$ is highest among $\{x_1, \dots, x_m\}$. Choose the first $k$ such that $x_{m+k}$ is less than $\max\{x_1, \dots, x_{m-1}\}$; then $A_k$ happens. Or, if there is no such $k$, then $A_{n+1}$ happens.