We know that $$\sum_{k=0}^n {n \choose k} = 2^n.$$

A continuous generalization of the formula would be $$\int_0^{n+1} \frac{\Gamma(n+1)}{\Gamma(n-x+1) \Gamma(x+1)} dx = 2^n?,$$ but this is incorrect numerically, though close, as I've checked it for $n=4$ and $n=5$. It is even closer when the bounds of integration is changed to $[-1, n+1]$ (e.g. $n=3$ gives $8.036$, $n=4$ gives $16.0274$, $n=8$ gives $256.013$).

Is there a formula for the difference of the integral and $2^n$ with either set of bounds? Can the order of the error be determined as dependent on $n$? It should be trivial to show that the expression grows as $2^n$ by doing a Riemann sum comparison and using the original formula, right? Is there a better generalization?

Here is the Wolfram alpha plot of the integrand for $n=4$:

enter image description here

  • $\begingroup$ Why do you want the upperbound to be $n+1$? $\endgroup$ – Braindead Jan 10 '14 at 0:38
  • $\begingroup$ Fencepost error: We sum over $n+1$ terms, we want the length of the interval to be $n+1$ too--only fair. But extending to -1 and $n+1$ makes it better anyways. $\endgroup$ – abnry Jan 10 '14 at 0:40
  • 2
    $\begingroup$ 1. Continuous generalization of a binomial coefficient is given by Beta-function. 2. If you want to compare a integral with the corresponding sum, answer is given by the Euler–Maclaurin formula. $\endgroup$ – Grigory M Jan 10 '14 at 0:47
  • 2
    $\begingroup$ See also mathoverflow.net/questions/254881/binomial-again-and-again. $\endgroup$ – Tom Copeland Dec 17 '16 at 23:12
  • 1
    $\begingroup$ (1) variations of the argument I gave on MO show $$\int_0^{n+1} {n \choose x}\,dx=2^n - \frac{1}{\pi} \int_0^\infty \frac{(1-e^{-\pi t})^{n+1}}{1+t^2} \,dt$$ $$\int_{-1}^{n+1} {n \choose x}\,dx=2^n +\frac{2}{\pi} \int_0^\infty \frac{e^{-\pi t}\,(1-e^{-\pi t})^{n}}{1+t^2} \,dt$$ (2) using that one can also determine the order of magnitude of the difference. It turns out to be $1/\log(n)$ for the $0..n+1$ integral and $2/n(\log(n)^2$ for the $-1,..,n+1$ integral. $\endgroup$ – esg Aug 10 '18 at 16:36

Integrate over the entire real line and it will work exactly, even without assuming that $n$ is an integer, as long as $n>-1$. (When $n$ is an integer, the sum $\sum_{k=0}^n {n \choose k}$ is also $\sum_{k=-\infty}^\infty {n \choose k}$, which is a Riemann sum with mesh 1 for the integral.) I refer to formula 6.414#2 in Gradshteyn and Ryzhik (which in turn cites "ET II 297(5)", where ET II = Erdélyi et al., Tables of Integral Transforms II [New York: McGraw Hill, 1954]): $$ \int_{-\infty}^\infty \frac{dx}{\Gamma(\alpha+x)\,\Gamma(\beta-x)} = \frac{2^{\alpha+\beta-2}}{\Gamma(\alpha+\beta-1)}, $$ which holds for all complex $\alpha,\beta$ with ${\rm Re}(\alpha+\beta) > 1$. Your integrand is obtained by taking $(\alpha,\beta) = (1,n+1)$ and multiplying through by $\Gamma(n+1)$.

Added later: In fact $2^n = \sum_{k=-\infty}^\infty {n \choose w+k}$ holds for all real $-$ or even complex $-$ $w$ as long as $n > -1$ (more generally ${\rm Re}(n) > -1$ for $n \in \bf C$), where the terms $n \choose w+k$ are defined using the Gamma function as suggested. Integration with respect to $w$ from $w=0$ to $w=1$ then gives the integral $\int_{x=-\infty}^\infty {n \choose x} \, dx = 2^n$.

We outline a complex-analytic proof of the formula for $F_n(w) := \sum_{k=-\infty}^\infty {n \choose w+k}$ for ${\rm Re}(n) > 0$, for which the sum converges absolutely; to extend to ${\rm Re}(n) > -1$ we could group the terms in pairs to get absolute convergence and then argue similarly. Using the Stirling's approximation to the complex Gamma function we find that $F_n(w)$ converges to an analytic function of period $1$ in $w$. [When $-1 < {\rm Re}(n) \leq 0$ an extra step is needed to prove $F_n(w+1) = F_n(w)$.] Moreover, on a period strip such as $0 \leq {\rm Re}(w) \leq 1$ the Stirling estimate shows that $|F_n(w)|$ grows no faster than some power of $w$ times $\exp \pi\left|{\rm Im}(w)\right|$. This implies that $F_n$ is constant by a standard argument(*). But we already saw that $F_n(0) = 2^n$. Hence $F_n(w) = 2^n$ for all $w$, QED.

(*) An analytic function of $w$ has period $1$ iff it is an analytic function of $q := e^{2\pi i w}$; now use Laurent expansions about $q=0$ and $q=\infty$, where $F_n$ is $O(|q|^{\pm(1/2+\epsilon)})$, to show that this function is entire and bounded, and thus constant by Liouville.

P.S. The case $n=0$ of the formula $$ \int_{-\infty}^\infty \frac{\Gamma(n+1)}{\Gamma(n-x+1)\,\Gamma(x+1)} dx = 2^n $$ is equivalent (via the identity $\Gamma(z)\,\Gamma(1-z) = \frac\pi{\sin \pi z}$) with the famous definite integral $\int_{-\infty}^\infty \sin t \, dt/t = \pi$.

  • 2
    $\begingroup$ Excellent! Thanks for adding the additional details. $\endgroup$ – abnry Jan 12 '14 at 15:50

The continuous generalization is given by the central limit theorem of de Moivre-Laplace, and in particular, the formula $$\int_0^\infty \exp\left(-x^2\right) = \frac{\sqrt{\pi}}2.$$ The integrand is a good approximation to the binomial coefficient, modulo scaling (which is, in a way, the content of the central limit theorem; see the linked-to page).

  • $\begingroup$ This is a good point but does only a small amount for answering my question. How to apply the central limit theorem specifically? The $Gamma$ based integrand does not come from the sum of $n$ random variables as far as i know, it's the original binomial distribution that matters. $\endgroup$ – abnry Jan 10 '14 at 16:19

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.