Problem 2

Let

m

be a fixed positive integer. The infinite sequence

\{a_n\}_{n\ge1}

is defined in the following way:

a_1

is a positive integer, and for every integer

n\ge1

a_{n+1}=a_n^2+2^m

a_n<2^m

, and

a_{n+1}=a_n/2

a_n\ge2^m

. For each

m

, determine all possible values of

a_1

such that every term of the sequence is an integer.

Step 1 of 7: Bound the odd part

Previous step Next step

a_i=b_i2^{c_i},\ b_i\ \text{odd};\qquad b_i>2^m\ \Longrightarrow\ \text{eventually a division of an odd number by }2

Detailed analysis

Write each term as $a_i=b_i2^{c_i}$ with $b_i$ odd. If some $b_i>2^m$ , then as long as $c_i>0$ we have $a_i\ge b_i>2^m$ , so the halving rule applies and $c$ decreases by $1$ while $b_i$ is unchanged; once $c_i$ reaches $0$ , the term equals the odd number $b_i>2^m$ , which still triggers halving, but $b_i$ odd makes $b_i/2$ non-integer. So if every term is an integer, $b_i\le2^m$ for all $i$ .