May not be a researchlevel problem for an expert, but nontrivial for a nonexpert: 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!

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)^{nk} \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 wellknown 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 GesselNov 25, 2016 at 16:57
2 Answers
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(1u^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 WilfZeilberger 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}{(nk+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(1u)^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(2y)^ndy=\sum_{k=0}^n(1)^k2^{nk}\binom{n}k\int_0^1y^kdy =\sum_{k=0}^n\frac{(1)^k2^{nk}}{n+k+1}\binom{n}k.$$ $$\int_{1}^12^{2n}t^n(1t)^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.$$

$\begingroup$ Great! The only question remaining, where does the closed form come from? $\endgroup$– WtPNov 25, 2016 at 17:15

3$\begingroup$ You can also derive it directly from the first line: changing variable linearly $\int_{1}^{1}(1u^2)^n du=2^{2n+1}\int_{0}^{1}t^n(1t)^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+a1}\,dt\\ &=\int_0^1 a t^{a1} \sum_{k=0}^n (1)^k \binom nk t^k\,dt\\ &=a\int_0^1 t^{a1}(1t)^n\, dt\\ &=aB(a,n+1). \end{aligned} $$ $\endgroup$ Nov 25, 2016 at 20:14
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 closedform 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(x1)\ldots (xn+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{k1}}$ (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.