Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Why do you want the upperbound to be $n+1$? –  Braindead Jan 10 at 0:38
    
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. –  nayrb Jan 10 at 0:40
    
Does it get worse if you do 0 to n? –  Braindead Jan 10 at 0:42
    
Yes, it does as far as I've seen it. –  nayrb Jan 10 at 0:42
2  
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. –  Grigory M Jan 10 at 0:47

2 Answers 2

up vote 14 down vote accepted

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

share|improve this answer
1  
Excellent! Thanks for adding the additional details. –  nayrb Jan 12 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).

share|improve this answer
    
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. –  nayrb Jan 10 at 16:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.