Replace $k$ with $n$. The key is to characterize all possible tuples $(a_0,\ldots,a_n)$ that are possible for a given $n\ge 0$. WLOG the tuple is always sorted in nondecreasing order. Claim: The possible tuples $(a_0,\ldots,a_n)$ can be characterized as follows: choose some $k\in [0,\lceil n/2 \rceil]$. Then the tuple for this $k$ is \[ (0,0,1,1,2,2,\ldots,k-1,k-1, \ k,k+1,k+2,\ldots,n-k)\]where $k=0$ corresponds to no initial pairing. Proof: Induct on $n$. For $n=0$, the only possible tuple is $(0)$, as expected. Suppose we have a tuple $(a_0,\ldots,a_n)$ corresponding to some $k$. Then for $(a_0,\ldots,a_{n+1})$, we tack on the $a_{n+1}$ and sort. We will show that either $a_{n+1}=k$; which corresponds to creating a pair with the currently since $k$, or $a_{n+1}=n+1-k$; which corresponds to tacking on a new single at the end of the existing tuple. This will prove the induction. We have \begin{align*} 2^{n+1}- \binom{n+1}{a_{n+1}} &= \binom{n+1}{a_0}+\cdots+\binom{n+1}{a_n} \\ &= 2\left[ \binom{n+1}{0}+\cdots+\binom{n+1}{k-1}\right] + \binom{n+1}{k}+\cdots+\binom{n+1}{n-k} \\ &= \left[ \binom{n+1}{0}+\cdots+ \binom{n+1}{k-1}\right] + 2^{n+1}-\left[\binom{n+1}{0}+\cdots+\binom{n+1}{k} \right] \\ &= 2^{n+1} - \binom{n+1}{k}. \end{align*}Therefore, $a_{n+1}=k$ or $a_{n+1}=n+1-k$, as claimed. If $n$ is even, then for $k=n/2$, we can get to $k=n/2+1$ as well as $k=n/2$ for $n+1$. That is, we can go from $(0,0,1,1,\ldots,n/2-1,n/2-1,n/2)$ for $n$ even to \begin{align*} k=n/2 &: (0,0,1,1,\ldots,n/2-1,n/2-1,n/2,n/2) \\ k=n/2+1 &: (0,0,1,1,\ldots,n/2-1,n/2-1,n/2,n/2+1). \end{align*}This allows us to generate an increasing number of tuples as $n$ increases. $\blacksquare$ Now any tuple $(a_0,\ldots,a_n)$ contains one number at least $\lfloor n/2 \rfloor$. Therefore, the infinite sequence $a_0,a_1,\ldots,$ will contain every nonnegative integer.

By induction we will actually classify all sequences: Claim: For any integer $n$, we have an equality of multisets \[ \{a_0, \dots, a_n\} = \{0,1,\dots,a\} \cup \{0,1,\dots,b\} \]for some integers $a$ and $b$ with $a+b=n-1$ (with the empty set used for $a=-1$ or $b=-1$). Proof. Suppose $\{a_0, \dots, a_{n-1}\} = \{0,1,\dots,p\} \cup \{0,1,\dots,q\}$ with $p+q=n-2$. Then \begin{align*} 2^n &= \sum_i \binom{n}{a_i} = \left[ \binom{n}{0} + \dots + \binom{n}{p} \right] + \left[ \binom{n}{0} + \dots + \binom{n}{q} \right] + \binom{n}{a_n} \\ &= \left[ \binom{n}{0} + \dots + \binom{n}{p} \right] + \left[ \binom{n}{n} + \dots + \binom{n}{p+2} \right] + \binom{n}{a_n} \\ &= 2^n -\binom{n}{p+1} + \binom{n}{a_n}. \end{align*}Hence $\binom{n}{p+1} = \binom{n}{a_n}$. From here we conclude either $a_n = p+1$ or $a_n = n-(p+1) = q+1$, as needed. $\blacksquare$

We say that a $k+1-$tuple $a_0,a_1,\ldots,a_{k+1}$ is asdf if for odd $n,$ for all $0\leq i\leq \frac{n-1}{2}$ there are exactly two terms of the form $\frac{n}{2}\pm (i+\frac{1}{2}),$ and for even $n,$ for all $1\leq i\leq \frac{n}{2}$ there are exactly two terms of the form $\frac{n}{2}\pm i$ and $\frac{n}{2}$ is also included. We prove that all tuples must be asdf, and we prove this by induction. Claim: $0$ is $asdf.$ Proof: $a_0$ must be $0.$ Claim: If $k$ is asdf, then $k+1$ must also be asdf. Proof: If two elements $i,i$ are the same you can treat one of them as $(k+1)-i$ for the purposes of our sum. Now we are just missing a copy of either $\lfloor\frac{n+1}{2}\rfloor$ or $\lceil\frac{n+1}{2}\rceil,$ whichever we want to make $a_{k+1}.$ Obviously the set $\{0,1,2,\ldots,k+1\}$ is asdf. Since undoing our temporary transformation maintains the asdfness of the set. Now this asdf lemma shows that either $\lfloor\frac{n}{2}\rfloor$ or $\lceil\frac{n}{2}\rceil$ must appear, so the sequence is unbounded.

This was also Canada IMO TST # 1

Claim: $\forall k\in\mathbb{Z}_{0}$ $ \exists t\in\{0,1,\dots, k\}$ $:$ $\{a_0,a_1,a_2,\dots ,a_k\} = \{0,1,\dots, t\} \cup \{0,1,\dots, k-t-1\}$ Proof:We prove this by induction on $k$. For $k=0$ we have $\{a_0\} = {0}\cup \emptyset$. Suppose it is true for $k$. $$\binom{k+1}{a_0} + \binom{k+1}{a_1} + \cdots + \binom{k+1}{a_k} + \binom{k+1}{a_{k+1}} = 2^{k+1} = \binom{k+1}{0} + \binom{k+1}{1} + \cdots + \binom{k+1}{k+1}$$By the induction hypothesis \begin{align*} \binom{k+1}{0} + \binom{k+1}{1} + \cdots + \binom{k+1}{k+1} = \binom{k+1}{a_0} + \binom{k+1}{a_1} + \cdots + \binom{k+1}{a_k} + \binom{k+1}{a_{k+1}} = \\ \qquad = \binom{k+1}{0} + \binom{k+1}{1} + \cdots + \binom{k+1}{t} + \binom{k+1}{0} + \binom{k+1}{1} + \binom{k+1}{k-t-1} + \binom{k+1}{a_{k+1}} = \\ \qquad = \binom{k+1}{0} + \cdots \binom{k+1}{t} + \binom{k+1}{t+2} +\cdots + \binom{k+1}{k+1} + \binom{k+1}{a_{k+1}}. \end{align*}$\implies \binom{k+1}{a_{k+1}} = \binom{k+1}{t+1}\implies a_{k+1} = t+1$ or $a_{k+1}= k+1-(t+1) = k-t. $ If $a_{k+1} = t\implies \{a_0,a_1,a_2,\dots ,a_{k+1}\} = \{0,1,\dots, t+1\} \cup \{0,1,\dots, (k+1)-(t+1)-1\}$, and if $a_{k+1} = t-k\implies \{a_0,a_1,a_2,\dots ,a_{k+1}\} = \{0,1,\dots, t\} \cup \{0,1,\dots, (k+1)-t-1\}.\square$ Thus, $a_0, a_1, \dots$ can be separated into two sequences of the form $0,1,\dots$. Therefore, at least one of these sequences is infinite and contains every non-negative integer.

