2.2 STRATEGIES FOR GETTING STARTED 33In other words,g (n^2 + b) = n if and only if 0 :S b < 2n + 1.
Now let us look at the "conjecture." For example, consider the case where b = I.
Then m = n^2 + 1 and g (m) = nand
f(m) = m+g(m) = n^2 + 1 +n.
Iterating the function f once more, we have
f^2 (m) = f(n^2 + n + 1) = n^2 + n +^1 + g(n^2 + n + I)
= n^2 + n + 1 + n = n^2 + 2n + 1 = (n + 1 f ,
so indeed the "conjecture" is true for b = 1.
Now let's look at b = 2. Then m = n^2 + 2 and g(m) = n provided that 2 < 2n + 1,
which is true for all positive integers n. Consequently,
f(m) =m+g(m) =n^2 +2+n,
andf^2 (n^2 +2) = n^2 +n+2+ g(n^2 +n+ 2).Since n+2 < 2n+ 1 is true for n > 1, we have g(n^2 +n+2) = n and consequently, if
n> 1,
Now we have discovered something fascinating: if m is 2 more than a perfect square,
and m > 1^2 + 2 = 3, then two iterations of f yields a number that is 1 more than a
perfect square. We know from our earlier work that two more iterations of f will then
give us a perfect square. For example, let m = 6^2 + 2 = 38. Then f(m) = 38 + 6 = 44
and f(44) = 44+6 = 50 and f^2 (50) = 64 (from the table). So f^4 (38) = 64. The only
number of the form n^2 + 2 that doesn't work is 12 + 2 = 3, but in this case, f (3) = 4,
so we are done.
We have made significant partial progress. We have shown that if m = n^2 + 1 or
m = n^2 + 2, then finitely many iterations of f will yield a perfect square. And we have
a nice direction in which to work. Our goal is getting perfect squares. The way we
measure partial progress toward this goal is by writing our numbers in the form n^2 + b,
where 0 :S b < 2n + 1. In other words, b is the "remainder." Now a more intriguing
conjecture is
If m has remainder b, then f^2 (m) has remainder b -1.
If we can establish this conjecture, then we are done, for eventually, the remainder will
become zero. Unfortunately, this conjecture is not quite true. For example, if m = 7 =
22 + 3, then f^2 (7) = 12 = 3^2 + 3. Even though this "wishful thinking conjecture" is
false, careful analysis will uncover something very similar that is true, and this will
lead to a full solution. We leave this analysis to you.