Question

Prove that the recursive algorithm for finding the sum of the first n positive integers you found in Exercise 8 is correct.

Short answer

The recursive algorithm is correct

Step-by-step solution

Consider the recursive algorithm

The recursive algorithm is,

procedure sum (n : positive integer )

if n = 1 then

return 1

else

return sum (n - 1) + n

Prove that the recursive algorithm for finding the sum of the first n positive integers

This can be proved by Induction.

The algorithm return 1, which is also the sum of the first positive integer and thus the algorithm, is correct for the basis step.

Assume that the algorithm is correct for the positive integer k with k > 1.

$\mathrm{sum}\left(k\right)=\sum _{i=1}^k i$

It is needed to prove that the algorithm is also correct for k + 1

$\begin{array}{r}\mathrm{sum}(k+1)=\mathrm{sum}\left(k\right)+(k+1)\\ =\sum _{i=1}^k i+(k+1)\\ =\sum _{i=1}^{k+1} i\end{array}$

Note that the algorithm gives the sum of the first k + 1 element for the integer k + 1, and thus the algorithm is correct for the integer k + 1.

Therefore, the by the principle of mathematical induction, the recursive algorithm is correct.