Processing math: 0%

Spring 2016, problem 13

Consider the binomial coefficients \binom{n}{k}=\frac{n!}{k!(n-k)!}, where k\in\{1,2,\ldots, n-1\}. Determine all positive integers n for which \binom{n}{1},\binom{n}{2},\ldots ,\binom{n}{n-1} are all even numbers.

Comments

Hubert
5 years ago

Hi, I'm Hubert from Paris ... Luca's theorem shows that n=2^q;

using the Wikipedia article notations with p=2 we want N=\binom mn even for 1\leq n\leq m-1,

  • if m is not a power of 2, then m_k=m_j=1 for some j\lt k and the given formula says \binom m{2^j} \equiv \binom 11 (mod\; 2) with n_j=1,\; n_k=0, \; k\neq j, odd;

  • now if m=2^k,\; m_j=0,\; j\lt k and n\lt m\Rightarrow~n_k=0, and at least one of the n_0,n_1,\cdots n_{k-1} is one, putting a 0=\binom 01 in the given product, for each n\in(0,m), making each N even.

Note: this strange \lt is the symbol "less than", can someone fix that ?

I need your help now ... :-(

The browser interprets the < as the start of an html tag or something like that. Use \lt and \leq inside $ signs instead.

Nelix 5 years ago
Nelix
5 years ago

The number n has the required property, if and only if n = 2^k for some positive integer k.

I suspect, there's a nice proof for that, involving the binomial theorem and a little group theory, but all I could come up was this rather calculational Proof:

[The notation \lfloor x \rfloor := floor(x) and \lceil x \rceil := ceil(x) is used throughout.]

For every natural a, define \nu(a) := b, where b is the largest integer, such that 2^b divides a. Or put another way: \nu(a) is the numbert of twos in the prime factorization of a.

A particular case of a result known as Legendre's formula states, that for all a \in \mathbb{N}:

\nu(a!) = \sum_{i=1}^{\infty} \lfloor \frac{a}{2^i} \rfloor

Also, from the definition of the binomial coefficients, we have:

\nu ( \binom{n}{k} ) = \nu(n!) -\nu(k!) - \nu([n -k]!) (*)

Now assume, that n is not a power of 2. So n lies strictly between two powers 2^j and 2^{j + 1} of two, i.e. there are j,r \in \mathbb{N}, with 0 \lt r \lt 2^j, such that n = 2^j + r.

Then \nu(n!) = \nu([2^j + r]!) = \sum_{i=1}^{\infty} \lfloor \frac{2^j + r}{2^i} \rfloor = \sum_{i=1}^{j} 2^{j-i }+\lfloor \frac{r}{2^i} \rfloor = \nu([2^j]!) + \nu(r!). Note, that the second manipulation only works, because we assume, that r \lt 2^j. Plugging this into the equation (*), we get:

\nu ( \binom{n}{2^j} ) = \nu ( \binom{2^j + r}{2^j} ) = \nu([2^j]!) + \nu(r!) - \nu([2^j]!) - \nu(r!) = 0

Therefore \binom{n}{2^j} is odd so that n does not have the property required in the problem statement.

This concludes the first half of the proof. We now assume, that n = 2^j for some j \in \mathbb{N} and prove it does indeed have said property.

Pick a k \in \mathbb{N}, such that 0 \lt k \lt 2^j. Then:

\nu ( \binom{n}{k} ) = \nu ( \binom{2^j}{k} ) = \nu([2^j]!) - \nu([2^j - k]!) - \nu(k!) = \sum_{i=1}^{j} \lceil \frac{k}{2^i} \rceil - \lfloor \frac{k}{2^i} \rfloor. By the definition of the rounding functions, none of the summands is negative and - from 0 \lt k \lt 2^j - the last one is equal to 1. Therefore \nu ( \binom{n}{k} ) >= 1 and so \binom{n}{k} is even. This completes the proof.

As an aside, using the general form of Legendre's formula, the proof takes little modification, to show that:

A prime number p divides all of \binom{n}{1},\binom{n}{2}, \ldots, \binom{n}{n-1} iff n is a power of p.