next up previous
Next: Wednesday, May 3, 2000 Up: Lecture Notes Previous: Monday, May 1, 2000

Tuesday, May 2, 2000

Complete Induction

We need to look at more general forms of induction, at least briefly.

Theorem (complete induction):  (An E N.(Ax < n.Px)->Pn) -> (Ax E N.Px)

Proof:  By induction as usual.

Suppose that (Ak E N.(Ax < k.Px)->Pk) is true.  We prove 
(An E N.(Ax <= n.Px)) by induction (notice that this implies (An.Pn)).

Basis step:

Since (Ax < 0.Px) is vacuously true, P0 must be true by the hypothesis
(Ak E N.(Ax < k.Px)->Pk), and this implies (Ax <= 0.Px), completing the
proof of the basis step.

Induction Step:

Suppose that (Ax <= n.Px) (this is our inductive hypothesis).  We want
to show that (Ax <= n+1.Px).  If x <= n+1, we either have x <= n,
in which case Px follows by application of the inductive hypothesis,
or x = n+1.  So all that remains is to prove P(n+1).  By ind hyp again,
we have (Ax < n+1.Px) (since x < n+1 <-> x <= n) from which our
hypothesis (Ak E N.(Ax < k.Px)->Pk), instantiated with k = n+1, allows
us to deduce P(n+1).  So we have shown (Ax <= n+1.Px) as desired, 
completing the proof by induction of (An E N.(Ax <= n.Px)), from which
(An E N.Pn) follows immediately.

An Example

Complete induction is often used when functions defined by more general
forms of recursion are used.  For example, complete induction is often used
when the Fibonacci numbers are involved.

I'll do an example which Grantham also does in his book, deriving
a formula for the Fibonacci numbers, but we will also do a little
motivation!

The Fibonacci numbers have the following recursive definition:

F(0) = 0
F(1) = 1
F(n+2) = F(n) + F(n+1)

The first few terms are 0,1,1,2,3,5,8...

(the 0 is only there because we start indexing at 0).

They belong to a whole family of sequences G satisfying

G(n+2) = G(n) + G(n+1)

For example, the ``Lucas numbers'' are often studied (I'll start their
indexing at 1):

1,3,4,7,11,18...

Here are some rather obvious facts about these sequences:

Any sequence of this kind is determined by its first two elements.

Suppose G and H are both sequences of this kind; then G+H is also
a sequence of this kind.  So is cG where c is a constant.

Now comes the ``trick'':

Suppose we could find a real number x such that 1+x = x^2;
then the sequence 1,x,x^2,x^3... would belong to this family,
because x^n + x^(n+1) = x^n*(1+x) = x^n*x^2 = x^(n+2).

Of course we can find such a number x -- we can use the quadratic formula
to find two of them!

x^2-x-1 = 0 has roots (1 +/- sqrt(1+4))/2 by the quadratic formula;
the two roots are x_1 = (1+sqrt(5))/2 and x_2 = (1-sqrt(5))/2.

Now we can use this to develop a formula for the Fibonacci sequence (or
for any sequence of this family). 

Suppose that F(n) = c_1*x_1^n + c_2*x_2^n.

We have F(0) = c_1*1 + c_2*1 = 0  so c_2 = -c_1.

We have F(1) = c_1*x_1 + c_2*x_2 = c_1*x_1 - c_1*x_2 = c_1*(x_1-x_2)
= c_1*sqrt(5) = 1, so c_1 = 1/sqrt(5) and c_2 = -1/sqrt(5), and we obtain
the formula F(n) = (x_1^n - x_2^n)/sqrt(5).

The context in which you see this formula is the much more mysterious
 
Exercise:  Prove by complete induction that F(n) =  (x_1^n - x_2^n)/sqrt(5)
for each n (where x_1 and x_2 are defined as above).

Proof:

Suppose for a fixed n that this statement is true for every smaller
value of n.  We show that it is true for n as well.

Case 1:  n = 0  (x_1^0 - x_2^0)/sqrt(5) = (1-1)/sqrt(5) = 0
= F(0)

Case 2:  n = 1  (x_1^1 - x_2^1)/sqrt(5) = sqrt(5)/sqrt(5) = 1
as desired

Case 3:  n > 1  We have by the hypothesis of our complete induction
that F(n-1) = (x_1^(n-1) - x_2^(n-1))/sqrt(5) and 
F(n-2) = (x_1^(n-2) - x_2^(n-2))/sqrt(5).

We can then compute F(n) = F(n-1) + F(n-2) = (x_1^(n-1) - x_2^(n-1))/sqrt(5)
+ (x_1^(n-2) - x_2^(n-2))/sqrt(5) = 
((x_1^(n-1)+x_1^(n-2))-(x_2^(n-1)+x_2^(n-2)))/sqrt(5) =
((x_1^(n-2)*(1+x_1))-(x_2^(n-2)*(1+x_2)) = 
(by algebraic facts about x_1 and x_2 already shown above)
((x_1^(n-2)*x_1^2)-(x_2^(n-2)*x_2^2) =
(x_1^n - x_2^n)/sqrt(5) as desired, completing the proof.

The fact that we need special cases for n=0 and n=1 has to
do with the special form of the definition of the Fibonacci
numbers (we could also develop a special ``Fibonacci induction''
which looks like standard induction except that there are two
basis steps and the induction step uses the two previous values,
but the more powerful generalization to complete induction is more
generally useful).

This is where we stopped on May 2.



Randall Holmes
2000-05-05