Show that $\lfloor 2n/p^k\rfloor$ is odd if $p^\alpha$ is in the prime factorization of $\binom{2n}n$

49 Views Asked by At

I am trying to work out the details of the accepted answer here:

On a property of the binomial coefficient

To summarize: We have $p$ a prime divisor of $\binom{2n}n$ and $\alpha$ the exponent in the prime factorization. That is to say

$$ p^\alpha | \binom{2n}n $$ $$ p^{\alpha+1} \require{cancel}\cancel{|} \binom{2n}n $$

We show that

$$ \alpha = \sum_{k=1}^\infty (\lfloor 2n/p^k \rfloor - 2\lfloor n/p^k\rfloor )$$

We want to show that if $k\le \alpha$ then $\lfloor 2n/p^k \rfloor$ is odd.

I suspect we want to consider the case of an odd prime separately, so for now let's assume $p$ is odd.


I'm unsure of exactly how to work with the floor function here. I can see that, splitting into integer and fractional parts,

\[ n/p^k = \lfloor n/p^k \rfloor + { n/p^k} \Rightarrow \\ 2n/p^k = 2\lfloor n/p^k \rfloor + 2{ n/p^k} \Rightarrow\\ \lfloor 2n/p^k \rfloor = 2\lfloor n/p^k\rfloor + x \]

where $x=0,1$ and as far as I can tell we can't get any good insights into $x$ in this setting.

I can see that this implies

$$ \alpha = \sum_{k=1}^\infty x $$

Also clearly when $n < p^k$ we have that $\lfloor n/p^k \rfloor = 0$ so that these terms in the sum could be dropped. If we call $\beta$ the exponent such that $p^\beta \le n < p^{\beta +1}$ then we have that $\alpha\le \beta$. But from here I'm stuck and not really all that sure if I've done anything useful.


Edit: I actually didn't see the second answer at that link until just now (the accepted one by TMM). I see that he rearranged the terms at the end. He then says that

$$ \lfloor 2n/p^k \rfloor - 2\lfloor n/p^k \rfloor = 1$$

if and only if $\lfloor 2n/p^k \rfloor$ is odd (and otherwise is 0). I haven't yet worked out how that follows from the work he has above, but I can probably get there on my own. What I really don't get is how this answers the question. If $k\le \alpha$ then it seems that somehow this is supposed to tell us that $\lfloor 2n/p^k\rfloor - 2\lfloor n/p^k\rfloor = 1$. At that point we can use what he found to get the desired result. But I don't see how we get to the point where we can infer that $\lfloor 2n/p^k\rfloor - 2\lfloor n/p^k\rfloor = 1$.

1

There are 1 best solutions below

2
On BEST ANSWER

It is not true that $\lfloor 2n/p^k \rfloor$ is odd if $1\le k\le \alpha$.

For example, consider $n=5, p=2$.
$\binom{2n}n=2^2\cdot3^2\cdot7$.
Let $k=2\le\alpha=2$.
However, $\lfloor 2n/p^k \rfloor=\lfloor 10/2^2 \rfloor=2$ is even.

For example, consider $n=18, p=3$.
$\binom{2n}n=2^2×3×5^2×7×11×19×23×29×31$.
Let $k=1\le\alpha=1$.
However, $\lfloor 2n/p^k \rfloor=\lfloor 36/3^1 \rfloor=12$ is even.


To show that $ \lfloor 2n/p^k \rfloor - 2\lfloor n/p^k \rfloor = 1$ if and only if $\lfloor 2n/p^k \rfloor$ is odd, let us prove the general fact.

Claim: $ \lfloor 2x \rfloor - 2\lfloor x \rfloor = 1$ if and only if $\lfloor 2x \rfloor$ is odd.

Proof: $x = \lfloor x\rfloor + \{x\}$. There are two cases.

  • $0\le\{x\}\lt\frac12$. Then $\lfloor 2x\rfloor=2\lfloor x\rfloor$ is even .
  • $\frac12\le\{x\}\lt1$. Then $\lfloor 2x\rfloor=2\lfloor x\rfloor+1$ is odd.