Problem 11153
(American Mathematical Monthly, Vol.112, May 2005) Proposed by P. Bracken (USA).
Letx1= 1, and for n ≥ 1 let xn+1= xn+ 2 + 1/xn. Ifyn= 2n + (1/2) log(n) − xn, show that the sequencehyni is eventually increasing.
Solution proposed by Giulio Francot and Roberto Tauraso,
Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
Let n ≥ 3 then summing the equations xk+1= xk+ 2 + 1/xk for k = 1, . . . , n − 1 we obtain
xn= x1+ 2(n − 1) +
n−1
X
k=1
1
xk = 2n +
n−1
X
k=2
1 xk. Therefore the sequence hxni is positive and increasing. Moreover for n ≥ 3
2n < xn= xn−1+ 2 + 1/xn−1≤ xn−1+ 3 ≤ 3(n − 1) + 1 < 3n.
The following is a better lower estimate
xn= 2n +
n−1
X
k=2
1
xk > 2n +
n−1
X
k=2
1
3k = 2n + 1
3(Hn−1− 1) . Now we consider the sequence hyni. Since
yn+1− yn= 2 +1
2log n + 1 n
− (xn+1− xn) = 1 2log
1 + 1
n
− 1 xn then hyni is eventually increasing if the following inequality eventually holds
xn> 2 log 1 +n1
. We note that
2 log 1 +n1
= 2
1
n −2n12 + o n12
=
2n 1 − 2n1 + o n1
= 2n
1 + 1
2n+ o 1 n
= 2n + 1 + o(1).
Finally by the lower estimate, since Hn goes to infinity, eventually xn> 2n +1
3(Hn−1− 1) ≥ 2n + 1 + o(1).