Solution to May 2005 Problem

 

If the sequence a0, a1, a2, ... satisfies

            (1)            a1 = 1, and

            (2)            for all integers m and n with m ≥ n ≥ 0, a2m + a2n = 2(am+n + am–n),

determine a2005.

This problem appeared in the team competition sponsored by the Math Association of America's North Central Section, held at Concordia College (Minnesota) November 10, 2001.

We received solutions this month from

Anarag Agarwal (USA)

Philippe Fondanaiche, (France)

Theerasak Asawanonwiwat (Thailand)

H.N. Gupta (Regina)

Felix Arnaiz Lanzo (Spain)

Xavier Hecquet (France)

Ricardo Barroso Campos (Spain)

Wolfgang Kais (Germany)

Pierre Bornsztein (France)

Arne Loosveldt (Belgium)

Bernard Carpentier (France)

Patrick LoPresti (USA)

K.A. Chandrashekara (.com)

M. Marinescu (.com)

Zdravko Cetkovski (Macedonia)

Anonymous

Pablo de la Viuda (Spain)

Richard Wood  (Dartmouth NS)
Krishna Prasad (.com) Tran Thanh Phuong (.com)

Answer:

a2005 = 20052 = 4 020 025.  Indeed, for any positive integer n, n2 is the unique value of an that satisfies the given relations.

The best way to start a problem like this is to determine a few values of an.

Set m = n = 0 in (2):

Then a0 + a0 = 2(a0 + a0) says that 2a0 = 4a0, so that

(3)  a0 = 0.

Set n = 0 in (2) and let m be arbitrary:

a2m + a0 = 2(am + am), so that by (3)

(4)  a2m = 4am.

Set n = 1 in (2) and let m be arbitrary:

a2m + a2·1 = 2(am+1 + am–1) and, since a2 = 4a1 and a2m = 4am (both by (4)), we deduce that

(5)  am+1 = 2am – am–1 + 2a1.

Furthermore, replacing a1 in (5) by 1 according to (1) — and this is the only place were we will use (1) — we get finally

(6)  am+1 = 2am – am–1 + 2.

Starting from a0 = 0 and a1 = 1, we use (6) to find that a2 = 4, a3 = 9, a4 = 16, and so forth.  You can keep going until you reach n = 2005 or you see a pattern, whichever comes first.  Happily, all our correspondents observed that an = n2.  The problem does not end here however: one must prove that this observation actually solves the problem.  For this, it is not enough simply to check that an = n2 satisfies the given conditions (1) and (2).  Among the submissions were two satisfactory ways to finish the problem.

Proof by induction.

We already know that the claim an = n2 holds for 0 and for 1: a0 = 02 and a1 = 11.  Assume that ak = k2 for all k ≤ m.  It remains to use (6) to show that am+1 = (m + 1)2: 

am+1 = 2am– am-1 + 2
         = 2m2 – (m – 1)2 + 2
         = 2m2 – m2 + 2m – 1 + 2
         = (m +1)2

and the proof is complete.

Proof by the theory of first order difference equations.

We recognize (6) combined with the initial conditions a0 = 0 and a1 = 1 to be an initial-value difference equation.  The theory tells us that there exists a unique solution in the form an = A + Bn + Kn2.  We have already determined that A = B = 0, and K = 1; that is, the unique solution is an = n2.  This completes our second argument.

Further comments.

  1. Note that using equation (5) (without condition (1)), we would have K = a1, which means the solution would be an = a1 n2.
  2. Hecquet provided a second solution that gives a direct answer that is more efficient than applying equation (6) 2005 times.  His idea is to reduce the problem to one of evaluating terms whose index is a power of 2; he can then repeatedly apply (4) to powers of 2: a2k = 4a2k-1.  The first three steps are

a2005 = a(1024+981) = 2a1024 + 2a981 - a43
a981 = a(512+469) = 2a512 + 2a496 – a43
a469 = a(256+213) = 2a256 + 2a213 – a43

With a few shortcuts he arrives after eight steps at a list of equations whose terms all have known values, which he then evaluates to get a2005 = 4 020 025.  Had we held off posing this problem until the year 2048, his method would have worked really well!