, 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{1010...1011}$, then $a_{i+1} = \overline{101010...110}$ (with one extra $10$ at the beginning) and $a_{i+2} = \overline{101010...11} = a_i$, so $N = i$ works. Now we manually check the other cases:

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

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

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

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

$a_i = \overline{1010...101001}$ : $a_{i+1} = \overline{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 $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.