28 CHAPTER 2 STRATEGIES FOR INVESTIGATING PROBLEMS
which yields ao + ao = ao, so ao = O. Now use the known indices 0, 1: plug m = 1, n =
o into (1) and we have 2al = i(a 2 +ao) = azl^2 , so a 2 = 4al = 4. More generally, if
we just fix n = 0, we have 2am = a 2 m/2, or a 2 m = 4am. Now let 's plug in m = 2 , n = 1:
1
aUI +a (^2) - 1 = 2 (a 4 +a 2 ).
Since a 4 = 4a 2 = 4 · 4 = 16, we have a 3 +al = i(16+4) , so a 3 = 9. At this point, we
are ready to venture the conjecture that an = n^2 for all n = 1,2,3 .... If this conjecture
is true, a likely method of proof will be mathematical induction. See page 45 below
for an outline of this technique and page 47 for the continuation of this problem.
Example 2.2.2 (AIME 1985) The numbers in the sequence
101 , 104, 109 ,1 16, ...
are of the form an = 100 + n^2 , where n = 1,2, (^3) , .... For each n, let dn be the greatest
common divisor^4 of an and an+ I. Find the maximum value of dn as n ranges through
the positive integers.Partial Solution: Just writing out the first few terms of an leads us to speculate
that the maximum value of dn is 1, since consecutive terms of the sequence seem to be
relatively prime. But first, we should look at simpler cases. There is probably nothingspecial about the number 100 in the definition of an , except perhaps that 100 = 102.
Let's look at numbers defined by an = u + n^2 , where u is fixed. Make a table.
u al a 2 a 3 a 4 a5 a 6 a 7
1 2 5 10 17 26 37 50
2 3 6 11 18 27 38 51
3 4 7 12 19 28 39 52
We marked with boldface the pair of consecutive terms in each row that had the
largest GCD (at least the largest for the first seven terms of that row). Notice that whenu = 1, then a 2 and a 3 had a GCD of 5. When u = 2, then a 4 and a5 had a GCD of9, and
when u = 3, then a 6 and a 7 had a GCD of 13. There is a clear pattern: we conjecture
that in general, for any fixed positive integer u, then a 2 u and a 2 u+ 1 will have a GCD of
4u + 1. We can explore this conjecture with a little algebra:
a 2 u = u + (2u)^2 = 4u^2 + u = u( 4u + 1),
whilea 2 u+1 = u+ (2u+ 1)^2 = 4u^2 +4u+ 1 +u = 4u^2 +5u+ 1 = (4u+ l)(u+ 1),
and, sure enough, a 2 u and a 2 u+ 1 share the common factor 4u + 1.
This is encouraging progress, but we are not yet done. We have merely shownthat 4u + 1 is a common factor of a 2 u and a 2 u+ I, but we want to show that it is the
greatest common factor. And we also need to show that the value 4u + 1 is the greatest
(^4) See (^3) .2. (^4) , (^3) .2.17 and Section 7.1 for more information about the greatest common divisor.