# Binomial again, and again

Let $\lceil a\rceil=$ the smallest integer $\geq a$, otherwise known as the ceiling function. When the arguments are real, interpret $\binom{a}b$ using the Euler's gamma function, $\Gamma$.

Recently, I posted a problem on MO about "sin-omials". Here is another one in the same spirit.

QUESTION. Numerical evidence suggest that $$\left\lceil \int_0^n\binom{n}x dx\right\rceil=\sum_{k=0}^n\binom{n}k.$$ If true, how do we prove this?

REMARK. The RHS evaluates to $2^n$; I only want to stress parallelism between the integral and sum.

• Probably relevant: $$\int_{-\infty}^\infty {n \choose x} \, dx = 2^n$$ exactly. In fact it equals $\sum_{k=-\infty}^\infty {n \choose k+x}$ for any real $x$. See my accepted answer to Question 632219 in Math Stackexchange <math.stackexchange.com/questions/633219> . – Noam D. Elkies Nov 17 '16 at 3:41
• @NoamD.Elkies: Interesting. BTW, the link is broken. – T. Amdeberhan Nov 17 '16 at 4:06
• The above link from Noam Elkies can be found at: math.stackexchange.com/questions/633219/… – T. Amdeberhan Nov 17 '16 at 4:28
• @AlexeyUstinov it is related but not literally duplicate: the question which you cite does not have integer part. – Fedor Petrov Nov 17 '16 at 8:47
• Right, but it is equivalent to the statement at the end of my second comment (the integrals outside $[0,n]$ add up to something that's negative but not as negative as $-1$). – Noam D. Elkies Nov 17 '16 at 14:18

Following the hint by Noam D. Elkies, we just need to show that the remainder $$R_n:=\int_{-\infty}^0{n!\over\Gamma(n+1-x)\Gamma(1+x)}dx+ \int_n^{+\infty} {n!\over\Gamma(n+1-x)\Gamma(1+x)}dx$$ satisfies $$0\le R_n<1.$$ The integrand writes $${n!\over\Gamma(n+1-x)\Gamma(1+x)}={n! \over (n-x)(n-1-x)\dots(1-x)\Gamma(1-x)x\Gamma(x)}={n!\over \pi}{ \sin \pi x \over (n-x)(n-1-x)\dots(1-x)x}.$$ With a linear change of variables it is easy to see that the two integrals above coincide, so that the remainder takes the form $$R_n= {2n!\over\pi}\int_{0}^{+\infty} {{ \sin \pi x \over x(x+1)\dots(x+n)}}\, dx$$

so in particular $R_0=1$. If we further write the integral as a Leibnitz alternating sum of the integrals over unit intervals, we find $$R_n= {2n!\over\pi}\sum_{k=0}^{\infty}\; (-1)^k\int_{0}^{1} {{ \sin \pi x \over (x+k)\dots(x+k+n)}}\, dx$$ $$={2n!\over\pi}\int_{0}^{1}\sin \pi x\bigg[ \sum_{k=0}^{\infty}\; {{ 1 \over (x+2k)\dots(x+2k+n)}}-{{ 1 \over (x+2k+1)\dots(x+2k+1+n)}}\bigg]\, dx$$ $$={2\over\pi}\int_{0}^{1}\sin \pi x \bigg[\sum_{k=0}^{\infty}\; {{ (n+1)! \over (x+2k)\dots(x+2k+1+n)}} \bigg]\, dx.$$ This way it is apparent that $R_n$ is positive and strictly decreasing w.r.to $n$, and we conclude that for $n\ge1$
$$0< R_n< R_0=1.$$

Here is a proof which doesn't use the identity $\int_{-\infty}^\infty {n \choose x}\,dx= 2^n$:

Using the representation ${ n \choose x}=\frac{1}{2\pi}\int_{-\pi}^\pi e^{-ixt}\left(1+e^{it}\right)^n\,dt$ (valid for $n,x\in\mathbb{R}, n>-1$) we find \begin{align*} \int_0^n {n \choose x}\,dx&=\frac{1}{2\pi} \int_0^n\int_{-\pi}^\pi e^{-ixt}\left(1+e^{it}\right)^n\,dt\,dx \\ &=\frac{1}{2\pi} \int_{-\pi}^\pi \frac{1-e^{-int}}{it}\left(1+e^{it}\right)^n\,dt\\ &=\frac{1}{2\pi} \int_{-\pi}^\pi \sum_{k=0}^n {n \choose k} \frac{e^{ikt}-e^{-i(n-k)t}}{it}\,dt\\ &=\frac{1}{2\pi} \int_{-\pi}^\pi \sum_{k=0}^n {n \choose k} \frac{e^{ikt}-e^{-ikt}}{it}\,dt\\ &=\frac{1}{\pi} \int_{-\pi}^\pi \sum_{k=0}^n {n \choose k} \frac{\sin(kt)}{t}\,dt\\ &=\frac{2}{\pi} \sum_{k=0}^n {n \choose k} \int_{0}^\pi\frac{\sin(kt)}{t}\,dt\\ &=\frac{2}{\pi} \sum_{k=0}^n {n \choose k} \mathrm{Si}(k\pi) \;\;\;\;\;\;\;\; (*) \end{align*} where $\mathrm{Si}(x)=\int_0^x \frac{\sin(t)}{t}\,dt$ denotes the sine integral. For $a\geq 0$ the sine integral has the representation $$\mathrm{Si}(a)=\frac{\pi}{2} - \cos(a)\,\int_{0}^\infty \frac{e^{-at}}{1+t^2}\,dt - \sin(a)\,\int_{0}^\infty \frac{t\,e^{-at}}{1+t^2}\,dt$$ Plugging this into $(*)$ (and using $\sin(k\pi)=0,\, \cos(k\pi)=(-1)^k$) we arrive at $$\int_0^n {n \choose x}\,dx=2^n - \frac{2}{\pi} \int_0^\infty \frac{(1-e^{-\pi t})^n}{1+t^2} \,dt=:2^n - R_n$$ Clearly the sequence $(R_n)$ is nonnegative, strictly decreasing and $R_0=1$.

Here's another proof of the key integral $$\int_{-\infty}^\infty {n \choose x} \, dx = 2^n$$ for $n=0,1,2,\ldots$, which is elementary modulo the classical definite integral $$\int_{-\infty}^\infty \sin t \, \frac{dt}{t} = \pi.$$ To my surprise, with a bit more work we also get what might be a new derivation of the latter formula as well.

Start from Pietro Majer's rewriting of $n \choose x$ as $$\frac{n!}{\pi} \, \frac{\sin \pi x}{(n-x)(n-1-x) \cdots (1-x) x}$$ (which we can take as the definition of $n \choose x$ for real $x$, thus replacing the Gamma function with a more elementary trigonometric function; note that the last factor in the denominator is $x$, not $0-x$). Now expand in partial fractions: $$\frac1{(n-x)(n-1-x) \cdots (1-x) x} = \sum_{i=0}^n \frac{c_i}{x-i},$$ to get $$\int_{-\infty}^\infty {n \choose x} \, dx = \frac{n!}{\pi} \sum_{i=0}^n c_i \int_{-\infty}^\infty \sin \pi x \, \frac{dx}{x-i}.$$ The integral is $(-1)^i \int_{-\infty}^\infty \sin \pi x \, \frac{dx}{x} = (-1)^i \pi$, so $$\int_{-\infty}^\infty {n \choose x} \, dx = n! \sum_{i=0}^n (-1)^i c_i.$$ But $c_i$ can be computed by letting $x \to i$ in the partial fraction expansion; we find that $(1)^i n! c_i = {n \choose i}$, so finally $$\int_{-\infty}^\infty {n \choose x} \, dx = \sum_{i=0}^n {n \choose i} = 2^n,$$ as claimed.

Now suppose we didn't know the value, call it $I$, of $\int_{-\infty}^\infty \sin t \, \frac{dt}{t}$. Then our analysis still gives $$\int_{-\infty}^\infty {n \choose x} \, dx = \frac{I}{\pi} 2^n.$$ But I claim that for large even $n$ the integral is asymptotic to $2^n$, whence $I=\pi$. The idea is:

i) the Riemann sum $\sum_{x=-\infty}^\infty {n \choose x}$ is $2^n$ exactly;

