### 2019 IMO SL #C1

The infinite sequence $a_0,a _1, a_2, \dots$ of (not necessarily distinct) integers has the following properties: $0\le a_i \le i$ for all integers $i\ge 0$, and$\binom{k}{a_0} + \binom{k}{a_1} + \dots + \binom{k}{a_k} = 2^k$for all integers $k\ge 0$. Prove that all integers $N\ge 0$ occur in the sequence (that is, for all $N\ge 0$, there exists $i\ge 0$ with $a_i=N$).

We claim that for any $n \in \mathbb{Z},$ we have $$\{a_1, a_2, \dots a_n\} = \{0,1,\dots ,q\}\cup\{0,1, \dots ,n-q-1\},$$where $q$ is a integer.

We will proceed with induction.

Base Case: If $n=0$, we must have $\{a_0\} = \{0\},$ as needed.

Inductive Step: Assume we have that $$\{a_1, a_2, \dots, a_{n-1}\} = \{0, 1, \dots, k\} \cup \{0, 1, \dots n-k-2\}$$for some $k$. Then, \begin{align*} 2^n &= \sum_{i}\binom{n}{a_i} \\ &=\left( \binom{n}{0} + \dots + \binom{n}{k} \right) + \left(\binom{n}{0} + \dots + \binom{n}{n-k-2} \right) + \binom{n}{a_n} \\ &= \left(\binom{n}{0} + \dots + \binom{n}{k} \right) + \left( \binom{n}{k+2} + \dots + \binom{n}{n} \right) + \binom{n}{a_n}\\ &= 2^k - \binom{n}{k+1}+\binom{n}{a_n}, \end{align*}where the third line is obtained from ${n \choose r} = {n \choose n-r},$ and the the fourth from the well-known fact that $\sum_{r=0}^{n} {n \choose r} = 2^n.$ Thus, $\binom{n}{k+1}=\binom{n}{a_n},$ and $a_n = k+1,$ or $n-k-1,$ as desired. $\square$