26
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ Why do you want the upperbound to be $n+1$? $\endgroup$
    – Braindead
    Jan 10, 2014 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, 2014 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, 2014 at 0:47
  • 2
    $\begingroup$ See also mathoverflow.net/questions/254881/binomial-again-and-again. $\endgroup$ Dec 17, 2016 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, 2018 at 16:36

2 Answers 2

30
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ Excellent! Thanks for adding the additional details. $\endgroup$
    – abnry
    Jan 12, 2014 at 15:50
5
$\begingroup$

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

$\endgroup$
1
  • $\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, 2014 at 16:19

You must log in to answer this question.

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