Another solution via Lucas's Theorem. Let $n = b_0b_1...b_m$ be it's binary representation. Then we need for any selections $a_0,a_1,...,a_m$ and $c_0,c_1,...,c_m$ such that $a_0a_1...a_m < n$ and $c_0c_1...c_m < n$ we have: $c_m + a_m \equiv \dbinom{b_0}{a_0} \dbinom{b_1}{a_1}...\dbinom{b_m}{a_m} + \dbinom{b_0}{c_0} ... \dbinom{b_m}{c_m} \pmod{2}$ The RHS must be a zeroth degree polynomial in each of $a_0,a_1,...,a_{m-1},c_0,c_1,...,c_{m-1}$ hence $b_0 = b_1 = ... = b_{m-1} = 1$. By similar logic it follows $b_m = 0$ or else the RHS won't vary with $a_m, c_m$, hence we get the desired result of $n = 2^k - 2$ for some $k$.

Let $i = 0$, for all $0 \leqslant j = 2r \leqslant n$, $\left( \begin{gathered} n \\ 2r \\ \end{gathered} \right) + 1$ is even, so $\left( \begin{gathered} n \\ 2r \\ \end{gathered} \right)$ is odd. Denote $n = {\left( {\overline {{n_t}{n_{t - 1}}...{n_1}{n_0}} } \right)_2}, 2r = {\left( {\overline {{k_t}{k_{t - 1}}...{k_1}0} } \right)_2}$, ${n_t} = 1$. By Lucas theorem $\prod\limits_{i = 0}^t {\left( \begin{gathered} {n_i} \hfill \\ {k_i} \hfill \\ \end{gathered} \right)} \equiv \left( \begin{gathered} n \\ 2r \\ \end{gathered} \right) \equiv 1(\bmod 2)$, so $\left( \begin{gathered} {n_i} \hfill \\ {k_i} \hfill \\ \end{gathered} \right) = 1$ for all $0 \leqslant i \leqslant t$, so ${n_0} = 0$. If there exit integer $1 \leqslant s \leqslant t - 1$ satisfies ${n_s} = 0$, we take $2r = {2^s}$, then $\left( \begin{gathered} {n_s} \hfill \\ {k_s} \hfill \\ \end{gathered} \right) = \left( \begin{gathered} 0 \hfill \\ 1 \hfill \\ \end{gathered} \right) = 0$, contradiction. So $n = {\left( {\overline {11...10} } \right)_2} = {2^{t + 1}} - 2$. On the other hand if $n = {\left( {\overline {11...10} } \right)_2}$, because $C_1^0 = C_1^1 = C_0^0 = 1$, for any $i = {\left( {\overline {{a_t}{a_{t - 1}}...{a_1}{a_0}} } \right)_2}$, by Lucas theorem $\left( \begin{gathered} n \\ i \\ \end{gathered} \right) \equiv \prod\limits_{i = 0}^t {\left( \begin{gathered} {n_i} \hfill \\ {a_i} \hfill \\ \end{gathered} \right)} \equiv \left( \begin{gathered} 0 \hfill \\ {a_0} \hfill \\ \end{gathered} \right) \equiv {a_0} - 1 \equiv i-1 (\bmod 2)$, similarly we have $\left( \begin{gathered} n \\ j \\ \end{gathered} \right) \equiv j - 1(\bmod 2)$, so $\left( \begin{gathered} n \hfill \\ i \hfill \\ \end{gathered} \right) + \left( \begin{gathered} n \hfill \\ j \hfill \\ \end{gathered} \right) \equiv i + j(\bmod 2)$. Above all, $n = {2^{t + 1}} - 2$, $t \in {Z^ + }$.

