Proof by Mathematical Induction
Proof by Mathematical Induction is a method of proof which Computer Scientists encounter on a regular basis. Intuitively, this method of proof uses the validity of one instance of an algorithm to prove the validity of another instance. After such a proof is constructed we are left with the statement - IF there is an instance of the algorithms that is true THEN there is this second instance which we have proved to be true.
Often we encounter such a proof when dealing with counting. The quintessential Mathematical Induction problem is shown in the following example.
1 + 2 + ... + n = n(n+1)/2
Whether or not this is true for any n is of little concern at this point. What is important is finding a relationship between the instance n and another instance, say n + 1. This is done in the following manner:
1. I must prove that if there is an instance of the function (an n) that is true than another instance will be true.
IF 1 + 2 + ... + n = n(n+1)/2 THEN 1 + 2 + ... + n + (n+1) = (n+1)((n+1)+1)/2
We MUST use our original HYPOTHESIS in our proof in order to show a relationship between one instance and the next instance with respect to our hypothesis. Our hypothesis was stated above and we see the 1 + 2 + ... + n again in our INDUCTION STEP so we use our hypothesis by replacing our equivalent statements.
n(n+1)/2 + (n+1) = (n+1)((n+1)+1)/2
This statement could be meaningless, because our hypothesis could be false for ALL n,we do not know yet, but we finish the algebra in order to see the equivalency.
n(n+1)+(2n+2)/2 = (n+1)(n+2)/2
(n^2 + n + 2n + 2)/2 = (n+1)(n+2)/2
(n^2 + 3n + 2)/2 = (n+1)(n+2)/2
(n+1)(n+2)/2 = (n+1)(n+2)/2
We have now proved that IF our hypothesis is true of an n, it will be true for n+1.
Let's see if our hypothesis is correct for n = 1 (since that's where our original hypothesis began).
1 = 1(2)/2 = 1
Q.E.D.
Our hypothesis is correct for n = 1 so by our proof it is correct for n+1 = 2. Recusively, our hypothesis is correct for n = 2 so it is correct for n+1 = 3, etc. We have PROVED that our hypothesis is correct for the set of natural numbers.
You might be wondering what would have happened had we tried n = 2 instead of n = 1 in our BASE STEP, lets see...
1 + 2 = 2(3)/2 = 3
Since we know that our hypothesis is true for n = 2 we know that it is true for n + 1 = 3, etc. but do we know if it is true for n = 1? No, we have not proved that our hypothesis is correct for all natural numbers.
Let's take a look at another (more interesting) instance of mathematical induction:
1. Begin with a string of length 0, the empty string, e, is within our language, asKleene star produces all possible strings over its operands including that of length zero.
2. Next, our hypothesis is that all strings of length n or less over S are within our language. That is, d0 -> d1 -> ... -> dn, where n >= 0, is an element of R, where d represents the derivation step and is followed by the step number d+1. at each step of the derivation an element of S is concatenated to our string.
3. Our inductive step is that all strings of length n+1 are within our language. By our hypothesis all strings of length n are within our language, so therefore we must analyze the n+1st element. We know that since this is a string over S the n+1st element is either a or b. If the element is a, our string passes, if the element is b, our string also passes, since R=(a U b)*. The n+1st element will never be the empty string, e, since our base case is where n = 0, the empty string,the n+1st element is always an element of S.
Q.E.D.
Design and content by Kevin L. Stern
All Rights Reserved.
Material on this page may be reprinted for educational, non-commercial purposes
as long as Northeastern Illinois University is informed of such usage, all
material with an author listed is the intellectual property of that author
and may not be reproduced without permission.