17
$\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
    Commented Feb 1, 2017 at 14:45
  • 6
    $\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
    Commented Feb 1, 2017 at 14:45
  • $\begingroup$ What is the source of the problem? What is $r$? $\endgroup$ Commented Feb 1, 2017 at 14:51
  • $\begingroup$ @labbhattacharjee : this is an exercice (of the second chapter) from the book "Principles and Techniques in Combinatorics". $\endgroup$ Commented Feb 1, 2017 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$ Commented Feb 1, 2017 at 15:41

3 Answers 3

14
$\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
    Commented Feb 1, 2017 at 16:10
  • 1
    $\begingroup$ @MartinSleziak: Very nice! (+1) $\endgroup$ Commented Feb 1, 2017 at 16:10
  • 1
    $\begingroup$ @MartinSleziak: thank you very much for your detailed answer. It's very kind of you. $\endgroup$ Commented Feb 1, 2017 at 16:55
9
$\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
4
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .