Advanced book on Mathematics Olympiad

(ff) #1

752 Combinatorics and Probability


which can be interpreted as the characteristic equation of a recursive sequencexn+ 1 −


(^4) √xn+xn− 1 =0. Given that the general formula of the terms of the sequence is( 1 +
3 )( 2 +



3 )n+( 1 −


3 )( 2 −


3 )n, we also see thatx 0 =2 andx 1 =10. An induction
based on the recurrence relation shows thatxnis divisible by 2 but not by 4. It follows
thatkis an integer and the problem is solved.
(Romanian Team Selection Test for the International Mathematical Olympiad, 1999,
proposed by D. Andrica)


864.We have


an+bn^3



2 +cn^3


4 =

√ (^32) ( 1 +√ (^32) +√ (^34) )n
(^3



2 )n

= 2 −

n 3
(^3


2 +^3


4 + 2 )n

= 2 −

n 3
( 1 +( 1 +

√ 3

2 +

√ 3

4 ))n= 2 −

n 3 ∑n
k= 0

(

n
k

)

(ak+bk

√ 3

2 +ck

√ 3

4 ).

Hence


an+bn^3


2 +cn^3


4 = 2 −

n 3 ∑n
k= 0

(

n
k

)

ak+ 2 −

n 3 ∑n
k= 0

(

n
k

)

bk^3


2 + 2 −

n 3 ∑n
k= 0

(

n
k

)

ck^3


4.

The conclusion follows from the fact that 2−n/^3 is an integer ifnis divisible by 3, is
an integer times^3



4ifnis congruent to 1 modulo 3, and is an integer times^3


2ifnis
congruent to 2 modulo 3.
(Revista Matematica din Timi ̧soara ̆ (Timi ̧soara Mathematics Gazette), proposed by
T. Andreescu and D. Andrica)


865.First solution: We prove the formula by induction onn. The casen=1 is straight-
forward. Now let us assume that the formula holds fornand let us prove it forn+1.
Using the induction hypothesis, we can write


[x+y]n+ 1 =(x+y−n)[x+y]n=(x+y−n)

∑n

k= 0

(

n
k

)

[x]n−k[y]k

=

∑n

k= 0

(

n
k

)

((x−k)+(y−n+k))[x]k[y]n−k

=

∑n

k= 0

(

n
k

)

(x−k)[x]k[y]n−k+

∑n

k= 0

(

n
k

)

(y−(n−k))[x]k[y]n−k

=

∑n

k= 0

(

n
k

)

[x]k+ 1 [y]n−k+

∑n

k= 0

(

n
k

)

[x]k[y]n−k+ 1

=

∑n+^1

k= 1

(

n
k− 1

)

[x]k[y]n−k+ 1 +

∑n

k= 0

(

n
k

)

[x]k[y]n−k+ 1
Free download pdf