Maths Olympiad Prep

Library / /17 of 61

Algebra Difficulty 5.3 AIME, harder Prove it Ibero-American Mathematical Olympiad

Problem:

The sequence ana_{n} is defined as follows: a1=56a_{1}=56, an+1=an1/ana_{n+1}=a_{n}-1/a_{n}. Show that an<0a_{n}<0 for some nn such that 0<n<20020<n<2002.

Solution

Solution:

Note that whilst ana_{n} remains positive we have a1>a2>a3>>ana_{1}>a_{2}>a_{3}>\ldots>a_{n}. Hence if ama_{m} and am+na_{m+n} are in this part of the sequence, then am+1=am1/ama_{m+1}=a_{m}-1/a_{m}, am+2=am+11/am+1<am+11/am=am2/ama_{m+2}=a_{m+1}-1/a_{m+1}<a_{m+1}-1/a_{m}=a_{m}-2/a_{m}. By a trivial induction am+n<amn/ama_{m+n}<a_{m}-n/a_{m}.

If we use one step then we need 562=313656^{2}=3136 terms to get a1+3136<56562/56=0a_{1+3136}<56-56^{2}/56=0, which is not good enough. So we try several steps.

Thus suppose that an>0a_{n}>0 for all n2002n\leq 2002. Then we get successively:

a337<56336/56=50a_{337}<56-336/56=50

a837<50500/50=40a_{837}<50-500/50=40

a1237<40400/40=30a_{1237}<40-400/40=30

a1537<30300/30=20a_{1537}<30-300/30=20

a1737<20200/20=10a_{1737}<20-200/20=10

a1837<10100/10=0a_{1837}<10-100/10=0.

Contradiction. So we must have an<0a_{n}<0 for some n<2002n<2002.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.