6
$\begingroup$

May not be a research-level problem for an expert, but non-trivial for a non-expert: why do we have $$ \sum_{k=0}^n \frac{(-1)^k}{2k+1} \binom{n}{k} = \frac12 \int_0^\pi (\sin x)^{2n+1} dx $$ and what is the asymptotic / good lower bound for this as $n$ grows? Thanks!

$\endgroup$
2
  • 8
    $\begingroup$ One very useful thing to recognize is that for any function $f: \mathbb{N} \to A$ into an abelian group $A$, the expression $\sum_{k=0}^n (-1)^{n-k} \binom{n}{k} f(k)$ is $(\Delta^n f)(0)$, where $(\Delta f)(n) := f(n+1) - f(n)$. $\endgroup$
    – Todd Trimble
    Nov 25, 2016 at 16:51
  • 7
    $\begingroup$ We have $$\sum_{k=0}^n \frac{(-1)^k}{2k+1} \binom nk =\binom{n+1/2}{n}^{-1}.$$ This is equivalent to the case $a=1/2$ of the well-known identity $$ \sum_{k=0}^n(-1)^k \frac{a}{k+a} \binom nk =\binom{n+a}{n}^{-1} $$ which can be proved in many ways (e.g., induction, partial fractions, the beta integral, a special case of Vandermonde's theorem). $\endgroup$
    – Ira Gessel
    Nov 25, 2016 at 16:57

2 Answers 2

11
$\begingroup$

You suspected right. It's easy. Convert $\sin^{2n+1}x=(1-\cos^2x)^n\sin x$ and integrate by substitution and apply binomial expansion $$\int_0^{\pi}\sin^{2n+1}x\,dx=2\int_0^1(1-u^2)^ndu=2\sum_{k=0}^n(-1)^k\binom{n}k\int_0^1u^{2k}du=2\sum_{k=0}^n\frac{(-1)^k}{2k+1}\binom{n}k.$$ There is more to this: the RHS has a closed form $$\frac12\int_0^1\sin^{2n+1}x\,dx=\sum_{k=0}^n\frac{(-1)^k}{2k+1}\binom{n}k=\frac{2^{2n}}{2n+1}\binom{2n}n^{-1}.\tag1$$ To prove (1), one may follow Ira Gessel's suggestion. But, let's employ Zeilberger's algorithm for the Wilf-Zeilberger method. Introduce the functions $F(n,k)=(-1)^k\frac{a}{k+a}\binom{n}k\binom{n+a}a$ and $G(n,k)=-F(n,k)\frac{(k+a)k}{(n-k+1)(n+1)}$. Then, check that $$F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k). \tag2$$ Now, sum (2) over all integers (note that $\binom{n}k=0$ if $k<0$ or $k>n$). Then the key is the RHS of (2) vanishes. Further, $f(n+1)-f(n)=0$ where $f(n)=\sum_{k=0}^nF(n,k)$. So, $f(n)$ is a constant sequence. Checking $f(0)=1$ implies $f(n)=1$, identically. We have recovered the generalized identity that Gessel mentioned above: $$\sum_{k=0}^n(-1)^k\frac{a}{k+a}\binom{n}k=\binom{n+a}a^{-1}.$$ NOTE. If you're into this kind of integrals, perhaps this MO discussion might appeal to you.

Regarding the asymptotic, it can be extracted using Stirling's approximation for the factorial $n!$; that is, to the first order $$\frac{2^{2n}}{2n+1}\binom{2n}n^{-1}\,\sim\, \sqrt{\pi}\left(2\sqrt{n}+\frac1{\sqrt{n}}\right)^{-1}.$$

We can get "bonus identities" by considering different linear change of variables for the same integral. $$\int_0^1(1-u)^n(1+u)^ndu=\sum_{k,j=0}^n(-1)^k\binom{n}k\binom{n}j\int_0^1u^{k+j}du=\sum_{k,j=0}^n\frac{(-1)^k}{k+j+1}\binom{n}k\binom{n}j.$$ $$\int_0^1y^n(2-y)^ndy=\sum_{k=0}^n(-1)^k2^{n-k}\binom{n}k\int_0^1y^kdy =\sum_{k=0}^n\frac{(-1)^k2^{n-k}}{n+k+1}\binom{n}k.$$ $$\int_{-1}^12^{2n}t^n(1-t)^ndt=2^{2n}\sum_{k=0}^n(-1)^k\binom{n}k\int_0^1t^{n+k}dt=2^{2n}\sum_{k=0}^n\frac{(-1)^k}{n+k+1}\binom{n}k.$$

