Show that $\frac{(2n-1)!}{(n)!(n-1)!}$ is odd or even according as to whether $n$ is or is not a power of $2$.

Question

Show that $\frac{(2n-1)!}{(n)!(n-1)!}$ is odd or even according as $n$ is or is not a power of $2$.

I know that the index of the highest power of $2$ contained in $n!$ is $n-1$ when $n$ is a power of $2$ and $n-r$ when $n$ is equal to $2^r-1$.

I've expanded the above to the result that the index of the highest power of $2$ contained in $n!$ is $2^r-1$ when $n$ is equal to $2^r+1$. (If you're wondering how I derived it, refer to the formula given in this question and correct me if I'm wrong). Using that, I've got that the highest power of $2$ in the term when $n$ is a power of $2$ is $\frac{2^{r+1}-(r+2)}{(2^r-1)(2^r-(r+1))}$.

Now here, if $r$ is odd, then the numerator is odd, so the whole term is odd and everything is fine. But if $r$ is odd, then the numerator is even and the denominator is odd, so the term is even which contradicts the above statement.

Putting $n=2^r+1$ the term equals $\frac{(2^{r+1}+1)}{(2^r+1)(2^r)}$. Finding the highest powers of $2$ I've got $\frac{(2^{r+1}-1)}{(2^r-1)(2^r-1)}$ which is odd.

I'm getting nearly opposite results.

Am I doing something very wrong?

Any help would be highly appreciated.

Answer 1

For any integer $k$ let $v(k)$ be the highest power of $2$ dividing $k$.

Then $v\left((2n-1)!\right)=v\left(2\times 4 \times 6 ...\times (2n-2)\right)=n-1+v\left((n-1)!\right)$. Therefore $$v\left(\frac{(2n-1)!}{(n-1)!n!}\right)=\frac {n-1}{v(n!)}.$$

This completes the proof since $v\left(n!\right)$ is $n-1$ when $n$ is a power of $2$ and is less than $n-1$ otherwise.

N.B. You already know this result for $n$ a power of $2$. For other values of $n$ the result follows easily by induction.

Suppose $n$ is a power of $2$. For $i<n$, $v(n+i)=v(i)$. So, for $k<n$, if $v\left(k!\right)<k-1$ then $$v\left((n+k)!\right)=v\left(n!\right)+v\left(k!\right)<n+k-1.$$

Answer 2

This follows from Lucas' Theorem.

that theorem tells us that $\binom ab$ is divisible by a prime $p$ if and only if one of the base $p$ digits of $b$ exceeds the corresponding digit of $a$.

If $n$ is not a power of $2$ then we can write $$n=2^{k_1}+\cdots + 2^{k_{r-1}}+2^{k_r}$$ where the $k_i$ are strictly decreasing and $r$ is at least $2$. But then $$2n-1=2^{k_1+1}+\cdots + 2^{k_{r-1}+1}+2^{k_r+1}-1=2^{k_1+1}+\cdots + 2^{k_{r-1}+1}+2^{k_r}+\cdots +1$$

We observe that $2^{k_{r-1}}$ is present in the expansion of $n$ but not in the expansion of $2n-1$ so Lucas tells us that $2\,\big |\,\binom {2n-1}n$ when $n$ is not a power of $2$.

The case where $n$ is a power of $2$ is similar and straight forward.

Answer 3

Let $\nu_2(x)$ be the exponent of the highest power of $2$ that divides $x$. By Legendre’s Formula,

\begin{equation}\nu_2\left(\frac{(2n-1)!}{n!(n-1)!}\right)=\sum_{i=0}^\infty\left\lfloor\frac{2n-1}{2^i}\right\rfloor-\left\lfloor\frac{n}{2^i}\right\rfloor-\left\lfloor\frac{n-1}{2^i}\right\rfloor\Rightarrow\label{1}\tag{1}\end{equation}

\begin{equation}\nu_2\left(\frac{(2n-1)!}{n!(n-1)!}\right)=\sum_{i=0}^\infty2^{-i}\left(r_{2^i}(n)+r_{2^i}(n-1)-r_{2^i}(2n-1)\right),\label{2}\tag{2}\end{equation} where $\lfloor\cdot\rfloor$ represents the floor function, and $r_{2^i}$ denotes the least non-negative residue modulo $2^i$.

Every term in $(\ref{2})$ is a positive number times a multiple of $2^i$ greater than $-2^i+1$, and therefore non-negative. Therefore, the problem’s expression will be odd iff every term in $(\ref{2})$ is in fact $0$. That is, iff either $2^i\mid n-1$, or $r_{2^i}(n)\leq 2^{i-1}$ for all $i$.

Any power of two, clearly, always withholds the second condition. Any number that is not a power of two, we can write as $n=k2^\alpha$, for $k>1$ odd. If $2^{\beta-1}<k<2^\beta$, $n$ will withhold neither condition for $i=\alpha+\beta$. This proves what we wanted. $\blacksquare$

Answer 4

So my breakthrough discovery is for when n is a power of 2.

Let's do some rewriting.

$\displaystyle\dfrac{(2n-1)!}{n!(n-1)!}=\dfrac{\dfrac{(2n)!}{2n}}{n! \cdot \dfrac{n!}{n}}=\dfrac{(2n)!}{2 \cdot (n!)^2}!$

And I'll replace $n=2^k$ to yield

$\dfrac{(2^{k+1})!}{2 \cdot ((2^k)!)^2}$

Now the best option is to deduce how many groups of 2 are in the numerator and denominator.

So for a number $\alpha!$, half of the numbers are divisible by 2, half of which are divisible by 4 and so on.

We can make a similar pattern for ourselves.

$2^{k+1}$ has $2^k$ numbers divisible by 2, $2^{k-1}$ divisible by 4 until only one number is divisible by $2^k$. I hope this pattern is easy to follow since it's not easy to type MathJax on a phone.

At the top the number of groups of 2 are

$2^{k+1}+2^k \ldots +1=(2^{k+1}-1)\text{groups}$

The pattern can be repeated for $2^k$ to get $(2^k-1)\text{groups}$. However that denominator is guided by special conditions. There's a power of 2 which makes it double and a factor of 2 which adds 1 more power. This leads to

$2(2^k-1)+1=(2^{k+1}-1)\text{groups}$

See that! The denominator and numerator have the same number of 2s. They therefore cancel out leaving no pairs for our poor fraction.

This thought process took about 24 hours. Peace.

P.S I can assume for the other case that there will always be a 2 somewhere to spare. I hope I can prove it sometime this week.