Saudi Arabia Mathematical Competitions 2012

Suppose $a_i$, when expressed in binary, is a number formed by appending some number of copies of $10$ at the beginning followed by a generic $k$-digit binary number. We show that continuing the recurrence from $a_i$ will eventually result in an $N$ for which $n>N$ implies $a_n=a_{n+2}$. We do so by strong induction on $k$.

Our base cases will be $k=0,1,2$. First, notice that if $a_i=\overline{\mathrm{1010...1011}}$, then $a_{i+1}=\overline{\mathrm{101010...110}}$ (with one extra $10$ at the beginning) and $a_{i+2}=\overline{\mathrm{101010...11}}=a_i$, so $N=i$ works. Now we manually check the other cases:

$a_i=\overline{\mathrm{1010...10101}}$ : $a_{i+1}=\overline{\mathrm{101010...1011}}$, already checked.

$a_i=\overline{\mathrm{1010...1010}}$ : $a_{i+1}=\overline{\mathrm{1010...101}}$, already checked.

$a_i=\overline{\mathrm{1010...10100}}$ : $a_{i+1}=\overline{\mathrm{1010...1010}}$, already checked.

$a_i=\overline{\mathrm{1010...101000}}$ : $a_{i+1}=\overline{\mathrm{1010...10100}}$, already checked.

$a_i=\overline{\mathrm{1010...101001}}$ : $a_{i+1}=\overline{\mathrm{101010...10101}}$, already checked.

Now for the inductive step. Assume $a_i$ has some copies of $10$ in its binary representation followed by an arbitrary $k$-digit number, and that we have shown our inductive hypothesis for all numbers less than $k$.

Case 1: $a_i$ ends with a $0$. Then $a_{i+1}$ is the same number without that $0$, so we have $k-1$ digits following the copies of $10$ and we can apply the inductive hypothesis.

Case 2: $a_i$ ends with a $1$ and the $k$-digit number is not all $1$s. Then $a_{i+1}$ is obtained by removing the $1$ at the end, adding $1$ to the number, and adding a $10$ to the beginning. Since the $k$-digit number is not all $1$s, adding $1$ to it will not mess up the last copy of $10$, so the result is a $(k-1)$-digit binary number preceded by copies of $10$, and we can apply the inductive hypothesis.

Case 3: $a_i$ ends with $k$ $1$s. Then $a_{i+1}$ ends with $\mathrm{1100...0}$, where there are $k-1$ $0$s, preceded by some copies of $10$. It can be easily computed that $a_{i+k}$ will be the same number without the last $k-1$ $0$s, so $a_{i+k}$ is a $2$-digit binary number preceded by copies of $10$, and our base case finishes this case.