3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Note: I got lost in your argument, so posted an argument along different lines. Hope it is helpful. $\endgroup$ – lulu Jan 4 at 19:49
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This should be the accepted answer. $\endgroup$ – URL Jan 5 at 5:11
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Are you sure that this is the only method to solve this Question? Because the author of the book didn't really tell us anything about Lucas's theorem. $\endgroup$ – Smiling Crocodile Jan 4 at 19:52
  • 1
    $\begingroup$ Oh, not at all. this is just the way I thought of to prove the result, I'm sure there are other ways to do it. That said, Lucas' Theorem is a great result and well worth learning. $\endgroup$ – lulu Jan 4 at 19:53
  • 1
    $\begingroup$ You mean gcd? each case requires an argument and you have to take some care. It should be clear that any common divisor of $a, b$ is also a divisor of $a-b$ and $a+bn$ for any $n$. The only issue is that you might have created a greater divisor. If, say, $n=0$, then $\gcd (a, a+bn)=a$ regardless of what $b$ was. $\endgroup$ – lulu Jan 4 at 20:00
  • 1
    $\begingroup$ If you don't like the use of $n=0$, use an example like this: $\gcd(15,5)=5$ but $\gcd(15, 15+5\times 3)=\gcd(15,30)=15$. $\endgroup$ – lulu Jan 4 at 20:03
  • 1
    $\begingroup$ No worries. Good luck. $\endgroup$ – lulu Jan 4 at 20:06
1
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How close is my answer to Legendre's formula? $\endgroup$ – Nεo Pλατo Jan 6 at 18:59
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.