0.5 Discrete structures recursion  (Page 6/8)

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.

Example of use of mathematical induction --- program correctness

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.