$\endgroup$
4
  • $\begingroup$ Great! The only question remaining, where does the closed form come from? $\endgroup$
    – W-t-P
    Nov 25, 2016 at 17:15
  • 3
    $\begingroup$ You can also derive it directly from the first line: changing variable linearly $\int_{-1}^{1}(1-u^2)^n du=2^{2n+1}\int_{0}^{1}t^n(1-t)^ndt= 2^{2n+1} B(n+1,n+1)$ $\endgroup$ Nov 25, 2016 at 17:46
  • $\begingroup$ Yes! That's perhaps what Gessel had in mind from the above comment. $\endgroup$ Nov 25, 2016 at 17:48
  • 2
    $\begingroup$ What I had in mind is $$ \begin{aligned} \sum_{k=0}^n(-1)^k \frac{a}{k+a} \binom nk &= \sum_{k=0}^n (-1)^k a\binom nk\int_0^1 t^{k+a-1}\,dt\\ &=\int_0^1 a t^{a-1} \sum_{k=0}^n (-1)^k \binom nk t^k\,dt\\ &=a\int_0^1 t^{a-1}(1-t)^n\, dt\\ &=aB(a,n+1). \end{aligned} $$ $\endgroup$
    – Ira Gessel
    Nov 25, 2016 at 20:14
11
$\begingroup$

As I hinted in my comment, the $(-1)^k \binom{n}{k}...$ should set off alarm bells. There is for example a basic reciprocity law, that for functions $f, g: \mathbb{N} \to \mathbb{R}$, we have

$$g(n) = \sum_{k=0}^n (-1)^k \binom{n}{k} f(k) \qquad \text{iff} \qquad f(n) = \sum_{k=0}^n (-1)^k \binom{n}{k} g(k)$$

(see Concrete Mathematics by Graham, Knuth, and Patashnik, Trick 3 on page 192; it's an easy exercise using e.g. exponential generating functions).

Using this, the claimed identity is equivalent to

$$\frac{1}{2n+1} = \sum_{k=0}^n \binom{n}{k} \frac1{2} \int_0^\pi (-1)^k (\sin x)^{2k+1}\; dx$$

which follows easily since the right side is (by the binomial theorem)

$$\frac1{2} \int_0^\pi \sin(x) (1 - \sin^2 x)^n\; dx = \frac1{2} \int_0^\pi (\cos x)^{2n} \sin x\; dx$$

followed by a straightforward integration.


As noted by Ira Gessel, the closed-form evaluation of $\sum_{k=0}^n (-1)^k \binom{n}{k} \frac1{2k+1}$ can be achieved by any number of methods. In the spirit of finite difference calculus (alluded to in my comment under the question), where the $n^{th}$ falling power

$$x^{\underline{n}} = x(x-1)\ldots (x-n+1)$$

plays the role of $x^n$ in the ordinary continuous calculus, we have $x^{\underline{m+n}} = x^{\underline{m}} (x - m)^{\underline{n}}$, giving the definition $x^{\underline{-m}} = \frac1{(x+1)(x+2)\ldots (x+m)}$, and the difference formula $\Delta x^{\underline{k}} = k x^{\underline{k-1}}$ (the Pascal triangle identity in disguise) holds for all integers $k$. By means of this one quickly computes

$$\Delta^n \frac1{2x + 1} = \frac{(-1)^n n! 2^n}{(2x+1)(2x + 3)\ldots (2(x+n) + 1)}$$

and then my comment which says $(-1)^n (\Delta^n f)(0) = \sum_{k=0}^n (-1)^k \binom{n}{k} f(k)$ leads to the evaluation

$$\sum_{k=0}^n (-1)^k \binom{n}{k} \frac1{2k+1} = \frac{n! 2^n}{1 \cdot 3 \cdot \ldots \cdot (2n+1)} = \frac{(n!)^2 2^{2n}}{(2n+1)!}$$

as Ira Gessel and T. Amdeberhan were saying.

$\endgroup$
1
  • $\begingroup$ This is cool, indeed. $\endgroup$ Nov 26, 2016 at 0:20

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.