Advanced book on Mathematics Olympiad

124 3 Real Analysis

375.Leta 0 =1994 andan+ 1 = a
n^2
an+ 1 for each nonnegative integern. Prove that for
0 ≤n≤998, the number 1994−nis the greatest integer less than or equal toan.

376.Fixka positive integer and define the sequence

an=

⌊

(k+

√

k^2 + 1 )n+

(

1

2

)n⌋

,n≥ 0.

Prove that

∑∞

n= 1

1

an− 1 an+ 1

=

1

8 k^2

.

The telescopic method can be applied to products as well. Within the first, relatively
easy, problem, the reader will recognize in disguise the Fermat numbers 2^2
n
+1,n≥1.

Example.Define the sequence(an)nbya 0 =3, andan+ 1 =a 0 a 1 ···an+2,n≥0.
Prove that

an+ 1 = 2 (a 0 − 1 )(a 1 − 1 )···(an− 1 )+ 1 , for alln≥ 0.

Solution.The recurrence relation givesa 0 a 1 ···ak− 1 =ak−2,k≥1. Substitute this
in the formula forak+ 1 to obtainak+ 1 =(ak− 2 )ak+2, which can be written as
ak+ 1 − 1 =(ak− 1 )^2. And so

ak+ 1 − 1

ak− 1

=ak− 1.

Multiplying these relations fork= 0 , 1 ,...,n, we obtain

an+ 1 − 1

an− 1

·

an− 1

an− 1 − 1

···

a 1 − 1

a 0 − 1

=(an− 1 )(an− 1 − 1 )···(a 0 − 1 ).

Since the left-hand side telescopes, we obtain

an+ 1 − 1

a 0 − 1

=(a 0 − 1 )(a 1 − 1 )···(an− 1 ),

and the identity follows. 

A more difficult problem is the following.

Example.Compute the product

∏∞

n= 1

(

1 +

(− 1 )n

Fn^2

)

,

whereFnis thenth Fibonacci number.