Since x3− 2 = 2 = x1, it follows that for n ≥ 1, x3n= xn+ 2

Problem 11852

(American Mathematical Monthly, Vol.122, August-September 2015) Proposed by S. Northshield (USA).

Forn ∈ Z⁺, letνn= k if 3^k dividesn but 3^k+1 does not. Letx1= 2, and for n ≥ 2 let xn= 4νn+ 2 − 2

xn−1

.

Show that every positive rational number appears exactly once in the sequence{xn}n≥1.

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.

The sequence begins with 2, 1, 4,³₂,²₃, 3,⁴₃,¹₂, 6,⁵₃, . . . . We have that for n ≥ 2, x3n−2 = 4ν3n− 2

x3n−1

= 4(νn+1)− 2 2 − 2

x3n−2

= 4νn+4− 2

2 − 2

2 − 2 x3n−3

= 4νn+2− 2 x3(n−1)− 2.

So x3n− 2 satisfies the same recurrence as xn. Since x3− 2 = 2 = x1, it follows that for n ≥ 1, x3n= xn+ 2.

Moreover, for n ≥ 1, x3n+1 = 2 − 2

x3n = 2 − 2

xn+ 2 and x3n+2 = 2 − 2

x3n+1 = 1 − 1 xn+ 1.

Now, we describe a procedure which determines, for any given rational number y0, a unique positive integer n such that xn= y0.

1) Let j = 0 and let c0= 0.

2) If yj= 2 then the value of n is equal to cj+ 3^j. Stop.

If yj= 1 then the value of n is equal to cj+ 2 · 3^j. Stop.

3) If 2 < yj then let yj+1 = yj− 2 and let cj+1= cj.

If 1 < yj< 2 then let yj+1= 2/(2 − yj) − 2 and let cj+1= cj+ 3^j. If 0 < yj< 1 then let yj+1= 1/(1 − yj) − 1 and let cj+1= cj+ 2 · 3^j. 4) Add 1 to j and go to step 2).

Note that the rational number yj is positive and if yj= aj/bj6∈ {1, 2} where aj, bj∈ Z⁺ then

yj+1=aj+1

bj+1 =











a_j−2bj

b_j if 2 < yj ⇒ aj+1+ bj+1= aj− bj,

2aj−2bj

2bj−a_j if 1 < yj < 2 ⇒ aj+1+ bj+1= aj,

a_j

bj−aj if 0 < yj < 1 ⇒ aj+1+ bj+1= bj.

Hence aj+ bj > aj+1+ bj+1≥ 1 which implies that the procedure will eventually stop.