17th Iberoamerican 2002

The sequence a_n is defined as follows: a₁ = 56, a_n+1 = a_n - 1/a_n. Show that a_n < 0 for some n such that 0 < n < 2002.

Solution

Note that whilst a_n remains positive we have a₁ > a₂ > a₃ > ... > a_n. Hence if a_m and a_m+n are in this part of the sequence, then a_m+1 = a_m - 1/a_m, a_m+2 = a_m+1 - 1/a_m+1 < a_m+1 - 1/a_m = a_m - 2/a_m. By a trivial induction a_m+n < a_m - n/a_m.

If we use one step then we need 56² = 3136 terms to get a₁₊₃₁₃₆ < 56 - 56²/56 = 0, which is not good enough. So we try several steps.

Thus suppose that a_n > 0 for all n<= 2002. Then we get successively:
a₃₃₇ < 56 - 336/56 = 50
a₈₃₇ < 50 - 500/50 = 40
a₁₂₃₇ < 40 - 400/40 = 30
a₁₅₃₇ < 30 - 300/30 = 20
a₁₇₃₇ < 20 - 200/20 = 10
a₁₈₃₇ < 10 - 100/10 = 0.

Contradiction. So we must have a_n < 0 for some n < 2002.

Using Maple, we find that a_n is first negative for n = 1572.

17th Ibero 2002

© John Scholes
jscholes@kalva.demon.co.uk
19 Oct 2002