462 Real Analysis
Remark.A solution based on the Binet formula is possible if we note the factorization
λ^4 − 3 λ^3 − 6 λ^2 + 3 λ+ 1 =(λ^2 − 4 λ− 1 )(λ^2 +λ− 1 ).Setting the left-hand side equal to 0 gives the characteristic equation for the sequence
(bn)n, while setting the first factor on the right equal to 0 gives the characteristic equation
for(an)n.
(proposed by T. Andreescu for a Romanian Team Selection Test for the International
Mathematical Olympiad, 2003, remark by R. Gologan)
302.We computeu 0 = 1 +1,u 1 = 2 +^12 ,u 2 = 2 +^12 ,u 3 = 8 +^18. A good guess is
un= 2 xn+ 2 −xnfor some sequence of positive integers(xn)n.
The recurrence gives
2 xn+^1 + 2 −xn+^1 = 2 xn+^2 xn−^1 + 2 −xn−^2 xn−^1 + 2 xn−^2 xn−^1 + 2 −xn+^2 xn−^1 − 2 x^1 − 2 −x^1.In order to satisfy this we hope thatxn+ 1 =xn+ 2 xn− 1 and thatxn− 2 xn− 1 =±x 1 =±1.
The characteristic equation of the first recurrence isλ^2 −λ− 2 =0, with the roots 2 and
−1, and using the fact thatx 0 =0 andx 1 =1 we get the general term of the sequence
xn=( 2 n−(− 1 )n)/3. Miraculously this also satisfiesxn− 2 xn− 1 =(− 1 )n+^1 so the second
condition holds as well. We conclude thatun= 2 xn, and soun= 2 [^2
n−(− 1 )n]/ 3
.
(18th International Mathematical Olympiad, 1976, proposed by the UK)
303.We need to determinemsuch thatbm>an>bm− 1. It seems that the difficult part
is to prove an inequality of the forman >bm, which reduces to 3an−^1 > 100 bm−^1 ,or
an− 1 >(log 3100 )bm− 1. Iterating, we obtain 3an−^2 >(log 3100 ) 100 bm−^2 , that is,
an− 2 >log 3 (log 3100 )+((log 3100 )bm− 2.Seeing this we might suspect that an inequality of the forman>u+vbn, holding for
allnwith some fixeduandv, might be useful in the solution. From such an inequality
we would derivean+ 1 = 3 an > 3 u( 3 v)bm.If3v>100, thenan+ 1 > 3 ubm+ 1 , and if
3 u>u+v, then we would obtainan+ 1 >u+vbm+ 1 , the same inequality as the one we
started with, but withm+1 andn+1 instead ofmandn.
The inequality 3v>100 holds forv=5, and 3u>u+5 holds foru=2. Thus
an> 2 + 5 bmimpliesan+ 1 > 2 + 5 bm+ 1. We haveb 1 =100,a 1 =3,a 2 =27,a 3 = 327 ,
and 2+ 5 b 1 = 502 < 729 = 36 ,soa 3 > 2 + 5 b 1. We find thatan> 2 + 5 bn− 2 for all
n≥3. In particular,an≥bn− 2.
On the other hand,an<bmimpliesan+ 1 = 3 an< 100 bm<bm+ 1 , which combined
witha 2 <b 1 yieldsan<bn− 1 for alln≥2. Hencebn− 2 <an<bn− 1 , which implies
thatm=n−1, and forn=100,m=99.
(short list of the 21st International Mathematical Olympiad, 1979, proposed by
Romania, solution by I. Cuculescu)