Answer to Question #159660 in Discrete Mathematics for Master

Question

2. Following algorithm calculates the sum of first n nonnegative integers. Prove the algorithm to be

correct using mathematical induction.

procedure sum(n: nonnegative integer)

if n = 0 then return 0

else return n + sum(n - 1)

{output is 0 + 1 + 2 + 3 + …… + n}

a. (10p) Show that basis step returns correct result

b. (10p) Write down the inductive hypothesis

c. (10p) What do you need to prove in the inductive step?

d. (10p) Complete the inductive step, stating where you use the inductive hypothesis

e. (10p) Explain why these steps show that this algorithm returns correct result for any

nonnegative integer n.

Answer 1

a. In case we have only 0 the result will be 0.

b. The inductive hypothesis is: Assume that sum(n-1) returns the sum of n-1 integers.

c. For the inductive step we need the following: In case sum(n-1) is the sum of n-1 integers, sum(n) will be the sum of n integers.

d. We use the third line of procedure and receive that from the inductive hypothesis it follows that sum(n) is the sum of n integers.

e. The basis step (item a) returns 0. Items a-d justify that in order to find the sum of n integers we need to add n to the sum of n-1 integers.