Question 64
Let $n$ be a natural number. We define sequences $a_i$ and $b_i$ as follows. We let $a_0 = 1$ and $b_0 = n$. For $i \gt 0$, we let
$$
(a_i, b_i) = \begin{cases} (2a_{i-1} + 1, b_{i-1} - a_{i-1} - 1) & \text{if } a_{i-1} \lt b_{i-1}, \\ (a_{i-1} - b_{i-1} - 1, 2b_{i-1} + 1) & \text{if } a_{i-1} \gt b_{i-1}, \\ (a_{i-1}, b_{i-1}) & \text{if } a_{i-1} = b_{i-1}. \end{cases}
$$
Given that $a_k = b_k$ for some natural number $k$, prove that $n + 3$ is a power of 2.
$$
(a_i, b_i) = \begin{cases} (2a_{i-1} + 1, b_{i-1} - a_{i-1} - 1) & \text{if } a_{i-1} \lt b_{i-1}, \\ (a_{i-1} - b_{i-1} - 1, 2b_{i-1} + 1) & \text{if } a_{i-1} \gt b_{i-1}, \\ (a_{i-1}, b_{i-1}) & \text{if } a_{i-1} = b_{i-1}. \end{cases}
$$
Given that $a_k = b_k$ for some natural number $k$, prove that $n + 3$ is a power of 2.