Put $i=i,j=0$ gives us ${n \choose i} \equiv i+1 (mod 2)$. Now $i=1, i=2$ gives us $n \equiv 2 (mod4)$ . Trivially $n=2$ is an answer. so assume $n \geq 4$ Consider $ 2^k \leq n< 2^{k+1}$ for $k \geq 2$ . because $n \equiv 2 (mod 4) $ so $n \leq 2^{k+1}-2$ now consider $n \neq 2^{k+1} -2 $ so $n \leq 2^{k+1} -4$ . put $i=2^k-2$ so $n-i \leq 2^k-2$ . $v_2 (n!) -v_2(i!) -v_2((n-i)!) = \sum ([\frac{n}{2^j}] - [\frac{i}{2^j}] -[\frac{n-i}{2^j}])$ and because $[x+y] \geq [x]+[y]$ so $[\frac{n}{2^j}] - [\frac{i}{2^j}] -[\frac{n-i}{2^j}] \geq 0$ so if ${n \choose i} \equiv 1 (mod2)$ then : $[\frac{n}{2^j}] - [\frac{i}{2^j}] -[\frac{n-i}{2^j}] =0$ for all $j \geq 0$ put $j=k$ .... now if $n=2^ {k+1} -2$ and odd $i$ we have $[\frac{n}{2}] - [\frac{i}{2}] -[\frac{n-i}{2}] \geq 1$ so ${n \choose i} \equiv 0 (mod 2)$ if $i$ is even...it's easy to show that $[\frac{n}{2^j}] - [\frac{i}{2^j}] -[\frac{n-i}{2^j}] =0$....

mahanmath wrote: Note that all the coefficients in RHS is $1$ due to uniqueness of binary representation , and there are exactly $2^s$ term in $RHS$ . So $\frac{n}{2} +1 =2^s$ $\implies$ $\boxed{n=2^{s+1} -2}$ . Excuse me, Can you explain this part...?

threehandsnal wrote: Excuse me, Can you explain this part...? When you expand a product like $\prod_{i=1}^{s} (1+x^{2^{a_i}}) $ , all the term and their exponent are of the form : $x^{2^{a_{i_1}} + 2^{a_{i_2}} + \dots + 2^{a_{i_m}}}$ . So exponent are unique , and it means the coefficients are all $1$ .Hence there are exactly $2^s$ terms in expanded form of $\prod_{i=1}^{s} (1+x^{2^{a_i}}) $ . For example $(1+x^2)(1+x^4)(1+x^{16}) = 1 + x^2 + x^4 + x^6 + x^{16} + x^{18} + x^{20} + x^{22}$ Due to first line of my post , There are exactly $\frac{n}{2} +1$ non-vanishing terms in expansion of $(1+x)^n$ , Because $\binom{n}{2k+1}$ is even Put them together to see $\frac{n}{2} +1 = 2^s$ .

Let $n = \sum_{i=0}^{p} n_i2^i$. Assume $p \ge 2$.Consider the case when $i$ and $j$ both are even. Assume that for some $0<t<p$ we have $n_t = 0$. Set $j= n$ and $i = n + 2^t - 2^p $. So $i+j$ is even but $\binom{n}{n} + \binom{n}{n + 2^t - 2^p}$ is odd. So $n_1 = \ldots = n_t = 1$. Assume that $n_0 = 1$ . Then If $i$ is odd but $j$ is even we get contradiction since $\binom{n}{i} + \binom{n}{j} $ is even while $i+j$ is odd. So $n_0 = 0$ and $n = 2^t - 2$

Proposed by Mehdi E'tesami Fard

with twice applications of pascal's identity ${n\choose i}+{n\choose i+1}={n+1\choose i+1}$ we deduce that all numbers ${n+2\choose i},\quad (1<i<n+2$) must be even! which is a well-known problem. so $n+2=2^k$.

