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

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