Greece — Selection Examination, 2019

We will prove using induction with respect to $\kappa$ that every initial part $\alpha_0, \alpha_1, \alpha_2, \ldots, \alpha_\kappa$ of the sequence consists of the following integers (not necessarily with the turn of the terms of the sequence)
$0, 1, \ldots, \ell-1, 0, 1, \ldots, \kappa-\ell$, for some $\ell \ge 0$ with $2\ell \le \kappa+1$.

For $\kappa = 0$, $\alpha_0 = 0$ holds. Suppose that for $\kappa = \nu$ the terms $\alpha_0, \alpha_1, \alpha_2, \ldots, \alpha_\nu$ are of the form
$0, 0, 1, 1, 2, 2, \ldots, \ell-1, \ell-1, \ell, \ell+1, \ldots, \nu-\ell-1, \nu-\ell$ for some $\ell$ with $0 \le 2\ell \le \kappa+1$.

Then, for $\kappa = \nu + 1$, we have from (β) that:
$$\begin{gather*} \binom{\nu+1}{\alpha_0} + \binom{\nu+1}{\alpha_1} + \cdots + \binom{\nu+1}{\alpha_\nu} + \binom{\nu+1}{\alpha_{\nu+1}} = 2^{\nu+1} \Leftrightarrow \\ \left\{ \binom{\nu+1}{0} + \binom{\nu+1}{1} + \cdots + \binom{\nu+1}{\ell-1} \right\} + \left\{ \binom{\nu+1}{0} + \binom{\nu+1}{1} + \cdots + \binom{\nu+1}{\nu-\ell} \right\} + \binom{\nu+1}{\alpha_{\nu+1}} = 2^{\nu+1} \Leftrightarrow \\ \left\{ \binom{\nu+1}{0} + \binom{\nu+1}{1} + \cdots + \binom{\nu+1}{\ell-1} \right\} + \left\{ \binom{\nu+1}{\nu+1} + \binom{\nu+1}{\nu} + \cdots + \binom{\nu+1}{\ell+1} \right\} + \binom{\nu+1}{\alpha_{\nu+1}} = 2^{\nu+1}. \quad (1) \end{gather*}$$
Moreover, we have:
$$\binom{\nu+1}{0} + \binom{\nu+1}{1} + \cdots + \binom{\nu+1}{\nu+1} = 2^{\nu+1}. \quad (2)$$
From relations (1) and (2) it follows that:
$$\binom{\nu+1}{\alpha_{\nu+1}} = \binom{\nu+1}{\ell}. \quad (3)$$
From relation (3), by using that the binomial coefficients $\binom{\nu+1}{i}$ are increasing when the variable $i \le \frac{\nu+1}{2}$ increases and they are decreasing when the variable $i \ge \frac{\nu+1}{2}$ increases, we conclude that $\alpha_{\nu+1} = \ell$ or $\alpha_{\nu+1} = \nu+1-\ell$. In both cases the initial part $\alpha_0, \alpha_1, \alpha_2, \ldots, \alpha_{\nu+1}$ of the sequence is of the form we seek. Therefore, according to the above conclusion, every integer $n \ge 0$ will coincide to the term $\alpha_i$ of the sequence for some $i$ with $0 \le i \le 2n$.

Indeed, the sequence will have terms $0, 1, \ldots, \ell-1, 0, 1, \ldots, 2n-\ell$, for some $\ell \le \frac{2n+1}{2}$, and therefore we have the cases:

* if $n < \ell \le \frac{2n+1}{2}$, then $n \le \ell-1$, and so there exists $i \ge 0$ such that $\alpha_i = n$.
* if $n \ge \ell$, then $n > \ell-1 \Rightarrow 2n-n < 2n-\ell+1 \Rightarrow n \le 2n-\ell$, and so again there exists $i \ge 0$ such that $\alpha_i = n$.