<< Chapter < Page | Chapter >> Page > |
Factoring (n + 1) out, we get
(n + 1)(n + 2) / 2,
which is equal to the RHS for n+1.
Thus LHS = RHS for n+1.
End of Proof.
Loops in an algorithm/program can be proven correct using mathematical induction. In general it involves something called "loop invariant" and it is very difficult to prove the correctness of a loop. Here we are going to give a few examples to convey the basic idea of correctness proof of loop algorithms.
First consider the following piece of code that computes the square of a natural number:
(We do not compute the square this way but this is just to illustrate the concept of loop invariant and its proof by induction.)
SQUARE Function: SQ(n)
S<- 0
i<- 0
while i<n
S<- S + n
i<- i + 1
return S
Let us first see how this code computes the square of a natural number. For example let us compute 3 2 using it.
First S<- 0 and i<- 0 give S = 0 and i = 0 initially.
Since i<3, the while loop is entered.
S<- 0 + 3
i<- 0 + 1
producing S = 3 and i = 1.
Since i<3, the while loop is entered the second time.
S<- 3 + 3
i<- 1 + 1
producing S = 6 and i = 2.
Since i<3, the while loop is entered the third time.
S<- 6 + 3
i<- 2 + 1
producing S = 9 and i = 3.
Since i = 3, the while loop is not entered any longer, S = 9 is returned and the algorithm is terminated.
In general to compute n2 by this algorithm, n is added n times.
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 0 and n is a natural number. Thus i eventually becomes equal to n.
Next, to prove that it computes n2, we show that after going through the loop k times, S = k*n and i = k hold. This statement is called a loop invariant and mathematical induction can be used to prove it.
Proof by induction.
Basis Step: k = 0. When k = 0, that is when the loop is not entered, S = 0 and i = 0. Hence S = k*n and i = k hold.
Induction Hypothesis: For an arbitrary value m of k, S = m * n and i = m hold after going through the loop m times.
Inductive Step: When the loop is entered (m + 1)-st time, S = m*n and i = m at the beginning of the loop. Inside the loop,
S<- m*n + n
i<- i + 1
producing S = (m + 1)*n and i = m + 1.
Thus S = k*n and i = k hold for any natural number k.
Now, when the algorithm stops, i = n. Hence the loop will have been entered n times.
Thus S = n*n = n2. Hence the algorithm is correct.
The next example is an algorithm to compute the factorial of a positive integer.
FACTORIAL Function: FAC(n)
i<- 1
F<- 1
while i<= n
F<- F * i
i<- i + 1
return F
Let us first see how this code computes the factorial of a positive integer. For example let us compute 3!.
First i<- 1 and F<- 1 give i = 1 and F = 1 initially.
Since i<3, the while loop is entered.
F<- 1 * 1
i<- 1 + 1
producing F = 1 and i = 2.
Since i<3, the while loop is entered the second time.
F<- 1 * 2
i<- 2 + 1
producing F = 2 and i = 3.
Since i = 3, the while loop is entered the third time.
Notification Switch
Would you like to follow the 'Discrete structures' conversation and receive update notifications?