Problem

Source:

Tags: divisor, recurrence relation, number theory



For each positive integer $n$, denote by $O(n)$ its greatest odd divisor. Given any positive integers $x_1 = a$ and $x_2 = b$, construct an innite sequence of positive integers as follows: $x_n = O(x_{n-1} + x_{n-2})$, where $n = 3,4,...$ (a) Prove that starting from some place, all terms of the sequence are equal to the same integer. (b) Express this integer in terms of $a$ and $b$.