Câu hỏi 64
Cho $n$ là một số tự nhiên. Ta định nghĩa các dãy $a_i$ và $b_i$ như sau. Đặt $a_0 = 1$ và $b_0 = n$. Với $i \gt 0$, đặt
$$
(a_i, b_i) = \begin{cases} (2a_{i-1} + 1, b_{i-1} - a_{i-1} - 1) & \text{nếu } a_{i-1} \lt b_{i-1}, \\ (a_{i-1} - b_{i-1} - 1, 2b_{i-1} + 1) & \text{nếu } a_{i-1} \gt b_{i-1}, \\ (a_{i-1}, b_{i-1}) & \text{nếu } a_{i-1} = b_{i-1}. \end{cases}
$$
Biết rằng $a_k = b_k$ với một số tự nhiên $k$ nào đó, hãy chứng minh rằng $n + 3$ là một lũy thừa của $2$.
$$
(a_i, b_i) = \begin{cases} (2a_{i-1} + 1, b_{i-1} - a_{i-1} - 1) & \text{nếu } a_{i-1} \lt b_{i-1}, \\ (a_{i-1} - b_{i-1} - 1, 2b_{i-1} + 1) & \text{nếu } a_{i-1} \gt b_{i-1}, \\ (a_{i-1}, b_{i-1}) & \text{nếu } a_{i-1} = b_{i-1}. \end{cases}
$$
Biết rằng $a_k = b_k$ với một số tự nhiên $k$ nào đó, hãy chứng minh rằng $n + 3$ là một lũy thừa của $2$.