Advanced book on Mathematics Olympiad

Real Analysis 461

an=

1

2

(a 2 n− 2 +a 2 )−an− 2 = 2 an− 1 + 2 a 1 −an− 2

= 2 (n^2 − 2 n+ 1 )+ 2 −(n^2 − 4 n+ 4 )=n^2.

This completes the proof.
(Russian Mathematical Olympiad, 1995)

301.First solution: If we compute some terms,a 0 =0,a 1 =2,a 3 =8,a 4 =34,
a 5 =144, we recognize Fibonacci numbers, namelyF 0 ,F 3 ,F 6 ,F 9 , andF 12. So a good
working hypothesis is thatan=F 3 nand also thatbn=(Fn)^3 , for alln≥0, from which
the conclusion would then follow.
We use induction. Everything is fine forn=0 andn=1. Assumingak=F 3 kfor
allk≤n, we have

an+ 1 = 4 F 3 n+F 3 n− 3 = 3 F 3 n+F 3 n+F 3 n− 3

= 3 F 3 n+F 3 n− 1 +F 3 n− 2 +F 3 n− 3 = 3 F 3 n+F 3 n− 1 +F 3 n− 1

=F 3 n+ 2 F 3 n+ 2 F 3 n− 1 =F 3 n+ 2 F 3 n+ 1 =F 3 n+F 3 n+ 1 +F 3 n+ 1

=F 3 n+ 2 +F 3 n+ 1 =F 3 n+ 3 =F 3 (n+ 1 ),

which proves the first part of the claim.
For the second part we deduce from the given recurrence relations that
bn+ 1 = 3 bn+ 6 bn− 1 − 3 bn− 2 −bn− 3 ,n≥ 3.

We point out that this is done by substitutingan=bn+ 1 +bn−bn− 1 into the recurrence
relation for(an)n. On the one hand,bn=(Fn)^3 is true forn= 0 , 1 , 2 ,3. The assumption
bk=(Fk)^3 for allk≤nyields

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

= 3 (Fn− 1 +Fn− 2 )^3 + 6 (Fn− 1 )^3 − 3 (Fn− 2 )^3 −(Fn− 1 −Fn− 2 )^3

= 8 (Fn− 1 )^3 + 12 (Fn− 1 )^2 Fn− 2 + 6 Fn− 1 (Fn− 2 )^2 +(Fn− 2 )^3

=( 2 Fn− 1 +Fn− 2 )^3 =(Fn+ 1 )^3.

This completes the induction, and with it the solution to the problem.

Second solution: Another way to prove thatbn=(Fn)^3 is to observe that both sequences
satisfy the same linear recurrence relation. Let

M=

(

11

10

)

.

We have seen before that

Mn=

(

Fn+ 1 Fn

Fn Fn− 1

)

.

Now the conclusion follows from the equalityM^3 n=(Mn)^3.