We are going to prove inductively the existence of a second sequence $b_0,b_1,b_2,...,b_n,...$ such that for every $n,k$ we have that : $$\binom{n+k}{a_n}+\binom{n+k}{a_{n+1}}+...+\binom{n+k}{a_{n+k}}=\binom{n+k}{b_n}+\binom{n+k}{b_n+1}+...+\binom{n+k}{b_n+k}$$obviously $b_0=0$ and the above holds . Now to get the next term $b_{n+1}$ from $b_n$: We have $\binom{n}{a_n}=\binom{n}{b_n}$ so either -$a_n=b_n$ for every $k$ $$\binom{n+1+k}{a_n}+...+\binom{n+1+k}{a_{n+1+k}}=\binom{n+1+k}{a_n}+...+\binom{n+1+k}{b_n+1+k}$$$$\binom{n+1+k}{a_{n+1}}+...+\binom{n+1+k}{a_{n+1+k}}=\binom{n+1+k}{b_{n}+1}+...+\binom{n+1+k}{b_n+1+k}$$in this case we can set $b_{n+1}=b_n+1$ -$a_n=n-b_n$ likewise the term $\binom{n+1+k}{a_n}$ will cancel with $\binom{n+1+k}{b_n+1+k}$ and then we set $b_{n+1}=b_n$. So : for every $n$ note that $(a_0=b_0=0)$ $ b_{n+1}=\left\{\begin{array}{ll} b_n+1, & \text { if } a_n=b_n \\ b_n, & \text { if } a_n=n-b_n \end{array}\right.$ Set $c_n=n-b_n$ $(b_0,c_0)=(0,0)$ from $(b_n,c_n)\to (b_{n+1},c_{n+1}) $ either $a_n=b_n$ and $(b_{n+1},c_{n+1})=(b_n+1,c_n)$ or $a_n=c_n$ and $(b_{n+1},c_{n+1})=(b_n,c_n+1)$ For any $m=0,1,2,3,...$ at some point either $b_k=m$ and $c_k\le m$ or vice versa . We get either $a_k=b_k=m$ or $a_k=c_k$ and $c_{k+1}$ will increase by one and in this case after a number of steps we will get some $(b_{k'},c_{k'})=(m,m)$ and $a_{k'}=m$. The above shows that every number $m$ will inevitably appear in the sequence $a_0,a_1,...$.

It clearly suffices to show the following: Claim: All possible sequences are formed by "interweaving" two copies of $0,1,2, \dots$ That is, we can color every term red or blue such that the red and blue subsequences are both exactly $0,1,2, \dots$ Proof: We induct, assuming that we can color the terms $a_0, a_1, \dots a_k$ as described above. The base case is obvious. Let the red numbers be $0,1,2, \dots , r$ and the blue terms be $0,1,2, \dots b$. Note $r+b=k-1$; thus we have \begin{align*} 2^{k+1} &= \binom{k+1}{a_0}+ \dots + \binom{k+1}{a_k}+ \binom{k+1}{a_{k+1}} \\ &= \left( \underbrace{\binom{k+1}{0}+ \dots +\binom{k+1}{r}}_{\text{red terms}} \right) + \left( \underbrace{\binom{k+1}{k+1}+ \binom{k+1}{k} + \dots + \binom{k+1}{k+1-b}}_{\text{blue terms}} \right)+\binom{k+1}{a_{k+1}} \\ \end{align*}It's now obvious (since $r+b=k-1$) that the only possibilities are $a_{k+1}=r+1$ or $a_{k+1}=b+1$. We're done.

Call $a_i$ good if it is the first appearance of that value in the sequence $(a)$, and bad otherwise. Define the set $A_k$ as the set containing all good $a_i$ for $0 \le i \le k$ and $B_k$ as the set containing all bad $a_i$ for $0 \le i \le k$. We claim that $A_k$ and $B_k$ are of the form $\{0, 1, \dots, t \}$ and $\{0, 1, \dots, k - t - 1\}$ for some $t$. Proceed with induction; if $k=0$, then $A_0 =\{0\}$ and $B_0$ is the empty set, so this works (assuming a generous interpretation of the definitions). Now assume the claim for $k$; we will prove it for $k+1$. Now summing through the good and the bad $a_i$, we have \begin{align*} 2^{k+1} &= \left( \binom{k+1}{0} + \dots + \binom{k+1}{t} \right) + \left( \binom{k+1}{0} + \dots + \binom{k+1}{k - t - 1} \right) + \binom{k+1}{a_{k+1}} \\ &= \binom{k+1}{0} + \dots + \binom{k+1}{t} + \binom{k+1}{t+2} + \dots + \binom{k+1}{k+1} + \binom{k+1}{a_{k+1}} \\ &= 2^{k+1} - \binom{k+1}{t+1} + \binom{k+1}{a_{k+1}} \end{align*}It follows that $a_{k+1} = t+1$ or $a{k+1} = k-t$ (by convexity of choose or something). The former implies that $a_{k+1}$ must be good since its value isn't in $A_k$ already, so $A_{k+1} = \{0, 1, \dots, t+1\}$ and $B_{k+1}$ is $\{0, 1, \dots, k - t - 1\} = \{0, 1, \dots, (k + 1) - (t + 1) - 1\}$. The latter implies that $a_{k+1}$ is bad or equal to $t+1$ since by definition we must have \[ t \ge k - t - 1 \implies k - t \le t + 1.\]The $t+1$ case is just the above. Otherwise, $a_{k+1}$ is bad so $A_{k+1}$ is $\{0, 1, \dots, t \}$ and $B_{k+1}$ is $\{0, 1, \dots, k - t - 1, k - t\} = \{0, 1, \dots, (k + 1) - t - 1\}$ Now to finish, we must show that $A_k$ approaches $\{0, 1, 2, \dots \}$ as $k \to \infty$, but clearly $|A_k| \ge |B_k|$ and $|A_k| + |B_k| = k+1$, hence $|A_k| \ge \frac{k}{2}$, i.e. it tends to infinity. Furthermore $A_k$ is always of the form $\{0, 1, \dots, t\}$ for some $t$, so it must approach $\{0, 1, 2, \dots \}$, as desired. $\blacksquare$

Claim: 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. Proof: 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. So, we are done. $\blacksquare$

I don't really understand @dchenmathcounts solution. I don't think their characterization is rigid enough. By their given definition, shouldn't $0, 5, 1, 1, 2, 2$ be an $asdf$ tuple for $n=5$? However, this does not imply that tuple for $n=6$ is $asdf$? I think that more explanation might be needed.

Suppose that $A_n$ for a nonnegative integer $n$ is the set of $a_i$ for $0\le i\le n$. Let a good situation be a situation where $$A_n=\{0,1,\ldots,j\}\cup \{0,1,\ldots,k\}$$for integers $j$ and $k$ so that $-1\le j \le k$. (Set the convention so that if a variable is $-1$, the corresponding set is empty.) Notice that $A_n$ contains $n+1$ elements, and the two individual sets contain $j+1+k+1=j+k+2$, so $$j+k+2=n+1\Rightarrow j+k=n-1.$$Claim: For all $n$, $A_n$ is always in a good situation. Proof. We will prove this using induction on $n$. The base case $n=0$ is trivial, as $A_0=\{0\}$, corresponding to $j=-1,k=0$. Suppose that $A_{n-1}$ is in a good situation. Then $$A_{n-1}=\{0,1,\ldots,j\}\cup \{0,1,\ldots,k\}$$must hold for some integers $-1\le j\le k$ so that $j+k=n-2$. For $A_n$ to remain in a good situation, we must have either $a_n=j+1$ or $a_n=k+1$. We claim that this must be the case. Indeed, plugging in $n$ into the condition, we get \begin{align*} 2^n &=\binom{n}{a_0}+\binom{n}{a_1}+\ldots+\binom{n}{a_n} \\ &= \left(\binom{n}{0}+\binom{n}{1}+\ldots+\binom{n}{j}\right)+\left(\binom{n}{0}+\binom{n}{1}+\ldots+\binom{n}{k}\right)+\binom{n}{a_n} \\ &= \left(\binom{n}{0}+\binom{n}{1}+\ldots+\binom{n}{j}\right)+\left(\binom{n}{n}+\binom{n}{n-1}+\ldots+\binom{n}{n-k}\right)+\binom{n}{a_n} \\ &= \left(\binom{n}{0}+\binom{n}{1}+\ldots+\binom{n}{j}\right)+\left(\binom{n}{n}+\binom{n}{n-1}+\ldots+\binom{n}{j+2}\right)+\binom{n}{a_n} \\ &=2^n-\binom{n}{j+1}+\binom{n}{a_n}. \end{align*}Therefore we get that $$\binom{n}{j+1}=\binom{n}{a_n},$$and therefore either $a_n=j+1$ or $a_n=n-(j+1)=k+1$. Therefore $A_n$ is also a good situation, and we are done. $\blacksquare$ Suppose for contradiction that a nonnegative integer $x$ never appeared in the sequence. Then consider the set $A_{2x}$. Because it is good, it can be expressed as $$\{0,1,\ldots,j\}\cup \{0,1,\ldots,k\}, j+k=2x-1.$$By the Pigeonhole Principle, we must either have $j\ge x$ or $k\ge x$, meaning that either the set $\{0,1,\ldots,j\}$ or $\{0,1,\ldots,k\}$ contains $x$, contradiction. The proof is complete.

Define "nice at $j$" to mean satisfying the problem condition up to $j$. $\textbf{Claim: }$ Any sequence $a_i$ satisfies that $\forall k$, for some $r$, then \[a_0\ldots a_k = \text{some permutation of }(0,0,1,1,\ldots ,r-1,r-1,r,r)+(r+1,\ldots k-r-1)\]$\textbf{Proof: }$ Inducting on $k$. The base case is clearly true because $a_0=0$. Note that for all $r$, the described type of sequence satisfies niceness. Then, for the inductive step, note that both adding a $r+1$ or adding a $k-r$ satisfy niceness at $k+1$. For each config, there are at most 2 valid moves at a time since $\binom{k+1}{x}=\binom{k+1}{y}\Longleftrightarrow x=\pm y$. Thus, the only 2 moves that preserve niceness keep the sequence in the form we've described, so our induction is complete. $\square$. This claim clearly implies that all nonnegatives appear, so we are done $\blacksquare$.

light up the sky at night, there in the dark... you can hide your fear

Claim 1. The sequence $\{ a_0, a_1, \dots, a_n \}=\{0, 1, 2, \dots, x\} \cup \{0, 1, 2, \dots, y\}$ where $x+y=n-1$. Proof. We will use induction to prove this. It is easy to see that this is true for $n=0$ and now assume that this is true for $n-1$. This means that $\{ a_0, a_1, \dots, a_{n-1} \} = \{0, 1, 2, \dots, x\} \cup \{0, 1, 2, \dots, y\}$ with $x+y=n-2$. Now we have \begin{align*} 2^n&=\left(\binom{n}{0}+\binom{n}{1}+\dots+\binom{n}{x}\right)+\left(\binom{n}{0}+\binom{n}{1}+\dots+\binom{n}{y}\right)+\binom{n}{a_n} \\ &= \left(\binom{n}{0}+\binom{n}{1}+\dots+\binom{n}{x}\right)+\left(\binom{n}{x+2}+\binom{n}{x+3}+\dots+\binom{n}{n}\right)+\binom{n}{a_n} \\ &= 2^n - \binom{n}{x+1} + \binom{n}{a_n} \end{align*}which means that $a_n$ is equal to $x+1$ or $n-x-1=y+1$ as desired. $\blacksquare$ We are actually done because this means that $\{ a_0, a_1, \dots, a_n \}$ must contain some number $\ge \lfloor \frac{n}{2} \rfloor$.

We will prove that $\{0,1,2,...,n\} \subseteq \{a_0,a_1,a_2,...,a_{2n}\}$ for all $n \in \mathbb{Z}_{\geq 0}$, with each $0,1,2,...,n$ appearing at most two times. To show this, we induct on $n$, the basecases are easy. Assume for the sake of contradiction that $n+1$ does not appear in $\{a_0,a_1,a_2,...,a_{2n+2}\}$, hence $n+1$ does not appear in $\{a_0,a_1,...,a_{2n}\}$. By inductive hypotesis, the set $\{a_0,a_1,a_2,...,a_{2n}\}$ satisfies that all but one element among $\{0,1,2,...,n\}$ appears twice. Say that $k$ just appears once in the set $\{a_0,a_1,a_2,...,a_{2n}\}$. Therefore, since $$\binom{2n+1}{a_0}+\binom{2n+1}{a_1}+...+\binom{2n+1}{a_{2n+1}}=2^{2n+1}$$and each element from $\{0,1,2,...,n\}$ without $\{k\}$ appears twice, we must have that $a_{2n+1}=k$. Now, since each $0,1,2,...,n$ appears twice in $\{a_0,a_1,...,a_{2n+1}\}$, and $\binom{2n+2}{a_0}+\binom{2n+2}{a_1}+...+\binom{2n+2}{a_{2n+2}}=2^{2n+2}$, it follows that $a_{2n+2}$ must be $n+1$, which is a contradiction by our assumption. Therefore, the claim is proved, so $\{0,1,2,...,n\} \subseteq \{a_0,a_1,a_2,...,a_{2n}\}$ for all $n \in \mathbb{Z}_{\geq 0}$, which implies that all integers $N \geq 0$ occur in the sequence. $\blacksquare$

The crux lies in observing that the subsequence $\{ a_0, a_2, \dots a_k \}$ is effectively $\{1, 2, 3, \dots , x \} \cup \{1, 2, 3, \dots , k - x - 1 \}$ for some $x \in \mathbb{Z}$ with $x = k - 1.$ To demonstrate the aforementioned property, we will use induction. The base case, namely when $k = 0$, is self-evident. As for the induction step, assume that $\{ a_0, a_2, \dots a_k \} = \{1, 2, 3, \dots , x \} \cup \{1, 2, 3, \dots , k - x - 1 \}$ for integer $x.$ Then, we must have that: \begin{align*} \sum_{i = 0}^{k + 1} \binom{k + 1}{a_i} &= \binom{k + 1}{a_{k + 1}} + \sum_{i = 0}^{x} \binom{k + 1}{i} + \sum_{i = 0}^{k - x - 1} \binom{k + 1}{i} \\ &= \binom{k + 1}{a_{k + 1}} + \sum_{i = 0}^{x} \binom{k + 1}{i} + \sum_{i = x + 2}^{k} \binom{k + 1}{i} \\ &= \binom{k + 1}{a_{k + 1}} + 2^{k + 1} - \binom{k + 1}{x + 1}. \end{align*}It thereby follows that $a_{k + 1} = x + 1$ or $a_{k + 1} = k - x.$ Then, $\{ a_1, a_2, \dots a_k \} = \{1, 2, 3, \dots x + 1 \} \cup \{ 1, 2, 3, \dots , k - x - 1 \}$ or $\{1, 2, 3, \dots x \} \cup \{1, 2, 3, \dots k - x \}$ respectively. Either way, the property holds true.

In fact, we claim that we can characterize all possible valid sequences. We claim that for any $k$, the valid multiset $\{a_0,a_1,\ldots,a_k\}$ must be the combination of the two sets $\{0,1,\ldots,a\}$ and $\{0,1,\ldots,b\}$ where (WLOG) $a \leq b$ and $a+b+2 = k+1$ (because there must be $k+1$ elements in both sets). For example, if $k = 4$, here are the valid multisets: $\{0,1,2,0,1\}$ $\{0,1,2,3,0\}$ $\{0,1,2,3,4\}$ To prove this we use induction. The base case $k = 0$ is obvious. Now, say that for some $k = l-1$ all multisets are of this form. Say that the previous multiset was $\{0,1,\ldots,a,0,1,\ldots,b\}$. Then, $a+b+1 = l-1$, so we have \[ \sum\limits_{i=0}^{l} \binom{l}{a_i} = \binom{l}{a_l} + \left(\sum\limits_{i=0}^{a} \binom{l}{i} \right) + \left(\sum\limits_{i=0}^{b} \binom{l}{l-i} \right) = \binom{l}{a_l} + 2^l - \binom{l}{a+1} \]so we must have $a_l = a+1$ or $a_l = l-(a+1) = b+1$, which clearly implies that the new multiset is valid (as it continues one of the sequences $0,1,\ldots,a$ or $0,1,\ldots,b$), which finishes.

Here's a rough sketch: we can swap $a_k$ and $a_{k+1}$ if they sum to $k$; now we can always keep swapping until we get a sequence like $0,0,1,1,2,2,3,3,4,5,6,7,8,\dots$.

We characterize all such sequences, as follows: Claim: On multisets of terms in the sequence, $\{a_0, a_1, \dots, a_n\} = \{0, 1, \dots, r - 1\} \cup \{0, 1, \dots s - 1\}$ for some integers $r + s = n + 1$. Proof: Proceed by induction on $n$. The result is trivially true for $n = 0$. Assume the result holds for $n = k - 1$. Then, \begin{align*} \binom{k}{a_k} &= 2^k - \left(\binom{k}{a_0} + \binom{k}{a_1} + \cdots + \binom{k}{a_{k-1}}\right) \\ & = 2^k - \left(\binom{k}{0} + \binom{k}{1} + \cdots + \binom{k}{r - 1}\right) - \left(\binom{k}{0} + \binom{k}{1} + \cdots + \binom{k}{s - 1}\right) \\ & = 2^k - \left(\binom{k}{0} + \binom{k}{1} + \cdots + \binom{k}{r - 1} + \binom{k}{r + 1} + \cdots + \binom{k}{k - 1} + \binom{k}{k}\right) \\ & = \binom{k}{r} \end{align*}Hence $a_k = r$ or $a_k = k - r = s$. The result is true for $n = k$. The claim is proven by induction. $\square$ Therefore, all integers $N \geq 0$ occur within the first $2N + 1$ terms of the sequence.

Define the sets $B$ and $C$ such that: $a_{i}\in B\Leftrightarrow a_{i}$ first appearance in $\{a_{i}\}$. $a_{i}\in C\Leftrightarrow a_{i}$ second appearance in $\{a_{i}\}$. Claim: at any moment if $\left|B\right|=l, \left|C\right|=k$ then $a_{k+l}\in \{l,k\}$. Proof: We proceed by induction. we have $a_{0}=0$ and assume the claim is true $\forall i \in \{0,1,...k+l-1\}$ , then: \begin{align*} &\binom{k+l}{a_{k+l}}+\sum_{0}^{k-1}\binom{k+l}{i}+ \sum_{0}^{l-1}\binom{k+l}{i}=2^{k+l}\\ &\Leftrightarrow \binom{k+l}{a_{k+l}}+\sum_{0}^{k-1}\binom{k+l}{i}+ \sum_{k+1}^{k+l}\binom{k+l}{i}=\sum_{0}^{k+l}\binom{k+l}{i}\\ &\Leftrightarrow \binom{k+l}{a_{k+l}}=\binom{k+l}{k}\\ &\Leftrightarrow a_{k+l} \in \{k,l\} \end{align*}so the claim is true by induction. Hence we deduced that: $\bullet$ Each natural value appears at most twice in $\{a_{i}\}_{i\geq 0}$. $\bullet$ For any moment if we have $\left | B \right |=l$ then $\forall 0 \le i< l$ we have $i \in B$. And since $B$ is not bounded above, we get the desired result. $\blacksquare$

WRONG $ $

Define a naughty sequence as a sequence of nonnegative integers $b_0,b_1,\dots,b_n$ such that $\binom{n}{b_0}+\binom{n}{b_1}+\dots+\binom{n}{b_n}=2^n$ and $b$ doesn't contain a total of exactly two $0$s and $(n)$s, or a total of exactly two $1$s and $(n-1)$s, $\dots$, until one $\frac n2$ if $n$ is even and a total of exactly two $\left(\frac{n-1}2\right)$s and $\left(\frac{n+1}2\right)$s if $n$ is odd. Basically, when the sequence doesn't follow the "standard" way to sum to $2^n$. Lemma 1. For any nonnegative integer $k$, there must be an $n$ such that neither $k$ nor anything above it appears in the first $n$ terms of the sequence, $k=a_n$, and the subsequence $a_0,a_1,\dots,a_n$ is not naughty. Proof. We use strong induction. The base case is just $n=0$. So, we assume that this works for $k$. Then the first $n+1$ terms of the sequence are all $\le k$, and must contain each of $0,1,\dots,k$(if not, then $k$ shouldn't have appeared yet). Then, to be a non-naughty subsequence, we must have the rest of the terms be $0,1,\dots,n-k-1$. It is then clear that $a_{n+1}$ is either $n-k$ or $k+1$. If it is $n-k$, the next has to be $n-k+1$, etc, until both options are $k+1$, so we choose $k+1$, noting that nothing above it has been chosen. If we chose $k+1$ at any step beforehand, that's also fine. Throughout the entire process, the sequence stays not naughty. This completes our induction, and the wanted result follows.

both sides are all teams with n people

We give the following sufficient characteristic of the sequence. Claim. For every integer $k\geq 0$ there exist such integer $0\leq l\leq \left\lfloor \frac{k+1}{2} \right\rfloor$ that holds the equality of multisets $$\left \{ a_0,a_1,\dots ,a_k\right \} = \left \{ 0,1,\dots ,l-1\right \} \cap \left \{ 0,1,\dots ,k-l\right \} .$$Proof. Induct on $k$. Clearly $a_0=0,$ so the base case $k=0$ is trivial. Next, by the inductive hypothesis for some $l$ holds $$\binom{k}{a_k}=2^k-\sum_{i=0}^{k-1} \binom{k}{a_i} =2^k-\sum_{i=0}^{k-l-1} \binom{k}{i} -\sum_{j=0}^{l-1} \binom{k}{j} =2^k-\sum_{i=0}^{k-l-1} \binom{k}{i}-\sum_{j=k-l+1}^k \binom{k}{j} =\binom{k}{k-l},$$therefore $a_k\in \left \{ l,k-l \right \}$, which easily completes the proof of inductive step $\Box$

Claim: For all integers $k\geq 0$, the tuple $(a_0, a_1, \dots, a_k)$ is some permutation of the concatenation of the tuples $(0, 1, \dots, p)$ and $(0, 1, \dots, k-p-1)$ for some integer $p\leq k$ (if $p=k$ then the second tuple is empty). Proof. We proceed by induction. The base case is clear: when $k=0$, we have $\binom{0}{a_0}=1$, so $a_0=0$. For the inductive step, assume that the desired result is true for $k=i$. Define the values $(b_0, b_1, \dots, b_k)=(0, 1, \dots, p, k-p-1, k-p-2, \dots, 0)$ as a permutation of $(a_0, a_1, \dots, a_k)$. We show the result for $k=i+1$. We have \begin{align*} 2^{k+1}&=\binom{k+1}{a_0}+\dots+\binom{k+1}{a_k}+\binom{k+1}{a_{k+1}} \\ &=\binom{k+1}{b_0}+\dots+\binom{k+1}{b_p}+\binom{k+1}{b_{p+1}}+\dots+\binom{k+1}{b_k}+\binom{k+1}{a_{k+1}} \\ &=\binom{k+1}{b_0}+\dots+\binom{k+1}{b_p}+\binom{k+1}{k+1-b_{p+1}}+\dots+\binom{k+1}{k+1-b_k}+\binom{k+1}{a_{k+1}} \\ &=\binom{k+1}{0}+\dots+\binom{k+1}{p}+\binom{k+1}{p+2}+\dots+\binom{k+1}{k+1}+\binom{k+1}{a_{k+1}} \\ &=2^{k+1}-\binom{k+1}{p+1}+\binom{k+1}{a_{k+1}}. \end{align*}Thus, $\binom{k+1}{a_{k+1}}=\binom{k+1}{p+1}$, so either $a_{k+1}=p+1$ or $a_{k+1}=k-p$. If the former is true, then $(a_0, a_1, \dots, a_{k+1})$ is a permutation of the concatenation of $(0, 1, \dots, p+1)$ and $(0, 1, \dots, (k+1)-(p+1)-1)$, as desired. If the latter is true, then $(a_0, a_1, \dots, a_{k+1})$ is a permutation of the concatenation of $(0, 1, \dots, p)$ and $(0, 1, \dots, (k+1)-p-1)$, as desired. $\blacksquare$ By this fact, for any given $k$, the set $\{a_0, a_1, \dots, a_k\}$ must be a superset of the set $\left\{0, 1, \dots, \left\lceil\frac{k-1}{2}\right\rceil\right\}$ (it exactly equals this set when $p=\left\lceil\frac{k-1}{2}\right\rceil$). As $k$ grows arbitrarily large, $\left\lceil\frac{k-1}{2}\right\rceil$ also grows arbitrarily large, so all integers $N\geq 0$ must occur in $a_0, a_1, a_2, \dots$, as desired.

The key is to classify the first $n+1$ terms as the union of two disjoint sequences $A = \{0, 1, 2, \cdots, a\}$ and $B = \{0, 1, 2, \cdots, b\}$ with $a+b = n-1$. This obviously implies the result. On the other hand, this is true inductively because \begin{align*} 2^{n+1} - {n+1 \choose a_{n+1}} &= \sum_{i=0}^n {n \choose a_i} + \sum_{a_i \in A} {n \choose a_{i-1}} + \sum_{a_i \in B} {n \choose a_{i-1}} \\ &= 2^n + 2^n - {n \choose a} - {n \choose b} \\ &= 2^{n+1} - {n+1 \choose a+1}. \end{align*}Hence $a_{n+1} = a+1$ or $b+1$, as needed. Remark on Motivation. This claim actually follows quite naturally after noticing the recursive relation $a_n = a_{n-1} + 1$ or $n +1 - a_{n-1}$, which is standing alone quite thorny to prove. Instead classifying the entire sequence based on this relation makes for a much smoother solution.

why did it take me so long to solve this We claim that all possible sequences are just $0,0,1,1,\dots, a,a,a+1,a+2,\dots, b$ where $a+b=n-1$. We proceed with induction with the base cases being trivial. Note that \[\binom{n+1}{0}+\binom{n+1}{1}+\dots + \binom{n+1}{a}+\binom{n+1}{n-b}+\dots + \binom{n+1}{n}=2^{n+1}-\binom{n}{a+1}\]so either $a_{n+1}=a+1$ or $b+1$ which finishes the induction.

Picture this: a monkey is being experimented upon in a science lab, trapped in a white room with glass windows. Scientists carefully watch through glass windows. The monkey is given two infinitely tall stacks of cards; each stack contains a card numbered $0$ at the top, a card numbered $1$ right below that, a card numbered $2$ right below that, etc. Besides the cards is a button and a counter that currently reads $0$. The monkey will pick one of the two stacks and remove the card at the top of that stack. The number on that card becomes $a_k$, where $k$ is the nubmer on the counter. Then, the monkey hits the button, which increments the counter by $1$. We claim that such a sequence $\{ a\}$ satisfies the conditions of the problem. Consider the moment right after the monkey picks a card and and assigns $a_k$ to the value of that card. At that moment, the sum of the two cards at the top of the deck is $k+1$. If the cards at the top of the two stacks are $i$ and $k+1-i$, then the monkey has drawn cards $0,1, \dots, i-1$ from the first stack and $0,1, \dots, k-i$ from the second stack. Then, note that \begin{align*} ~ & \left( \binom{k}{0}+\binom{k}{1} + \dots + \binom{k}{i-1} \right) + \left( \binom{k}{0}+\binom{k}{1} + \dots + \binom{k}{k-i} \right) \\ = ~ & \left( \binom{k}{0}+\binom{k}{1} + \dots + \binom{k}{i-1} \right) + \left( \binom{k}{k}+\binom{k}{k-1} + \dots + \binom{k}{i} \right) \\ = ~ & 2^k, \end{align*}which proves our claim. Now consider the scenario where the monkey tries to rebel and pick a different value for $a_k$ than one of the cards at the top of each stack. We have already seen that those two choices presented to the monkey are good choices - either value can be assigned to $a_k$ while still satisfying the conditions of the problem. Also, due to the conditions of the problem and the way the choose function works, there can be at most two solutions to $a_k$, given fixed values for $a_0, a_1, \dots, a_{k-1}$. Thus, if the monkey rebels, he will pick an incorrect value for $a_k$. Thus, a valid sequence $a_0, a_1, a_2, \dots$ is generated if and only if the monkey complies with his scientists' orders. So, inevitably, the monkey must draw every single positive integer in existence, as he sits, endlessly drawing cards and pressing buttons.

The main claim is that the sequence $ a_0, a_1, \cdots , a_k $ is always a permutation of $ 0, 1, \cdots, (a - 1), 0, 1, \cdots, (b - 1)$ for some $ a + b = k+1$ (here we allow $ a, b = 0$ so that e.g. $ 0, 1, \cdots, (a - 1)$ may be empty). We prove this by induction on $ k $. Base case: $ k = 0 $ is trivially true as $ a_0 = 0 $. Induction step: Suppose the claim is true for some $ k $. Then applying the well-known result of $2^{n} = \sum_{i=0}^{n} {n \choose i}$, we get \[ \sum_{i=0}^{k+1} {{k+1} \choose a_i} = \sum_{i=0}^{k+1} {{k+1} \choose i}\]\[ \sum_{i=0}^{a-1} {{k+1} \choose i} + \sum_{i=0}^{b-1} {{k+1} \choose i} + {{k+1} \choose a_{k+1}} = \sum_{i=0}^{k+1} {{k+1} \choose i}\]Now rewrite the second term with the substitution $j = k + 1 - i$ and the fact that ${{k + 1} \choose i} = {{k + 1} \choose j}$: \[ \sum_{i=0}^{a-1} {{k+1} \choose i} + \sum_{j=a+1}^{k+1} {{k+1} \choose j} + {{k+1} \choose a_{k+1}} = \sum_{i=0}^{k+1} {{k+1} \choose i}\]\[ {{k+1} \choose a_{k+1}} = {{k+1} \choose a}\]Hence we must have $a_{k+1} = a$ or $a_{k+1} = k+1 - a = b$, for either of which it is easy to see that the claim holds for $ a_0, \cdots, a_{k+1}$. Now the problem is straightforward; just take sufficient large $k$ (say, $k \geq 2N$) then if WLoG $a \geq b$ then $a \geq \left\lceil\frac{k + 1}{2}\right\rceil \geq N+1$, and $ N $ can be found in the sequence $0, \cdots, (a-1)$.

We'll proceed by induction, showing that the sequence must maintain the form $1,1,2,2,...,i,i,i+1,i+2,...,j$. The base case n=0 is obvious with $a_0=0$. Now, suppose the hypothesis is true for some n=k, where n is the number of terms in the sequence (specifically, j+i+1=n=k). Then $$\binom{k+1}{0}+\binom{k+1}{0}+...+\binom{k+1}{i}+\binom{k+1}{i}+\binom{k+1}{i+1}+\binom{k+1}{i+2}+...+\binom{k+1}{j}=\binom{k+1}{0}+\binom{k+1}{1}+...+\binom{k+1}{j}+\binom{k+1}{j+2}+...+\binom{k+1}{k+1}=2^{k+1}-\binom{k+1}{j+1},$$which readily implies that the next term in the sequence is either j+1 or i+1=(k+1)-(j+1), which indeed holds the structure of the sequence we described; in particular, we won't skip over a number and eventually must run over all nonnegative integers. $\blacksquare$

We perform induction on the following three claims at once. 1. For all $k \geq 0$, there must exist some term $a_i=k$ in the set $a_0,a_1,\dots,a_{2k}$. 2. In the set of terms $a_0,a_1,\dots,a_{2k-1}$ there exists two terms each of $\{0,(2k-1)\}$ , $\{1,2k-2\} , \dots, \{k,k-1\}$. 3. If there exists so term $a_i=k$ for some integer $k$, in the set $a_1,\dots,a_n$ for some $n$, then there also does not exist any term $a_j > k $ in $a_1,\dots,a_n$. It is easy to see that in the base case $a_0=0$ the first claim is true, considering upto $a_1$ we see that Claim 2 is also clearly true and so is the last. Now, we proceed by induction. Say our claims are true upto the term $a_{2k-1}$. Now, we have two cases. Case 1 : There exists no term $a_i=k$ in $a_1,\dots,a_{2k-1}$. Then using Claim 1, \begin{align*} 2^{2k} &= \binom{2k}{a_0} + \binom{2k}{a_1} +\dots + \binom{2k}{a_{2k}}\\ 2^{2k} &= 2 \left(\binom{2k}{0} + \binom{2k}{1} +\dots + \binom{2k}{k-1}\right) + \binom{2k}{a_{2k}} \\ &= \binom{2k}{0} + \dots + \binom{2k}{k-1} + \binom{2k}{k+1} + \dots + \binom{2k}{2k-1} + \binom{2k}{2k} + \binom{2k}{a_{2k}}\\ \binom{2k}{a_{2k}} &= \binom{2k}{k} \end{align*}which means $a_{2k}=k$ as needed. Here, the first equality was obtain by the Inductive Hypothesis (Claim 2). Further, \[2^{2k+1} = \binom{2k+1}{a_0} + \binom{2k+1}{a_1} +\dots + \binom{2k+1}{a_{2k+1}} \]\begin{align*} 2^{2k+1} &= \binom{2k+1}{0} + \dots + \binom{2k+1}{k} + \binom{2k+1}{k+2} + \dots + \binom{2k+1}{2k+1} + \binom{2k+1}{a_{2k+1}}\\ \binom{2k}{a_{2k}} &= \binom{2k+1}{k+1} \end{align*}Thus, $a_{2k+1}=k+1$ or $k$, which verifies Claim $2$. Considering the possible values obtained, we see that clearly Claim 3 is maintained too. Case 2 : There exists some $a_i$ in $a_1,\dots,a_{2k-1}$ equal to $k,k+1,\dots,k+c$ but no term $a_j=k+c+1$ for $k-1 \geq c \geq 0$. Now, first notice that this means we have exactly 2 terms which are $0,1,\dots,k-c-2$ each and one each which are $k-c-1,\dots,k-2,k-1,k,k+1,\dots,k+c$. Using this information, we see that \begin{align*} 2^{2k} &= \binom{2k}{a_0}+ \binom{2k}{a_1} + \binom{2k}{a_2} + \dots + \binom{2k}{a_{2k}}\\ &= \binom{2k}{0} + \binom{2k}{1} + \dots + \binom{2k}{k+c} + \binom{2k}{k-c-2} + \binom{2k}{k-c-3} + \dots + \binom{2k}{0}\\ &= \binom{2k}{0} + \binom{2k}{1} + \dots + \binom{2k}{k+c} + \binom{2k}{k+c+2} + \dots + \binom{2k}{2k} + \binom{2k}{a_{2k}}\\ \binom{2k}{a_{2k}} &= \binom{2k}{k+c+1} \end{align*}Thus, $a_{2k}=k+c+1$ or $k-c-1$. Now, \begin{align*} 2^{2k+1} &= \binom{2k+1}{a_0} + \binom{2k+1}{a_1} + \binom{2k+1}{a_2} + \dots + \binom{2k+1}{a_{2k}} + \binom{2k+1}{a_{2k+1}}\\ &= \binom{2k+1}{0} + \dots + \binom{2k+1}{k+c} + \binom{2k+1}{a_{2k}}+\binom{2k+1}{k+c+3} + \dots + \binom{2k+1}{2k+1} + \binom{2k+1}{a_{2k+1}}\\ \end{align*}\[\binom{2k+1}{a_{2k+1}}+\binom{2k+1}{a_{2k}} = \binom{2k+1}{k+c+2} + \binom{2k+1}{k+c+1} \]If, $a_{2k}=k+c+1$, then we have $a_{2k+1}=k+c+2$ or $k-c-1$ and if $a_{2k}=k-c-1$ then $a_{2k+1}=k+c+1$ or $k-c$. Thus, it is easy to see that indeed Claim 2, is true here too and so is Claim 3. Thus, by the Principle of Mathematical Induction, all our claims are true, and in particular Claim 1 is true. Thus, every non-negative integer $n$ clearly must appear in the sequence since for all $n\in \mathbb{N}$ one of $a_1,\dots,a_{2n}$ is in fact n.

Claim: For $n \ge 0$, $(a_0, a_1, \ldots, a_n)$ is some permutation of $(0, 1, \ldots, a -1 , 0, 1, \ldots, b - 1)$ for nonnegative $a$, $b$ such that $a + b = n + 1$ (where $a = 0$ means it's just $(0, 1, \ldots, b - 1)$, and likewise for $b = 0$). Proof: We will induct on $n$; the base case of $n = 0$ is obvious as $a_0 = 0$. For the inductive step, if the assertion is true for $n$, then we have $$\begin{aligned} \sum_{i = 0}^n\binom{n + 1}{a_i} &= \sum_{j = 0}^{a - 1}\left[\binom{n}{j} + \binom{n}{j - 1}\right] + \sum_{k = 0}^{b - 1}\left[\binom{n}{k} + \binom{n}{k - 1}\right] \\ &= 2 \cdot \left(\sum_{j = 0}^{a - 1}\binom{n}{j} + \sum_{k = 0}^{b - 1}\binom{n}{k}\right) - \left(\binom{n}{a - 1} + \binom{n}{b - 1}\right) \\ &= 2^{n + 1} - \left(\binom{n}{a - 1} + \binom{n}{a}\right) \\ &= 2^{n + 1} - \binom{n + 1}{a}. \end{aligned}$$ Therefore, either $a_{n + 1} = a$ or $a_{n + 1} = n + 1 - a = b$, which proves the claim. To finish, note that all of $0, 1, \ldots, \lfloor \tfrac{n}{2} \rfloor$ must appear in $a_0, a_1, \ldots, a_n$.

We claim that $\{a_i | i \le m + n + 1\} = \{0, 1, 2, \dots, m\} \cup \{0, 1, 2, \dots, n\}$. We will show this claim by induction. Let $k = m+n+2$ We get \begin{align*} 2^{k} &= \left( \binom {k}{0} + \binom {k}{1} + \dots + \binom {k}{m} \right) + \left( \binom {k}{0} + \binom {k}{1} + \dots + \binom {k}{n} \right) + \binom n{a_k} \\ &= \left( \binom {k}{0} + \binom {k}{1} + \dots + \binom {k}{m} \right) + \left( \binom {k}{k} + \binom {k}{k-1} + \dots + \binom {k}{k-n} \right) + \binom {n}{a_k} \\ &= \left( \binom {k}{0} + \binom {k}{1} + \dots + \binom {k}{m} \right) + \left( \binom {k}{k} + \binom {k}{k-1} + \dots + \binom {k}{m+2} \right) + \binom {n}{a_k} \\ &= 2^k - \binom {k}{m+1} + \binom{n}{a_k}\end{align*}So $\binom {k}{a_k} = \binom{k}{n+1} = \binom{k}{m+1}$, so $a_k = n+1, m+1$ and finishing our induction. Now we are done since $N$ must appear in one of the first $2N+1$ terms of the sequence.

We denote a $k$-tuple $(a_0, a_1, \ldots, a_k)$ to be symmetric if we can choose specific indices $0 \le i \le k$ then make the swap $a_i \mapsto k-a_i$ so that the $k$-tuple is altered to $(0, 1, 2, \ldots, k)$. Call the indices that we swapped to be special, and let $\mathcal{S}_k$ be the set of these indices for $k$. Claim: The swapped versions ("fake") of all special indices are consecutive and at the "end" of the tuple for all $k$ and as a result $(a_0, a_1, \ldots, a_k)$ is symmetric for all $k$ We proceed with induction and prove both claims at once. Note that the base case for $k = 0, 1$ is trivial as they satisfy both properties. If an index $i \in \mathcal{S}_k$ then we make $i \in \mathcal{S}_{k+1}$. For $k$, if the hypothesis is true for both properties, then doing a "swap" on all $i \in \mathcal{S}_k$ for $k+1$ shifts the block of "fake" indices up by $1$, and leaves a spot for one index $j \neq a_i+1$ if $i$ is special and $j \neq a_i$ if $i$ is normal. Therefore $a_{k+1} = j, n+1-j$ and both hypotheses are true for $k+1$. Now, FTSOC assume there exists some $N$ that $a_i$ "skips". Simply take $k = 2N$, and note that because $(a_0, a_1, \ldots, a_{2N})$ is symmetric, one of $\{i, 2N-i\}$ is achieved by $a_j$ for all $0 \le i \le 2N$. Therefore letting $i = N$ gives the desired contradiction.

The bulk of the proof is to simply determine the structure of all possible sequences. Arranged in increasing order, they must appear like the following examples for $n=7$ and $n=8$ (to emphasize both parities): \begin{align*} 00112233 \quad & \quad 001122334 \\ 00112234 \quad & \quad 001122345 \\ 00112345 \quad & \quad 001123456 \\ 00123456 \quad & \quad 001234567 \\ 01234567 \quad & \quad 012345678 \end{align*} Notice the order of $a_0,\ldots,a_{k-1}$ doesn't matter once we reach $k$. To prove this must always hold, we simply induct, notice there are 1-2 possible additional terms for each sequence, and eliminate the sequences which are permutations of each other. $\blacksquare$

Claim: for every non negative number $m$, all integers in $[0,m]$ occur in the sequence $a_0, a_1,.......a_{2m}$ at least once and and all number in the sequence whether in $[0,m]$ or not occur maximum twice, which directly implies the problem statement. Proof : We will do this by strong induction on $m$. putting $m=k=0$ we get $\binom{0}{a_0}= 1$ Hence, $ a_0 =0$ Now assume the given assertion is true for all integers in $[0,m]$ FSTOC, Assume the assertion is false for $m+1$. put $k=2(m+1) = 2m+2$ to get $$ \binom{2m+2}{a_0}+\binom{2m+2}{a_1}+\cdots+\binom{2m+2}{a_{2m+2}} =2^{2m+2}= \binom{2m+2}{0}+\binom{2m+2}{1}+\cdots+\binom{2m+2}{2m+2}( eqn.\ 1) $$Note that the function $\binom{2m+2}{k}$ k is a non negative integer increases as k increases from 1 till $m+1$, it attains its maximum value at $k= m+1$. and then decrease in a symmetrical way from $m+1$ till $2m+2$. So, since the Claim is true by inductive hypothesis for $[0,m]$, we get LHS(of eqn. 1) < $\binom{2m+2}{1}+\binom{2m+2}{2}...+\binom{2m+2}{m} +\binom{2m+2}{m+2}+\binom{2m+2}{2}...+\binom{2m+2}{2m} + \binom{2m+2}{a_{2m+1}}+\binom{2m+2}{a_{2m+2}}= 2^{2m+2}-\binom{2m+2}{2m+2}-\binom{2m+2}{2m+1}-\binom{2m+2}{m+1}+\binom{2m+2}{a_{2m+1}}+\binom{2m+2}{a_{2m+2}}$ and do ...................... to get the answer. (I also don't know how t get to the answer )

We claim that the sequence at all points can be partitioned into at most $2$ sets, each consisting of a consecutive set of integers starting from $0$. We do this inductively. Base Case: This is obviously true as $a_0 = 0$. Inductive Step: Let us add $a_{n + 1}$. If $a_0$ through $a_n$ is just the first $n + 1$ nonnegative integers, we see that either $a_{n + 1} = n + 1$ and we add to the existing set, or $a_{n + 1} = 0$ and we create a new one. Otherwise, if the two sets range from $0$ to $x$ and $0$ to $y$, we must have $x + y = n - 1$, so setting $k = n + 1$ for typist's convenience we have $\sum \binom{k}{a_i} = \binom k0 + \cdots + \binom kx + \binom{k}{n + 1- y} + \cdots \binom kk$, since $n + 1 - y = x + 2$ we are forced that $a_{n + 1} = x + 1$ or $a_{n + 1} = n + 1 - x - 1 =y + 1 $, which proves the claim. We are clearly done, since the integer $i$ must occur in $a_0 \cdots a_{2i + 1}$, as a subsequence of this is forced to be $0, \cdots i$ by pigeonhole on the claim.

For nonnegative integers $k$ and $m$, let $b_{k,m}$ denote the number of times in which $m$ appears in the multiset $\{a_0,a_1,\dots,a_k\}$. We claim two things. First, we claim that $b_{k,m}>0$ if and only if $m\le c_k$ for some $c_k\ge\frac{k}2-1$. Second, we claim that the multiset $\{\binom{k}{a_i}\mid i\in\{0,1,\dots,k\}\}$ is exactly equal to the multiset $\{\binom{k}{i}\mid i\in\{0,1,\dots,k\}\}$. Both claims are easy to verify for $k=0$ as $a_0=0$. If both claims hold for $k-1$, then $\sum_{i=0}^{k-1}\binom{k}{a_i}=2^k-\binom{k}{c_{k-1}+1}$, so $a_k\in\{c_{k-1}+1,k-c_{k-1}-1\}$. One can check that this upholds both claims for $k$. In particular, we can never have $c_k<\frac{k}2-1$ as otherwise $c_{k-1}+1=k-c_{k-1}-1$. Using the second claim, observe that any integer $N$ must appear in the sequence $a_0,a_1,\dots,a_{2N}$ (if it doesn't appear in $a_0,a_1,\dots,a_{2N-1}$, then $\binom{2N}{a_{2N}}=\binom{2N}N$), and we are done. $\blacksquare$ from above posts observe that $b_{k,m}\le2$ at all times