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 2 of 7: The odd part never decreases

Previous step Next step

a_i\ge2^m:\ b_{i+1}=b_i;\qquad a_i<2^m:\ b_{i+1}>b_i\ \text{unless}\ 2c_i=m\ \text{and}\ b_i=1\ (\text{then}\ b_{i+1}=b_i=1)

Detailed analysis

If $a_i\ge2^m$ , halving removes one factor of $2$ , so $b_{i+1}=b_i$ . If $a_i<2^m$ , then $a_{i+1}=b_i^22^{2c_i}+2^m$ ; factoring out $2^{\min(2c_i,m)}$ shows the odd part becomes $b_i^22^{|2c_i-m|}+1$ when $2c_i\ne m$ , which exceeds $b_i^2\ge b_i$ ; when $2c_i=m$ it becomes $(b_i^2+1)/2$ (odd, since $b_i^2\equiv1\pmod8$ for odd $b_i$ ), which by $(b_i-1)^2\ge0$ satisfies $b_{i+1}\ge b_i$ with equality exactly when $b_i=1$ . So $b_i$ never decreases, and strictly increases at every small-rule step except this single borderline case.