Advanced book on Mathematics Olympiad

Real Analysis 487

Pn′′+ 1 (x)=Pn′′(x)

(

2 Pn(x)+

1

n

)

+(Pn′(x))^2 ,

andPn(x)≥0, forx≥0. Convexity implies

Pn(x)≤

Pn(bn)−P( 0 )

bn− 0

x=

x

bn

, for 0≤x≤bn.

In particular, 1−^1 n=Pn(an)≤abnn. Together with the fact thatbn≤1, this means that

bn−an≤^1 n. By Cantor’s nested intervals theorem there exists a unique numbertsuch

thatan<t<bnfor everyn. This is the unique number satisfying 1−^1 n<Pn(t) < 1

for alln. We conclude thattis the unique number for which the sequencexn=Pn(t)

satisfies 0<xn<xn+ 1 <1 for everyn.

(26th International Mathematical Olympiad, 1985)

350.The answer to the question is yes. We claim that for any sequence of positive integers

nk, there exists a numberγ>1 such that(γk)kand(nk)khave infinitely many terms

in common. We need the following lemma.

Lemma.For anyα, β, 1 <α<β,the set∪∞k= 1 [αk,βk− 1 ]contains some interval of

the form(a,∞).

Proof.Observe that(β/α)k→∞ask→∞. Hence for largek,αk+^1 <βk−1, and

the lemma follows.

Let us return to the problem and prove the claim. Fix the numbersα 1 andβ 1 ,

1 <α 1 <β 1. Using the lemma we can find somek 1 such that the interval[αk 11 ,β 1 k^1 − 1 ]

contains some terms of the sequence(nk)k. Choose one of these terms and call itt 1.

Define

α 2 =t 11 /k^1 ,β 2 =

(

t 1 +

1

2

) 1 /k 1

.

Then[α 2 ,β 2 ]⊂[α 1 ,β 1 ], and for anyx∈[α 2 ,β 2 ],xk^1 =t 1. Again by the lemma,

there existsk 2 such that[αk 22 ,βk 22 − 1 ]contains a term of(nk)kdifferent fromn 1. Call

this termt 2. Let

α 3 =t 21 /k^2 ,β 3 =

(

t 2 +

1

2

) 1 /k 2

.

As before,[α 3 ,β 3 ]⊂[α 2 ,β 2 ]andxk^2 =t 2 for anyx ∈[α 3 ,β 3 ]. Repeat the con-
struction infinitely many times. By Cantor’s nested intervals theorem, the intersection
of the decreasing sequence of intervals[αj,βj],j= 1 , 2 ,...,is nonempty. Letγbe
an element of this intersection. Thenγkj=tj,j= 1 , 2 ,...,which shows that the
sequence(γj)jcontains a subset of the sequence(nk)k. This proves the claim.