8. Determine all natural numbers $n \geq 2$ such that for all integers $0 \leq i, j \leq n$:

$$
i+j \equiv\binom{n}{i}+\binom{n}{j} \quad(\bmod 2)
$$

Answer: The solutions are all numbers of the form $n=2^{k}-2$ with $k \geq 2$.
## Solution:

By setting $j=i+1$ (for $i<n$), we obtain

$$
\binom{n+1}{i+1}=\binom{n}{i}+\binom{n}{i+1} \equiv i+i+1 \equiv 1 \quad(\bmod 2)
$$

Thus, since $\binom{n+1}{0}=1$, this means that for all $0 \leq i \leq n+1$ the number $\binom{n+1}{i}$ must be odd. For all $0 \leq i \leq n+1$ we can write

$$
\binom{n+1}{i}=\frac{(n+1) \cdot n \cdot(n-1) \cdot \ldots \cdot(n+2-i)}{1 \cdot 2 \cdot \ldots \cdot i}
$$

so since to go from $i-1$ to $i$ we multiply by $q=\frac{n+2-i}{i}$ and since $\binom{n+1}{i-1}$ and $\binom{n+1}{i}$ are both odd, this means that the irreducible fraction associated with $q$ must be a quotient of two odd numbers. In other words, it is necessary that for all $1 \leq i \leq n+1$ the two numbers $n+2-i$ and $i$ admit the same number of factors 2 in their prime decomposition.

We want to show that $n+2$ is a power of 2. Let $2^{l}$ be the largest power of 2 that is strictly less than $n+2$. In particular, we have $2^{l} \geq \frac{n+2}{2}$. Consider therefore $i=2^{l}$. It must then be that $2^{l}$ divides $n+2-2^{l}$, and since $n+2-2^{l} \leq 2^{l}$, this is only the case if $n+2=2^{l+1}$.

It remains to prove that all numbers of the form $n=2^{k}-2$ are indeed solutions. For this, it suffices to prove that $\binom{n}{i} \equiv i+1(\bmod 2)$ for all $0 \leq i \leq n$. Indeed, if this is the case, we then have

$$
\binom{n}{i}+\binom{n}{j} \equiv i+j+2 \equiv i+j \quad(\bmod 2)
$$

We will prove this property by induction on $i$. For $i=0$ and $i=1$, we clearly have $\binom{n}{i} \equiv$ $i+1(\bmod 2)$. Suppose now that the property has already been proven up to $i-1$. If $i$ is odd, we multiply the previous number by $\frac{n+1-i}{i}$, and since the numerator is even while the denominator is odd, we indeed have that $\binom{n}{i}$ is even. If $i$ is even, we multiply $\binom{n}{i-2}$ by $\frac{n+1-i}{i-1} \cdot \frac{n+2-i}{i}$. The first fraction is a quotient of two odd numbers, and since $n+2=2^{k}$, the second fraction can also be written as a quotient of two odd numbers, so since $\binom{n}{i-2}$ is odd, $\binom{n}{i}$ is also odd.

Another solution: Look at the Sierpinski triangle and notice with equations like above that you need a series of the form $(1,0,1,0,1, \ldots, 1,0,1)$. You can show that such series occur exactly at $2^{n}-2$.