1
$\begingroup$

True or false, for all primes p > 2, there are an infinite number of positive integers n for which p does not divide ${2n \choose n}$.

I think the answer would be no, but I am not sure. Since n! has all numbers less than n as factors I would assume that p would be among those. Is my reasoning correct?

$\endgroup$
  • $\begingroup$ Your reasoning is not complete anyways... remember that $\binom{2n}{n}=\frac{(2n)!}{(n!)(n!)}$. Even if $p$ is a factor of $n!$, it will also be a factor of the other $n!$ as well as a factor of $(2n)!$, but you have to ask the question of how many times $p$ is a factor of each to find out whether the resulting number is still divisible by $p$ or not. Some of the $p$'s will cancel from numerator and denominator, but how many is not immediately obvious. You then have to argue for or against the existence of infinitely many $n$ for which $p$ does not divide $\binom{2n}{n}$. $\endgroup$ – JMoravitz May 15 '17 at 1:47
  • $\begingroup$ Note for example $\binom{10}{5}=252$ is not divisible by $5$ but is divisible by $7$. $\binom{20}{10}=184756$ again is not divisible by $5$ and is also not divisible by $7$. On the other hand $\binom{16}{8}=12870$ is divisible by $5$ but is not divisible by $7$. Other oddities occur, but the question is if for a given $p$ whether or not there are infinitely many values of $n$ such that $\binom{2n}{n}$ is not divisible by $p$. $\endgroup$ – JMoravitz May 15 '17 at 1:51
  • $\begingroup$ How would I find if there are infinite or finite values? From what I understand from your post, only if the exponent of p in the prime factorization of 2n is greater than two times that of n then p divides the binomial coefficient. $\endgroup$ – shrindle May 15 '17 at 2:33
  • $\begingroup$ Not quite... only if the exponent of $p$ in the prime factorization of $(2n)!$ (don't forget the factorial) is higher than two times that of $n!$ will it be... as for an answer... fractal already gave a start to a satisfactory answer below, and I don't expect there to be a cleaner solution than using legendre's formula. $\endgroup$ – JMoravitz May 15 '17 at 2:55
3
$\begingroup$

The answer is actually yes. For a hint, see Legendre's Formula.

Solution:

For $p$ to not divide $\binom{2n}{n}$, $v_p((2n)!)$ must be exactly $v_p(n!) + v_p(n!) = 2v_p(n!)$ (where $v_a(b)$ is defined as the largest nonnegative integer $k$ such that $a^k$ divides b).

So the question is equivalent to, given a prime $p > 2$, do there exist an infinite number of $n$ such that $v_p((2n)!) = 2v_p(n!)$? I claim the answer is yes. Consider $n = p^i$ for some positive integer $i$. Then by Legendre's Formula, $$v_p(n!) = \Bigg\lfloor\dfrac{n}{p}\Bigg\rfloor + \Bigg\lfloor\dfrac{n}{p^2}\Bigg\rfloor + \cdots + \Bigg\lfloor\dfrac{n}{p^i}\Bigg\rfloor = p^{i-1}+p^{i-2}+\cdots+1,$$$$v_p(2n) = \Bigg\lfloor\dfrac{2n}{p}\Bigg\rfloor + \Bigg\lfloor\dfrac{2n}{p^2}\Bigg\rfloor + \cdots + \Bigg\lfloor\dfrac{2n}{p^i}\Bigg\rfloor \\ = 2p^{i-1}+2p^{i-2}+\cdots+2 = 2v_p(n!),$$ as desired. Since there are infinitely many powers of $p$, the conclusion follows.

The key idea here is that there are no powers of $p$ between $p^i$ and $2p^i$. This only works when $p > 2$, and fails for $p = 2$. In fact, $2$ divides $\binom{2n}{n}$ for every positive integer $n$, which you can use $v_2$ and Legendre's formula to prove.

$\endgroup$
  • $\begingroup$ what exactly is $v_p$? $\endgroup$ – shrindle May 15 '17 at 1:58
  • $\begingroup$ $v_p(m)$ basically counts the exponent of $p$ in the prime factorization of $m$. For instance, $v_2(24) = 3$, $v_3(81) = 4$, and $v_5(1001) = 0$. It is very useful notation! $\endgroup$ – fractal1729 May 15 '17 at 1:59
  • $\begingroup$ Can you really pull the 2 out of the floor function? Wouldn't that change the values? For example ⌊2*1.5⌋=3 while 2⌊1.5⌋=2 $\endgroup$ – shrindle May 15 '17 at 2:05
  • 1
    $\begingroup$ @shrindle notice that he started with "Consider $n=p^i$ for some positive integer $i$." Ordinarily your complaint would be valid, but since $\frac{n}{p^k}=p^i/p^k=p^{i-k}$ is an integer for all values of $k\leq i$ it follows that $\lfloor \frac{2n}{p^k}\rfloor = \frac{2n}{p^k}$ since it is an integer, and for convenience, we rewrite again with floor signs $\dots = 2\lfloor \frac{n}{p^k}\rfloor$. Now... consider the case where $k>i$... each term would be less than one, thus the floor is zero and so is often omitted from the expression (note his expression ended at $p^i$) $\endgroup$ – JMoravitz May 15 '17 at 3:01
  • $\begingroup$ Nice elaboration @JMoravitz, thanks. Another thing I should have noted in the solution is why it only works for $p > 2$; I will edit that in. $\endgroup$ – fractal1729 May 15 '17 at 12:14

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.