Advanced book on Mathematics Olympiad

464 Real Analysis

Remark.In the particular casea=b=1, we obtain the well-known identity for the
Fibonacci sequenceFn+ 1 Fn− 1 −Fn^2 =(− 1 )n+^1.

307.A standard idea is to eliminate the square root. If we setbn=

√

1 + 24 an, then
bn^2 = 1 + 24 an, and so

b^2 n+ 1 = 1 + 24 an+ 1 = 1 +

3

2

( 1 + 4 an+

√

1 + 24 an)

= 1 +

3

2

(

1 +

1

6

(

b^2 n− 1

)

+bn

)

=

1

4

(b^2 n+ 6 bn+ 9 )=

(

bn+ 3

2

) 2

.

Hencebn+ 1 =^12 bn+^32. This is an inhomogeneous first-order linear recursion. We can
solve this by analogy with inhomogeneous linear first-order equations. Recall that ifa, b
are constants, then the equationf′(x)=af (x)+bhas the solution

f(x)=eax

∫

e−axbdx+ceax.

In our problem the general term should be

bn=

1

2 n+^1

+ 3

∑n

k= 1

1

2 k

,n≥ 1.

Summing the geometric series, we obtainbn= 3 + 2 n^1 − 2 , and the answer to our problem is

an=

bn^2 − 1

24

=

1

3

+

1

2 n

+

1

3

·

1

22 n−^1

.

(proposed by Germany for the 22nd International Mathematical Olympiad, 1981)

308.Call the expression from the statementSn. It is not hard to find a way to write it in
closed form. For example, if we letu= 1 +i

√

a, thenSn=^12 (un+un).
Notice thatunandunare both roots of the quadratic equationz^2 − 2 z+a+ 1 =0,
so they satisfy the recurrence relationxn+ 2 = 2 xn+ 1 −(a+ 1 )xn. The same should be
true forSn; hence

Sn+ 2 = 2 Sn+ 1 −(a+ 1 )Sn,n≥ 1.

One verifies thatS 1 =1 andS 2 = 1 − 2 kare divisible by 2. Also, ifSnis divisible by
2 n−^1 andSn+ 1 is divisible by 2n, then(a+ 1 )Snand 2Sn+ 1 are both divisible by 2n+^1 , and
hence so must beSn+ 2. The conclusion follows by induction.
(Romanian Mathematical Olympiad, 1984, proposed by D. Mihe ̧t)