Advanced book on Mathematics Olympiad

466 Real Analysis

λ^3 − 3 λ^2 + 6 λ− 4 = 0.

An easy check shows thatλ 1 =1 is a solution to this equation. Sinceλ^3 − 3 λ^2 +
6 λ− 4 =(λ− 1 )(λ^2 − 2 λ+ 4 ), the other two solutions areλ 2 , 3 = 1 ±i

√

3, that is,

λ 2 , 3 = 2 (cosπ 3 ±isinπ 3 ). It follows that the formula for the general term of a sequence

satisfying the recurrence relation is

ak=c 1 +c 22 kcos

kπ

3

+c 32 ksin

kπ

3

+ 667 k, k≥ 0 ,

withc 1 ,c 2 , andc 3 some real constants.
Ifc 2 >0, thena 3 ( 2 m+ 1 )will be negative for largem, and ifc 2 <0, thena 6 mwill be
negative for largem. Sincef (n)can take only positive values, this implies thatc 2 =0.
A similar argument shows thatc 3 =0. It follows thatak=c 1 + 667 k. So the first term
of the sequence determines all the others. Sincea 0 =n, we havec 1 =n, and hence
ak=n+ 667 k, for allk. In particular,a 1 =f (n)=n+667, and hence this is the only
possible solution.
(Mathematics Magazine, proposed by R. Gelca)
311.We computex 3 =91,x 4 =436,x 5 =2089. And we already suggested by placing
the problem in this section that the solution should involve some linear recurrence. Let us
hope that the terms of the sequence satisfy a recurrencexn+ 1 =αxn+βxn− 1. Substituting
n=2 andn=3 we obtainα= 5 ,β=−1, and then the relation is also verified for the
next term 2089= 5 · 436 −91. Let us prove that this recurrence holds in general.
Ifynis the general term of this recurrence, thenyn=arn+bsn, where

r=

5 +

√

21

2

,s=

5 −

√

21

2

,rs= 1 ,r−s=

√

21 ;

and

a=

7 +

√

21

14

,b=

7 −

√

21

14

,ab= 1.

We then compute

yn+ 1 −

yn^2

yn− 1

=

yn+ 1 yn− 1 −yn^2

yn− 1

=

(arn+^1 +bsn+^1 )(arn−^1 +bsn−^1 )−(arn+bxn)^2

arn−^1 +bsn−^1

=

ab(rs)n−^1 (r−s)^2

yn− 1

=

3

yn− 1

.

Of course, 0<yn^3 − 1 <1 forn≥2. Becauseyn+ 1 is an integer, it follows that

yn+ 1 =

⌈

yn^2

yn− 1

⌉

.