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

4 Answers 4

25
$\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$
24
$\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$
0
16
$\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$
4
  • 3
    $\begingroup$ this is very very nice $\endgroup$ Nov 19, 2016 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$ Nov 19, 2016 at 10:46
  • 3
    $\begingroup$ I like the simplicity here. $\endgroup$ Nov 19, 2016 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$ Nov 19, 2016 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$
1
  • $\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$ Dec 17, 2016 at 22:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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