<< Chapter < Page | Chapter >> Page > |
F<- 2 * 3
i<- 3 + 1
producing F = 6 and i = 4.
Since i = 4, the while loop is not entered any longer, F = 6 is returned and the algorithm is terminated.
To prove that the algorithm is correct, let us first note that the algorithm stops after a finite number of steps. For i increases one by one from 1 and n is a positive integer. Thus i eventually becomes equal to n.
Next, to prove that it computes n!, we show that after going through the loop k times, F = k ! and i = k + 1 hold. This is a loop invariant and again we are going to use mathematical induction to prove it.
Proof by induction.
Basis Step: k = 1. When k = 1, that is when the loop is entered the first time, F = 1 * 1 = 1 and i = 1 + 1 = 2. Since 1! = 1, F = k! and i = k + 1 hold.
Induction Hypothesis: For an arbitrary value m of k, F = m! and i = m + 1 hold after going through the loop m times.
Inductive Step: When the loop is entered (m + 1)-st time, F = m! and i = (m+1) at the beginning of the loop. Inside the loop,
F<- m!* (m + 1)
i<- (m + 1) + 1
producing F = (m + 1)! and i = (m + 1) + 1.
Thus F = k! and i = k + 1 hold for any positive integer k.
Now, when the algorithm stops, i = n + 1. Hence the loop will have been entered n times. Thus F = n! is returned. Hence the algorithm is correct.
There is another form of induction over the natural numbers based on the second principle of induction to prove assertions of the form ∀x P(x). This form of induction does not require the basis step, and in the inductive step P(n) is proved assuming P(k) holds for all k<n . Certain problems can be proven more easily by using the second principle than the first principle because P(k) for all k<n can be used rather than just P(n - 1) to prove P(n).
Formally the second principle of induction states that
if ∀n [ ∀k [ k<n $\to $ P(k) ] $\to $ P(n) ] , then ∀n P(n) can be concluded.
Here ∀k [ k<n $\to $ P(k) ] is the induction hypothesis.
The reason that this principle holds is going to be explained later after a few examples of proof. Example 1: Let us prove the following equality using the second principle:
For any natural number n , 1 + 3 + ... + ( 2n + 1 ) = ( n + 1 )2.
Proof: Assume that 1 + 3 + ... + ( 2k + 1 ) = ( k + 1 )2 holds for all k, k<n.
Then 1 + 3 + ... + ( 2n + 1 ) = ( 1 + 3 + ... + ( 2n - 1 ) ) + ( 2n + 1 )
= n2 + ( 2n + 1 ) = ( n + 1 )2 by the induction hypothesis.
Hence by the second principle of induction 1 + 3 + ... + ( 2n + 1 ) = ( n + 1 )2 holds for all natural numbers.
Example 2: Prove that for all positive integer n, ${\sum}_{i=1}^{n}$ i ( i! ) = ( n + 1 )! - 1
Proof: Assume that
1 * 1! + 2 * 2! + ... + k * k! = ( k + 1 )! - 1 for all k, k<n.
Then 1 * 1! + 2 * 2! + ... + ( n - 1 ) * ( n - 1 )! + n * n!
= n! - 1 + n * n! by the induction hypothesis.
= ( n + 1 )n! - 1
Hence by the second principle of induction ${\sum}_{i=1}^{n}$ i ( i! ) = ( n + 1 )! - 1 holds for all positive integers.
Example 3: Prove that any positive integer n, n>1, can be written as the product of prime numbers.
Notification Switch
Would you like to follow the 'Discrete structures' conversation and receive update notifications?