Solution for January 2009

The Problem:
	MP83 January 2008 Let a0 = 2009 and for any non-negative integer n.  Prove that 2009 – n is the greatest integer less than or equal to an for 0 ≤ n ≤ 1005.

Correct responses:

This month's problem is a modified version of short-listed problem A1 proposed for the 35th International Mathematical Olympiad (Hong Kong, 1994).  Correct solutions were submitted to us by Bojan Basic (Serbia) Seb Lebre (?) Luigi Bernardini (Italy) Matthew Lim (USA) Lou Cairoli (USA) Jeff Lindstrom (Ontario) Bernard Carpentier (France) Catherine Nadault (France) Bernard Collignon (France) Shpetim Rexhepi (Macedonia) Olivier Cyr (France) John T. Robinson (USA) Philippe Fondanaiche (France) Heri Setiyawan (Indonesia) Cornel Gruian (Rumania) Albert Stadler (Switzerland) Omran Kouba (Syria)

The solution:

All the solutions had much in common:  It follows quickly from the definition that a_n is positive for all n; also
,
whence

From this we deduce that the sequence is decreasing: a₀ > a₁ > ... > a_n > ... .  Moreover, we havefor all n > 0,

        (1)

Let  d_n = a_n – (2009 – n).  If we can show that the difference d_n < 1 for n ≤ 1005, then we can conclude that 2009 – n is the greatest integer less than or equal to a_n, as claimed.  From the third equation in (1),

        (2)

Again, because the sequence of a_k's is decreasing we have 1/(a_k + 1) < 1/(a_n–1 + 1) for k < n – 1. From (1), which says that a₁₀₀₄ > 2009 – 1004 = 1005, we see that for 0 ≤ n ≤ 1005,

,

which completes the argument.

Comments.  Even for values of n well beyond 1005 it is clear that 2009 – n is the greatest integer less than or equal to an (in symbols, ).  Several correspondents investigated how far this equality continues to hold.  For the answer one must look more closely at the precise value of the difference d_n = a_n - (2009 - n), which by (2) is

Because a_n is positive and decreasing to zero, the series on the right grows without bound; thus, there must exist an integer, call it N, for which d_N < 1 while d_N+1 > 1.  Indeed, a computer tells us that N = 1271; that is,

, while

Lim, Kouba, Nadault, Stadler, Fondanaiche and Robinson all showed that if one knows some calculus, it is easy to determine without a computer that N must be either 1270 or 1271.  Here is Lim's argument (with contributions from each of the others).

An upper bound on N.  (We use the definition of N: for k ≤ N, a_k – (2009 – k) < 1; that is, a_k < 2010 – k).)

whence , and therefore

A lower bound on N.   (Here we use that for k ≤ N, 1 + (a_k – (2009 – k)) > 1; that is, 1 + a_k > 2010 – k.)

whence , and therefore

To eliminate 1270 as a possible value for N we need a better estimate for the lower bound.  The work is not so much harder, but only Nadault persevered.  We have posted her lovely argument on our French web page for those who would like to see the details.