6
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ How much numerical evidence for this do you have? $\endgroup$ Apr 10, 2018 at 22:38
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 10, 2018 at 22:45
  • $\begingroup$ @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. $\endgroup$ Apr 10, 2018 at 22:46
  • $\begingroup$ @ArnaudMortier Ah, so $2^n n!\frac{2^n n!}{(2n+1)!}=\frac{2^{2n}}{(2n+1)\binom{2n}{n}}$. Yeah, that explains it. $\endgroup$ Apr 10, 2018 at 22:59
  • $\begingroup$ I edited my answer to add a combinatorial proof of the crucial identity. $\endgroup$ Apr 11, 2018 at 0:26

2 Answers 2

5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$ Apr 11, 2018 at 0:58
  • $\begingroup$ @AlexanderBurstein Interesting. I'll try to think in this direction too. $\endgroup$ Apr 11, 2018 at 1:01
5
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Apr 10, 2018 at 23:00
  • $\begingroup$ If you insist on the combinatorial/probabilistic proof, let me think about it a bit. I'm sure there is one. $\endgroup$
    – Hamed
    Apr 10, 2018 at 23:06
  • $\begingroup$ @Hamed (+1) I got one, if you are interested :) $\endgroup$ Apr 11, 2018 at 0:30
  • $\begingroup$ It's too bad I can't accept both answers, this one is very good, too. $\endgroup$ Apr 11, 2018 at 1:00

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.