----------------------------------------------------------------------------
Lemma:
1, 0 <= G(n) - G(n - 1) <= 1 for
n > 0
2. G(n - 2) < G(n) for
n > 1
Proof:
G(1) - G(0) = 1 so we have our base-case. Assume that
0 <= G(m) - G(m - 1) <= 1 for
m < n.
Then we have
Code:
G(n) - G(n - 1) = n - GG(n - 1) - n + 1 + GG(n - 2) (Definition of G)
= 1 - GG(n - 1) + GG(n - 2) EQN1
= 1 - (GG(n - 1) - GG(n - 2))
and by the inductive hypothesis,
G(n - 1) = G(n - 2) or
G(n - 1) = G(n - 2) + 1.
Assume the former. Then
GG(n - 1) - GG(n - 2) = 0 and so
G(n) - G(n - 1) = 1. This suffices to show
part 1 for this case. Then
G(n) - G(n - 2) = [G(n) - G(n - 1)] + [G(n - 1) - G(n - 2)] = 1 + 0, and
part 2 holds.
Consider the case where
G(n - 1) - G(n - 2) = 1. Then
G(n) - G(n - 2) = [G(n) - G(n - 1)] + [G(n - 1) - G(n - 2)] = G(n) - G(n - 1) + 1.
■
Proposition:
1) For all m > 0, there exists at least one n >= 0 such that G(n) = m.
2) There exist at most two such n for any given m.
Proof:
Assume that there exists m such that there is no n with G(n) = m and that it is the
least such m. Then there exists an n such that G(n) = m - 1. if G(n + 1) = m + 1
then Lemma 4 is violated. So G(n + 1) = m - 1. Take G(n + 2). If G(n + 2) = m + 1,
then, again, Lemma 4 is violated. But now if G(n + 2) = m - 1, Lemma 5 is violated.
We are left with the conclusion that G(n + 2) = m contrary to our assumption that no
such n exists. Hence there must be no such m. So for every m, there exists at least
one n such that G(n) = m.
Now suppose that G(n) = G(n + j) for j > 0. Then G(n + j) - G(n) = 0 which, by lemma 4
and 5 is only possible if j = 0 or j = 1. Hence, only a pair of successive integers can
have the same image under G and there can be at most two such integers.
■