M.SH: Something is missing! There can exist some case (though there aren't) where all $\binom{n+2}{i+1}$'s are even but some $\binom{n+1}{i+1}$'s are even too! Then we have $\binom{n}{i+1}$ and $\binom{n}{i}$ have the same parity.

Consider Pascal's triangle modulo 2, where the 0th row is just 1, the 1st row is 1 1, the 2nd row is 1 0 1 and so on. In order $i + j$ and $\binom{n}{i} + \binom{n}{j}$ to have the same parity for all $0 \leq i,j \leq n$, we need the $n$ row of Pascal's triangle to alternate between 0's and 1's. This is because clearly the 0th entry in the nth row of pascal's triangle is 1, so it then follows that we need every even index in the nth row to also be 1, and every odd index in the nth row to be 0, and it is clear that such a row satisfies the desired condition. But then the next row in pascals triangle must look like 11111...1, and so the row after this must look like 10000000...001. But it is clear from Lucas's theorem or other ways that this only happens when the index of the row is a power of 2, so the n that work are exactly those of the form $2^{k} - 2$ where $k$ is an integer with $k > 1$.

First of all observe that if $n$ is odd, then $i+(n-i)=n$ and $\binom{n}{i}+\binom{n}{n-i}=2\binom{n}{i}$ have different parities. So $n$ must be even. Next, we note that \begin{align*} &\binom n i+\binom n j \text{ and } i+j \text{ have same parity}\\ \iff & \binom n i-i+\binom n j-j \text{ is even}\\ \iff & \binom n i-i \text{ has same parity for all } i\end{align*}Now $\binom n 0-0=1-0$ is odd, so $\binom n i-i$ is odd for all $0\le i\le n$. Now consider $i$ even, so that $\binom n i$ is odd. Suppose $n=(\overline{n_m\cdots n_2n_1})_2$ and $i=(\overline{i_m\cdots i_2i_1})_2$. By Lucas' theorem, we have $$\binom n i\equiv \prod \binom{n_j}{i_j}\pmod{2}$$If some $n_j$ for $1<j<m$ is $0$, then we could choose $i$ with $i_m=0,i_j=1,i_1=0$ so that the above product would be 0, which is impossible. So all digits in the binary representation of $n$ are 1 except the last one, which may be 0 or 1. Thus $n$ is of the form $2^a-1$ or $2^a-2$. But $2^a-1$ is odd. So we must have $$n=2^a-2, a=2,3,4,...$$It is easily checked by Lucas' theorem that it's indeed a solution.

Kummer's theorem kills this question

I have an average length solution, which does employ a lot of similar ideas to the above, and is not especially elegant. The only real advantage I see in it is that while it does not stray too far from the "underlying cause" of the problem, it does skirt the use of Lucas's Theorem or Kummer's Theorem without necessarily proving them.

Easy to see that $\dbinom{n}{i} \equiv i+1 \pmod{2}$ for $0 \le i \le n$ from $\dbinom{n}{0} = 1$. Also $\dbinom{n}{1} = n \equiv 0 \pmod{2}$ so $n$ is even. Now it is easy to see that for odd $i$ we have that $\dbinom{n}{i}$ is even as $v_2(\dbinom{n}{i}) = v_2(\dbinom{n}{i+1} \cdot \frac{i+1}{n-1}) \ge v_2(i+1)-v_2(n-1) \ge 1$ For all even $i$ we need $\dbinom{n}{i}$ to be odd. We can easily show that this condition is equivalent to $v_2(n-k-2) = v_2(k)$. Note $v_2(\dbinom{n}{2}) = v_2(n) - v_2(2) = 0$, and $v_2(\dbinom{n}{4}) = v_2(n)+v_2(n+2)-v_2(2)-v_2(4) = 0$ and etc. Now for some arbitrary even $k$ let $v_2(k) = m$. Then $v_2(n-k-2) = m$ or $n-k-2 \equiv n-2^m-2 \equiv 2^m \pmod{2^{m+1}}$ or $n \equiv -2 \pmod{2^{m+1}}$ So in the range from $0,2,...,n$ pick $k$ such that $v_2(k) = m$ is maximal. Then we must have $n \equiv -2 \pmod{2^{m+1}}$. But note that $0 <n <2^{m+1}$ (or else there exists a $k$ in the range such that $v_2(k) > m$). Thus the only solution is $n = 2^{m+1}-2$

Here is a pure polynomials approach, possibly isomorphic to other solutions but phrased without things like Kummer's Theorem, p-adics, binary representation, etc. Lemma: In $\mathbb{F}_2[x]$, we have: $k$ is a power of two $\iff (1+x)^k=1+x^k$. Proof: The forward direction is clear by induction. For the other direction, write $k=2^m \cdot \ell$ where $\ell$ is odd. Then $(1 + x)^{2^m\ell} = (1+x^{2^m})^\ell$, which upon expansion contains the term $x^{2^m}$. Then $1+x^{2^m\ell}$, too, must contain $x^{2^m}$, meaning $\ell=1$. $\Box$ The condition requires $\binom{n}{i}$ and $i$ to have opposite parity for all $i=1, 2, \dots, n$ (clearly this forces $n$ to be even). Equivalently, we wish to find all even $n$ for which the following polynomial equality holds in $\mathbb{F}_2[x]$: \[(1+x)^n = 1 + x^2 + x^4 + \dots + x^n.\]As $\mathbb{F}_2[x]$ has unique factorization, we may multiply both sides by $(1+x)^2 = 1+x^2$ to obtain the equivalent polynomial equality \[(1+x)^{n+2} = 1+x^{n+2}.\]By the lemma, $n$ must be of the form $2^m-2$, and all of our steps are bidirectional, so all such $n$ work.

Answer: $n=2^k-2$ for $2\leq k\in Z^+$. $i=0$ gives $\binom{n}{i}\equiv i-1(mod \ 2)$ which gives that $\binom{n}{2m-1}$ is even while $\binom{n}{2m}$ is odd.

The problem statement is equivalent to saying $\binom{n}{i}-i$ has the same parity for $0 \le i \le n$. $i=0$ forces these numbers to be odd. Hence this is equivalent to $\binom{n}{i} \equiv i+1 \pmod 2$, id est the $n+1$-th row in the Pascal triangle must be all odd. It's well known that the number of odd integers in the $k$-th row of the Pascal's triangle is $2^{S_2(k)}$, where $S_2(n)$ denotes the sum of digits in base $2$. Hence $n+1=2^{S_2(n+1)}$ which obviously imply $n=2^k-2$ for some $k$. On the other hand, let $n=2+2^2+\dots +2^{k-1}$ and $i=i_0+2i_1+\dots +i_{k-1}2^{k-1}$, Lucas' theorem gives \[\binom{n}{i} \equiv \binom{1}{i_{k-1}} \cdot \binom{1}{i_{k-2}} \cdot \binom{1}{i_1} \cdot \binom{0}{i_0} \pmod 2\]Hence $\binom{n}{i} \equiv \binom{0}{i_0} \equiv i_0+1 \equiv i+1 \pmod 2$.

The answer is all $n = 2^t - 2$, where $t \geq 2$. Claim 1 : $n$ must be even For the sake of contradiction, set $n = 2k + 1$ and take $i = k$ and $j = k + 1$ then $i + j = 2k + 1$ which is odd. Since $\binom{2k+1}{k} = \binom{2k+1}{k+1}$, then their sum must be even, which is contradiction. Claim 2 : $n$ must be on the form $2^t - 2$ Since we showed that $n$ must be even, set $n = 2k$ We compute $v_2(\binom{2k}{k}) = 2k - s_2(2k) - 2(k - s_2(k)) = 2s_2(k) - s_2(2k) = s_2(k) \geq 1$ (Using Legendre Formula, and the fact that $s_2(k) = s_2(2k)$, where $s_2(k)$ is the sum of the digits of $k$ is base $2$) We then compute $v_2(\binom{2n}{n+1}) = 2k - s_2(2k) - (k + 1 - s_2(k+1) + k - 1 - s_2(k-1)) = s_2(k + 1) + s_2(k-1) - s_2(k)$ If $k$ is odd, then $s_2(k + 1) + s_2(k-1) - s_2(k) =s_2(k+1) + 1 \geq 1$ If $k$ is even then $s_2(k + 1) + s_2(k-1) - s_2(k) = s_2(k + 1) - 1$, so for this to be even we need $s_2(k+1) \geq 2$ Now note that if $\binom{2k}{k}$ and $\binom{2k}{k+1}$ are both even, then their sum is even, but $i = k$ and $j = k +1$ give us $i + j = 2k +1$ which is odd. In order to get a valid $n$ we must have $s_2(k+1) = 1$, thus $k+1$ must be a power of two, i.e $k = 2^k - 1$, and thus $n = 2^{k + 1} - 2$ Claim 3 : All $n$ on the form $2^k - 2$, where $k \geq 2$ are solutions This comes from the fact that $\binom{2^k - 2}{a}$ have the opposite parity of $a$, we use Lucas Theorem : By Lucas Theorem : $\binom{2^k - 2}{a} \equiv \binom{0}{n_0} \pmod2$, (Since all the $\binom{1}{n_i}$ vanish because they are all $1$, whatever value $n_i$ takes) where $n_0$ is the number in the "units" place of $n$ in base 2, hence $\binom{0}{n_0} = 0$ if $n_0 = 1$ and $\binom{0}{n_0} = 1$ if $n_0 = 0$ by convention. This is sufficient since if $\binom{n}{i}$, $\binom{n}{j}$ have the same parity, then $i$ and $j$ also have the same parity, so $\binom{n}{i} + \binom{n}{j}$ and $i + j$ are both even. and if $\binom{n}{i}$, $\binom{n}{j}$ have opposite parity , then $i$ and $j$ also have opposite parity, so $\binom{n}{i} + \binom{n}{j}$ and $i + j$ are both odd. which concludes