S(n) involving a variable n
is true.
Now, letS(n)be some arbitrary statement about an integer n. In the simplest form of an inductive proof of the statementS(n), we prove two facts: 1. The basis case, which is frequently taken to beS(0). However, the basis can beS(k)for any integer k, wit hthe understanding that then the statementS(n)is proved only for n >= k . 2. The inductive step, where we prove that for all n >= 0 ,S(n)impliesS(n + 1 ). In this part of the proof, we assume that the statementS(n)is ture.S(n)is called the induction hypothesis, and assuming it to be tree, we must then prove thatS( n + 1)is true.
In the following discussion SUM( n , i = 0 ) stands for the summation sign
with "n" over it and "i = 0" below. Also exponent operator is represented
as "^". An example of mathematical induction (Foundations
p. 33-34 ):
STATEMENT S(n) : SUM( n , i = 0) 2^i = 2^( n + 1) - 1
for any n >= 0
BASIS
To prove the basis, we substitute 0 for n in the equation S(n).
Then S(n) becomes
SUM( 0 , i = 0 ) 2^i = 2^1 - 1 (2.2)
There is only one term, for i = 0 , in te summation on the left side of
Equation (2.2), so that the left side of (2.2) sums to 2^0 or 1. The right
side of Equation (2.2) which is 2^1 - 1 , or 2 - 1, also has the value 1.
Thus we have proved the basis of S(n); that is , we have shown
that this equality is true for n = 0 .
INDUCTION
Now we must prove the inductive step; we assume that S(n) is true,
and we preve the same equality with n + 1 susbstituted for n.
The equation to be proved, S(n + 1), is
SUM( n + 1 , i = 0 ) 2^i = 2^( n + 2 ) - 1 (2.3)
To prove Equation (2.3), we begin by considering the sum on the left side,
SUM( n + 1 , i = 0 ) 2^i. This sum is almost the same as the sum on the
left side of S(n), with is SUM( n + 1 , i = 0 ) 2^i, except that
(2.3) also has a term for i = n + 1, that is, the term 2^(n + 1).
Since we are allowed to assume that the inductive hypothesis S(n)
is ture in out proof of Equation (2.3), we should contrive to use S(n)
to advantage. We do so by breaking the sum in (2.3) into two parts, one of
which is the sum in S(n). That is, we separate otu the last
term, where i = n + 1, and write
SUM( n + 1 , i = 0 ) 2^i = SUM( n , i = 0 ) 2^i + 2^(n + 1 ) (2.4)
Now we can make use of S(n) by subsituting it s right side,
2^(n + 1 ) - 1 , for SUM( n , i = 0 ) 2^i in Equation (2.4)
SUM( n + 1 , i = 0 ) 2^i = 2^(n + 1) - 1 + 2^(n + 1 ) (2.4)
When we simplify the right side of Equation (2.5), it becomes 2 x 2^(n+ 1) - 1,
or 2^( n + 2 ) - 1. Now we see that the summation of the left side of (2.5)
is the same as the left side of (2.5), ahd the right side of (2.5) is equal
to the right side of (2.3). We have thus proved the validity of Equation (2.3)
by using the equality S(n); that proof is the inductive step.
The conclusion we draw is that S(n) holds for all nonnegative value of n.
Which is a realitively straight forward use of induction. An informal
explanation of why induction works follows. Say we needed to prove that the
statement S(k) was true for some nonnegative integer k.
If k = 0 then the basis is the justification. If k > 0 then
since we know that S(n) implies S( n + 1), iteratively "crank through" setting
n equal to 0 .. k until you arrive at k. That's not
a rigorous mathematical proof, but it is hopefull, an intuitive one.
So to quote from Foundations( p. 24)
...In computer science, we often wish to prove, formally or informally, that a statement S(n) about a program is true. The statement S(n) might, for example, describe what is true on the nth iteration of some loop or what is true for the nth recursive call to some procedure. Proofs of this sort are generally inductive.
Additionally, relying on the Inductive Hypothesis is very similar to relying on a recursive call to "do the right thing". Therefore, an inducitive proof of a recursive function often bare a striking resemblence to one another.
The following is an informal inductive proof of factorial. It probably would not fly in a discrete math class, but it will do. In the following PRODUCT stands for that "capital" pi symbol. It stands for what SUM does but only you multiply the terms instead of add.
1 if n = 0
STATEMENT S(n) n! = n * ( n - 1)! if n > 0
Were n >= 0 .
BASIS
There are really two basis conditions in this proof
1. If n = 0 then the equation becomes
0! = 1
which we know is true.
2. If n = 1 then the equation becomes
1! = 1 * 0!
1! = 1 * 1
after subsituting in the first basis condition and is clearly true.
Induction
If we assume that S(n) is true, then we need to prove that
S(n + 1) is
(n + 1)! = ( n + 1 ) * n!
we can modify the right hand side by saying
(n + 1)! = n! * ( n + 1 )
At this point if we note ( a if rigorous prove by induction ) that n!
equals 1*2*..*n then the right hand side becomes.
(n + 1)! = 1*2*..*n * ( n + 1 )
Now I'd like to turn this into code.
1. The BASIS becomes by template for what is
the base case of my recursion.
2. Secondly proving how to construct S(n + 1) from
S( n ) should give me an idea on what to
do in the nonbase case.
So in following step 1 I come up with the following code fragment
(cond ( ( = n 0 ) 1 )
( ( = n 1 ) 1 )
Next from the induction part of the proof I know that I can contruct the
S(n + 1 ) from S(n) by multiplying by n + 1.
If I apply a negtive 1 to everything that becomes
S(n ) = n * S( n - 1 )
[ NOTE: you can do a proof by induction by assuming S(n - 1) is true and
then show S( n ). All that matters that you show that for one
incremental construction step "things" are still true. ]
So I can change this into a another code fragment.
( n * (fact (1- n )))
So all together now:
(defun fact ( n )
(cond ((= n 0) 1 )
((= n 1) 1 )
(t ( n * (fact (1- n ))))))
I've outlined some other quasi induction proofs for some of my solutions. See the Design Rationale for the corresponding solution on the "Guide to the Solutions" page ( if there is one ) for any induction proofs.