ii) the integral of ${n \choose x} \, dx$ over $x$ outside the interval $[0,n]$ is asymptotically small compared with $2^n$; and

iii) the integral from $0$ to $n$ is within $n \choose n/2$ of the Riemann sum $\sum_{i=0}^n {n \choose i}$, and is thus asymptotic to $2^n$.

Now (i) is just the binomial expansion of $(1+1)^n$, which we've used already, while (ii) was already proved by Pietro Majer (in fact he obtained a much stronger bound of $1$, while we need only $o(2^n)$ which is easier to prove). It remains to show (iii). But this requires only that $n \choose x$ is increasing on $0 < x < n/2$ and decreasing on $n/2 < x < n$ (we can then compare the integral with the lower and upper Riemann sums). But we readily see from the product formula for $\sin \pi x$ that $\log{n \choose x}$ is concave downwards on $0 < x < n$; since this function is symmetric about $x=n/2$, we conclude that it is increasing on $x<n/2$ and decreasing on $x>n/2$, QED.

• this is very very nice – Pietro Majer Nov 19 '16 at 9:26
• The starting point for the second part, that is the identity $\int_{-\infty}^{+\infty} {n\choose x}dx={2^n}\int_{-\infty}^{+\infty} {0\choose x}dx={2^n\over \pi}\int_{-\infty}^{+\infty} {\sin\pi x\over x}dx,$ may also be derived inductively, integrating ${n\choose x}={n-1\choose x}+{n-1\choose x-1}.$ – Pietro Majer Nov 19 '16 at 10:46
• I like the simplicity here. – T. Amdeberhan Nov 19 '16 at 13:33
• Also, if we adopt the trigonometric definition of ${n\choose x}$, the relation ${n-1\choose x}+ {n-1 \choose x-1}= {n\choose x}$ may be derived from the identity: $${1\over(n-1-x)\dots(1-x)\cdot x}-{1\over(n-x)\dots(2-x)\cdot(x-1)}={n\over(n-x)(n-1-x)\dots(1-x)\cdot x}$$ multiplying by $\sin\pi x=-\sin\pi(x-1)$ – Pietro Majer Nov 19 '16 at 14:36

