# Is the numerator of $\sum_{k=0}^{n}{(-1)^k\binom{n}{k}\frac{1}{2k+1}}$ always a power of $2$ in lowest terms?

Is the numerator of $$\sum_{k=0}^{n}{(-1)^k\binom{n}{k}\frac{1}{2k+1}}$$ always a power of $2$ in lowest terms, and if so, why? Is there a combinatorial or probabilistic proof of this?

• How much numerical evidence for this do you have? Apr 10, 2018 at 22:38
• This is equal to the product of all even numbers up to $2n$ divided by the product of all odd numbers up to $2n+1$. So the question is why is there enough downstairs to cancel all the odds from upstairs. Apr 10, 2018 at 22:45
• @HenningMakholm Through about $n=50$. Put $\sqrt{\frac{1-x}{x}}\arctan\left(\sqrt{\frac{x}{1-x}}\right)$ into Mathematica (or Wolfram Alpha) and check its Taylor series for yourself. Apr 10, 2018 at 22:46
• @ArnaudMortier Ah, so $2^n n!\frac{2^n n!}{(2n+1)!}=\frac{2^{2n}}{(2n+1)\binom{2n}{n}}$. Yeah, that explains it. Apr 10, 2018 at 22:59
• I edited my answer to add a combinatorial proof of the crucial identity. Apr 11, 2018 at 0:26

Proved in edit at the end: this sum is equal to the fraction $${\prod_{i=1}^n 2i\over\prod_{i=1}^{n} 2i+1}$$

Now: $\prod_{i=1}^n 2i=2^n n!$

and $\prod_{i=1}^{n} {2i+1}={(2n+1)!\over \prod_{i=1}^n 2i}={(2n+1)!\over 2^n n!}$

Therefore your sum is equal to $${(2^n n!)^2\over (2n+1)!}={2^{2n}\over(2n+1){2n \choose n}}$$

Where the result is now clear.

Edit: combinatorial proof of the identity ${\prod_{i=1}^n 2i\over\prod_{i=1}^{n} 2i+1}$.

Define the sum $$S_{n,m}=\sum_{k=0}^{n}{(-1)^k\binom{n}{k}\frac{1}{2k+m}}$$ Claim: for any $n,m$, one has $$S_{n,m}={\prod_{i=1}^{n}2i\over \prod_{i=0}^{n}2i+m }$$

The claim implies the desired identity when $m=1$.

Proof of the claim:

The identity ${n+1\choose k}={n\choose k}+{n\choose k-1} \$ implies immediately that $$S_{n+1,m}=S_{n,m}-S_{n,m+2}$$

Moreover, the claim holds when $n=0$, where $S_{0,m}=\frac1m$

The result follows now from an immediate induction on $n$.

• This is nice, but I think I had something more bijective in mind. Like an application of the sieve method. Say, we consider the set $\{0,\pm1, \pm2,\dots,\pm n\}$ and the properties $P_i=$ something happens at $\pm i$, $i=1,\dots,n$. Then see where we have exactly $0$ properties, i.e. something happens only at $0$. Apr 11, 2018 at 0:58
• @AlexanderBurstein Interesting. I'll try to think in this direction too. Apr 11, 2018 at 1:01

Consider the function $$F(q)=\sum_{k=0}^n (-1)^k {n\choose k} q^{2k}=(1-q^2)^n$$ If we denote the sum you want to calculate by $\phi=\sum_{k=0}^n (-1)^k {n\choose k}\frac{1}{2k+1}$, then $$\phi = \int_0^1 F(q)dq = \int_0^1 (1-q^2)^n dq=\frac{(2n)!!}{(2n+1)!!}$$ where $k!!=k(k-2)(k-4)\cdots$. This simplifies to $$\phi=\frac{2^{2n} (n!)^2}{(2n+1)!}$$ Now note that $${2n \choose n}=\frac{(2n)!}{(n!)^2}\in \mathbb{Z}$$ so $(n!)^2$ divides $(2n)!$ which in turn means it divides $(2n+1)!$. So the numerator of $\phi$ is necessarily a power of $2$ in lowest terms.

• Thanks! That explains it. But what would be a combinatorial/probabilistic proof of this identity? Kind of curious about that still. Although, that’s probably deducible from the answer somehow. Apr 10, 2018 at 23:00
• If you insist on the combinatorial/probabilistic proof, let me think about it a bit. I'm sure there is one. Apr 10, 2018 at 23:06
• @Hamed (+1) I got one, if you are interested :) Apr 11, 2018 at 0:30
• It's too bad I can't accept both answers, this one is very good, too. Apr 11, 2018 at 1:00