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
Answer
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)}.
No comments:
Post a Comment