| All variables are non-negative integers.
(1) F(0,y) = 1.
(2) F(1,0) = 2.
(3) F(x,0) = x+2 for x >= 2.
(4) F(x+1,y+1) = F(F(x,y+1),y) for x+1 >= 2.
Theorem: F(x,2) = 2^x.
Lemma: F(x,1) = 2x, for x > 0.
F(1,1) = F(F(0,1),0) = F(1,0) = 2, so the lemma is true for x = 1.
Now consider an x > 1.
Suppose F(k,1) = 2k for k > 0 for all k < x. Then F(x,1) =
F(F(x-1,1),0) = F(2(x-1),0) = 2(x-1)+2 = 2x. (Note that 2(x-1) must
be greater than or equal to two, since x is greater than one, so
(3) applies to F(2(x-1),0).
By induction, the lemma is true.
Proof: F(0,2) = 1, by (1).
Now consider an x > 0.
Suppose F(k,2) = 2^k for all k < x. Then F(x,2) = F(F(x-1,2),1) =
F(2^(x-1),1) = 2(2^(x-1)) = 2^x.
By induction, the theorem is true.
-- edp
|