Archangel Macsika
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.
The Answer to the Question
is below this banner.
Can't find a solution anywhere?
NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?
Get the Answers Now!You will get a detailed answer to your question or assignment in the shortest time possible.
Here's the Solution to this Question
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.