15
$\begingroup$

Do you have any idea to prove the following identity via a combinatorial (or algebraic) method? $\sum_{n=r}^{n=\infty} {n \choose r}^{-1} = \frac{r}{r-1}$

This is Exercise 71 in Chapter 2 of the book Chen C.C., Koh K.M. Principles and techniques in combinatorics. The book does not give a solution, although it mentions: "see H. W. Gould, Combinatorial Identities, Morgantown, W.V. (1972), 18-19".

many thanks in advance, Shahram

$\endgroup$
12
  • 3
    $\begingroup$ have you spend one or two own thoughts on it? $\endgroup$ – tired Feb 1 '17 at 14:45
  • 5
    $\begingroup$ Maybe you can use the fact that $${n\choose k}^{-1}=(n+1)\int_0^1x^{n-k}(1-x)^k\mathrm dx$$ $\endgroup$ – polfosol Feb 1 '17 at 14:45
  • $\begingroup$ What is the source of the problem? What is $r$? $\endgroup$ – lab bhattacharjee Feb 1 '17 at 14:51
  • $\begingroup$ @labbhattacharjee : this is an exercice (of the second chapter) from the book "Principles and Techniques in Combinatorics". $\endgroup$ – Shahram Khazaie Feb 1 '17 at 14:55
  • 2
    $\begingroup$ This sum is also mentioned in the question: What are the properties of these two functions? Found using Approach0. $\endgroup$ – Martin Sleziak Feb 1 '17 at 15:41
13
$\begingroup$

This is basically a generalization of the approach from this answer: \begin{align*} \sum_{n=r}^\infty \frac1{\binom nr} &= r! \sum_{n=r}^\infty \frac1{n(n-1)\cdots(n-r+1)}\\ &= \frac{r!}{r-1} \sum_{n=r}^\infty \frac{n-(n-r+1)}{n(n-1)\cdots(n-r+1)}\\ &= \frac{r!}{r-1} \sum_{n=r}^\infty \left(\frac1{(n-1)\cdots(n-r+1)} - \frac1{n(n-1)\dots(n-r+2)}\right)\\ &\overset{(1)}= \frac{r!}{r-1} \cdot \frac1{(r-1)!} = \\ &= \frac{r}{r-1} \end{align*}

The equation $(1)$ is based on the fact that we get a telescoping sum and with the exception of the first term, all remaining terms "cancel out".

The above works only for $r\ne1$. But it is clear that for $r=1$ we get the harmonic series $\sum\limits_{n=1}^\infty \frac1n$, which is divergent.


To explain this more clearly, we have a sum of the form $$\sum_{r=n}^\infty (a_n-a_{n+1})= (a_r-a_{r+1})+ (a_{r+1}-a_{r+2})+\dots.$$ Since $a_n\to 0$, we get that the sum is simply $a_r$, since the partial sum is $$\sum_{r=n}^N (a_n-a_{n+1}) = (a_r-a_{r+1})+(a_{r+1}-a_{r+2})+\dots+(a_N-a_{N+1}) = a_r-a_{N+1}.$$ In our case $a_n=1/[(n-1)\cdots(n-r)]$.


After some rewriting, we can see that this is a sum which has been calculated on this site a few times, namely $\sum_{k=1}^\infty \frac1{k(k+1)\cdots(k+s)}$. In our case, $s=r-1$. (Clearly, when I was trying to search for it before posting my answer, I did not choose the correct search queries.) A few posts about this sum found using the above search in Approach0:

We can also find some posts about the finite sum, for example General formula for this sum $\sum_{k=1}^n\frac{1}{k(k+1)...(k+m)}$.

$\endgroup$
3
  • $\begingroup$ Damn it, i was so close $+1$ $\endgroup$ – tired Feb 1 '17 at 16:10
  • 1
    $\begingroup$ @MartinSleziak: Very nice! (+1) $\endgroup$ – Markus Scheuer Feb 1 '17 at 16:10
  • 1
    $\begingroup$ @MartinSleziak: thank you very much for your detailed answer. It's very kind of you. $\endgroup$ – Shahram Khazaie Feb 1 '17 at 16:55
6
$\begingroup$

$${n \choose r}^{-1}$$

$$=\frac{r!(n-r)!}{n!}$$

$$=\frac{r\Gamma(r) \Gamma (n-r+1)}{\Gamma (n+1)}$$

$$=rB(r,n-r+1)$$

$$=r \int_{0}^{1} x^{n-r} (1-x)^{r-1} dx$$

$$=r \int_{0}^{1} x^n x^{-r} (1-x)^{r-1} dx$$

Also note,

$$\sum_{n=r}^{\infty} x^n=\sum_{n=0}^{\infty} x^{n+r}=\frac{x^r}{1-x}$$

So that,

$$\sum_{n=r}^{\infty} {n \choose r}^{-1}$$

$$=r \int_{0}^{1} (1-x)^{r-2} dx$$

$$=\frac{r}{r-1}$$

$\endgroup$
0
3
$\begingroup$

\begin{align} \sum_{n=r}^\infty \binom{n}{r}^{-1} &= \sum_{n=r}^\infty \, (n+1)\int_0^1 x^{n-r} (1-x)^{r}\,dx \\ &= \int_0^1 \left( \sum_{n=r}^\infty (n+1)x^{n-r} \right) (1-x)^r \,dx \\ &= \int_0^1 \frac{1+r-rx}{(1-x)^2} (1-x)^r \,dx \\ &= \frac{r}{r-1} \end{align}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.