10
$\begingroup$

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$$

  • 0
    Why is the text on this so big?2010-09-16
  • 2
    @Ben Alpert: Because i gave the displaystyle command.2010-09-22

2 Answers 2

17

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$.

  • 0
    @QY: Superb! What do you mean by unimodality! I cant get the meaning2010-09-16
  • 5
    Unimodality means that the sequence is increasing, then decreasing. This is a standard property of binomial coefficients.2010-09-16
  • 0
    @QY: I wasn't familiar with that term :x)2010-09-16
13

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)$$

  • 0
    @MhenniBenghorbal: Thanks!2013-06-14