# Finding $\lim\limits_{n \to \infty} \sum\limits_{k=0}^n { n \choose k}^{-1}$

We know that $$2^n= (1+1)^n = \sum_{k=0}^n {n \choose k}$$ I was asked to solve this limit, $$\lim_{n \to \infty} \ \sum_{k=0}^n {n \choose k}^{-1}=? \quad \text{for} \ n \geq 1$$

-
Why is the text on this so big? –  Ben Alpert Sep 16 '10 at 23:44
@Ben Alpert: Because i gave the displaystyle command. –  anonymous Sep 22 '10 at 20:38

The terms from $k = 2$ to $k = n-2$ are all at most $\frac{1}{ {n \choose 2} }$ by unimodality, hence their sum is at most $\frac{2}{n-1}$. So the entire sum is at most $2 + \frac{2}{n} + \frac{2}{n-1}$. The limit is $2$.

-
@QY: Superb! What do you mean by unimodality! I cant get the meaning –  anonymous Sep 16 '10 at 13:36
Unimodality means that the sequence is increasing, then decreasing. This is a standard property of binomial coefficients. –  Qiaochu Yuan Sep 16 '10 at 14:13
@QY: I wasn't familiar with that term :x) –  anonymous Sep 16 '10 at 14:23

This does not exactly answer the question (which was answered very nicely by Qiaochu), but I am adding this as a curiosity.

We can write $\displaystyle \sum_{k=0}^{n} {n \choose k}^{-1}$ as an integral (which can be generalized to other expressions involving the reciprocals of the binomial coefficients).

We have the following beta integral identity

$${n \choose k}^{-1} = (n+1)\int_{0}^{1} t^{n-k}(1-t)^k \ dt$$

(For a nice application of Beta integrals, see this answer by Robin Chapman: Formula for the harmonic series due to Gregorio Fontana.)

We have

$$\sum_{k=0}^{n} {n \choose k}^{-1} = (n+1) \sum_{k=0}^{n} \int_{0}^{1} t^{n-k}(1-t)^k \ dt$$

$$= (n+1)\int_{0}^{1} \sum_{k=0}^{n} t^{n-k}(1-t)^k \ dt$$ $$= (n+1)\int_{0}^{1} \frac{t^{n+1} - (1-t)^{n+1}}{2t-1} \ dt$$

We should be able to use the analytical tools available to investigate the properties of this integral.

For instance, at least two different proofs that the limit is $2$ can be found here: Different proofs of $\lim\limits_{n \rightarrow \infty} n \int_0^1 \frac{x^n - (1-x)^n}{2x-1} \mathrm dx= 2$

For an example of a different use of this integral formula:

Setting $\displaystyle 2t-1 = y$ we get

$$\sum_{k=0}^{n} {n \choose k}^{-1} = \frac{n+1}{2^{n+2}} \int_{-1}^{1} \frac{(1+y)^{n+1} - (1-y)^{n+1}}{y} \ dy$$

Expanding out the right side gives us this nice looking formula

$$\sum_{k=0}^{n} {n \choose k}^{-1} = \frac{n+1}{2^n}\left(\frac{{n+1 \choose 1}}{1} + \frac{{n+1 \choose 3}}{3} + \frac{{n+1 \choose 5}}{5} + \dots \right)$$

-
(+1) nice answer. –  Mhenni Benghorbal Jun 14 '13 at 6:34
@MhenniBenghorbal: Thanks! –  Aryabhata Jun 14 '13 at 17:23