35
$\begingroup$

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.

$\endgroup$
  • 12
    $\begingroup$ 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> . $\endgroup$ – Noam D. Elkies Nov 17 '16 at 3:41
  • $\begingroup$ @NoamD.Elkies: Interesting. BTW, the link is broken. $\endgroup$ – T. Amdeberhan Nov 17 '16 at 4:06
  • 6
    $\begingroup$ The above link from Noam Elkies can be found at: math.stackexchange.com/questions/633219/… $\endgroup$ – T. Amdeberhan Nov 17 '16 at 4:28
  • 2
    $\begingroup$ @AlexeyUstinov it is related but not literally duplicate: the question which you cite does not have integer part. $\endgroup$ – Fedor Petrov Nov 17 '16 at 8:47
  • 2
    $\begingroup$ 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$). $\endgroup$ – Noam D. Elkies Nov 17 '16 at 14:18
24
$\begingroup$

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

$\endgroup$
23
$\begingroup$

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

$\endgroup$
15
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ this is very very nice $\endgroup$ – Pietro Majer Nov 19 '16 at 9:26
  • 3
    $\begingroup$ 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}.$ $\endgroup$ – Pietro Majer Nov 19 '16 at 10:46
  • 3
    $\begingroup$ I like the simplicity here. $\endgroup$ – T. Amdeberhan Nov 19 '16 at 13:33
  • 3
    $\begingroup$ 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)$ $\endgroup$ – Pietro Majer Nov 19 '16 at 14:36
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Tom Copeland Dec 17 '16 at 22:40

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.