Advanced book on Mathematics Olympiad

Real Analysis 467

Hencexnandynsatisfy the same recurrence. This implies thatxn =ynfor alln.

The conclusion now follows by induction if we rewrite the recurrence as(xn+ 1 − 1 )=

5 (xn− 1 )−(xn− 1 − 1 )+3.

(proposed for the USA Mathematical Olympiad by G. Heuer)

312.From the recurrence relation for(an)n, we obtain

2 an+ 1 − 3 an=

√

5 a^2 n− 4 ,

and hence

4 a^2 n+ 1 − 12 an+ 1 an+ 9 a^2 n= 5 a^2 n− 4.

After canceling similar terms and dividing by 4, we obtain

a^2 n+ 1 − 3 an+ 1 an+a^2 n=− 1.

Subtracting this from the analogous relation forn−1 instead ofnyields

a^2 n+ 1 − 3 an+ 1 an+ 3 anan− 1 −an^2 − 1 = 0.

This is the same as

(an+ 1 −an− 1 )(an+ 1 − 3 an+an− 1 )= 0 ,

which holds forn≥1. Looking at the recurrence relation we see immediately that the

sequence(an)nis strictly increasing, so in the above product the first factor is different

from 0. Hence the second factor is equal to 0, i.e.,

an+ 1 = 3 an−an− 1 ,n≥ 2.

This is a linear recurrence that can, of course, be solved by the usual algorithm. But this

is a famous recurrence relation, satisfied by the Fibonacci numbers of odd index. A less

experienced reader can simply look at the first few terms, and then prove by induction

thatan=F 2 n+ 1 ,n≥1.

The sequence(bn)nalso satisfies a recurrence relation that can be found by substituting

an=bn+ 1 −bnin the recurrence relation for(an)n. After computations, we obtain

bn+ 1 = 2 bn+ 2 bn− 1 −bn− 2 ,n≥ 3.

But now we are told thatbnshould be equal to(Fn)^2 ,n≥1. Here is a proof by

induction onn. It is straightforward to check the equality forn= 1 , 2 ,3. Assuming that

bk=(Fk)^2 for allk≤n, it follows that

bn+ 1 = 2 (Fn)^2 + 2 (Fn− 1 )^2 −(Fn− 2 )^2