SELECTION EXAMINATION 2019

We will prove using induction with respect to $\kappa$ that every initial part ${\alpha }_0,{\alpha }_1,{\alpha }_2,\dots ,{\alpha }_{\kappa }$ of the sequence consists of the following integers (not necessarily with the turn of the terms of the sequence) $0,1,\dots ,\ell -1,0,1,\dots ,\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,\dots ,{\alpha }_{\nu }$ are of the form $0,0,1,1,2,2,\dots ,\ell -1,\ell -1,\ell ,\ell +1,\dots ,\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{array}{c}\left(\genfrac{}{}{0ex}{}{\nu +1}{{\alpha }_0}\right)+\left(\genfrac{}{}{0ex}{}{\nu +1}{{\alpha }_1}\right)+\cdots +\left(\genfrac{}{}{0ex}{}{\nu +1}{{\alpha }_{\nu }}\right)+\left(\genfrac{}{}{0ex}{}{\nu +1}{{\alpha }_{\nu +1}}\right)=2^{\nu +1}\iff \\ \left\{\left(\genfrac{}{}{0ex}{}{\nu +1}{0}\right)+\left(\genfrac{}{}{0ex}{}{\nu +1}{1}\right)+\cdots +\left(\genfrac{}{}{0ex}{}{\nu +1}{\ell -1}\right)\right\}+\left\{\left(\genfrac{}{}{0ex}{}{\nu +1}{0}\right)+\left(\genfrac{}{}{0ex}{}{\nu +1}{1}\right)+\cdots +\left(\genfrac{}{}{0ex}{}{\nu +1}{\nu -\ell }\right)\right\}+\left(\genfrac{}{}{0ex}{}{\nu +1}{{\alpha }_{\nu +1}}\right)=2^{\nu +1}\iff \\ \left\{\left(\genfrac{}{}{0ex}{}{\nu +1}{0}\right)+\left(\genfrac{}{}{0ex}{}{\nu +1}{1}\right)+\cdots +\left(\genfrac{}{}{0ex}{}{\nu +1}{\ell -1}\right)\right\}+\left\{\left(\genfrac{}{}{0ex}{}{\nu +1}{\nu +1}\right)+\left(\genfrac{}{}{0ex}{}{\nu +1}{\nu }\right)+\cdots +\left(\genfrac{}{}{0ex}{}{\nu +1}{\ell +1}\right)\right\}+\left(\genfrac{}{}{0ex}{}{\nu +1}{{\alpha }_{\nu +1}}\right)=2^{\nu +1}.(1)\end{array}$$ Moreover, we have: $$\left(\genfrac{}{}{0ex}{}{\nu +1}{0}\right)+\left(\genfrac{}{}{0ex}{}{\nu +1}{1}\right)+\cdots +\left(\genfrac{}{}{0ex}{}{\nu +1}{\nu +1}\right)=2^{\nu +1}.(2)$$ From relations (1) and (2) it follows that: $$\left(\genfrac{}{}{0ex}{}{\nu +1}{{\alpha }_{\nu +1}}\right)=\left(\genfrac{}{}{0ex}{}{\nu +1}{\ell }\right).(3)$$ From relation (3), by using that the binomial coefficients $\left(\genfrac{}{}{0ex}{}{\nu +1}{i}\right)$ 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,\dots ,{\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,\dots ,\ell -1,0,1,\dots ,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$.