Question

Recursively computing the sum of the first n positive odd integers, cont. About (a) Use induction to prove that your algorithm to compute the sum of the first n positive odd integers returns the correct value for every positive integer input.

Answer 1

The recursive function would work like this: the n-th odd number is 2n-1. With each iteration, we return the sum of 2n-1 and the sum of the first n-1 odd numbers. The break case is when we have the sum of the first odd number, which is 1, and we return 1.

int recursiveOddSum(int n) {

if(2n-1==1) return 1;

return (2n-1) + recursiveOddSum(n-1);

}

To prove the correctness of this algorithm by induction, we start from the base case as usual:

`f(1)=1`

by definition of the break case, and 1 is indeed the sum of the first odd number (it is a degenerate sum of only one term).

Now we can assume that
`f(n-1)` returns indeed the sum of the first n-1 odd numbers, and we have to proof that
`f(n)` returns the sum of the first n odd numbers. By the recursive logic, we have

`f(n)=f(n-1)+2n-1`

and by induction,
`f(n-1)` is the sum of the first n-1 odd numbers, and 2n-1 is the n-th odd number. So,
`f(n)` is the sum of the first n odd numbers, as required:

`f(n)=\underbrace{\underbrace{f(n-1)}_{\text{sum of the first n-1 odds}}+\underbrace{2n-1}_{\text{n-th odd}}}_{\text{sum of the first n odds.}}`