The $2^n$ result in Noam Elkies answer generalizes to $n=s$ for $real(s)>-1$, as he notes in MSE. In this range, the generalized binomial coefficient $\binom{s}{\alpha}$ is a Fourier band-limited fct. in $\alpha$, or, equivalently a sinc fct. interpolation of the sequence $\binom{s}{n}$. See my notes "Fractional calculus and interpolation of generalized binomial coefficients" for simple derivations and my contribution to the MO-Q Generalizing a problem to make it easier for the integral of the sinc fct. over infinte limits, also simply derived.

The Wikipedia article on the classic Gibbs phenomena explores the extrema of $Si(x)$, easily visualized as a convolution of the sinc with the rectangle function, and, therefore, bounds on the residual of the ceiling.

The sinc function interpolation is an important illustration of the Nyquist-Shannon sampling theorem and a special case of a generalized Chu-Vandermonde identity using Euler's reflection formula for the gamma/factorial function. (I remember long ago reading somewhere that Ramanujan noted this. Anyone know a ref? This would be simple check for his Master Theorem/Formula.)

• Since it is band-limited, we could also interpolate from the samples $\binom{s}{n+\beta}$, for fractional $\beta$, summing over all the integers, negative and positive, and get the same results. – Tom Copeland Dec 17 '16 at 22:40