AoPS - Problem

that one was quite tough Claim: there exist such $n$ if and only if $\binom{n}{i} \equiv i +1(mod 2)$, $0<i<n$ Proof: $\binom{n}{i} \equiv i - \binom{n}{0} \equiv i-1\equiv i+1(mod 2)$ Let $n=2^p+q$, $0<q<2^p$ Take a look on $\binom{n}{2^p-2}=\frac{(2^p +q)...(q+3)}{(2^p-2)...1}$ Note that $v_2$ of denominator is $\sum_{i=0}\lfloor \frac{2^p - 2}{2^i}\rfloor$ (Legendre's formula) Note that nominator contains $2^p$ number, then if $q+3\le 2^p$ $\binom{n}{2^p-2}$ is even and since $2^p -2$ is even we get contradiction There are two cases 1)$n=2^p - 1$, obviously does not satisfy 2)$n=2^p-2$ $\binom{2^p-2}{i} = \frac{(2^p-2)...(2^p-i-1)}{i!}$ Note that $ord_2(2^p-i)=ord_2(i)$ and so $v_2$ of the nominator is greater that in denominator. So $\binom{2^p-2}{i}$ is even only if $i$ is odd, so $n =2^p-2$ satisfies the condition