Proof by Induction Algorithm

Question

I am stuck on trying to prove this algorithm using mathematical induction.

add_list(s,n) {
//add a list s of numbers with length n
    sum = 0
    for i = 1 to n
        sum = sum + si
    return sum

I know I need to start with a base case, and I'm guessing that it would look something like this:

for n = 0, sum = 0 + 0.

I am not sure then how to proceed with setting up the inductive hypothesis and the rest of the proof though. help pls...

Answer 1

So the problem is, I think, to prove that the outlined algorithm computes $s(n) = \sum_{i=1}^n s_i$, for a 'list' $(s_1,\ldots,s_n)$.

Yes, your base case appears correct: if $n=0$, then the list is empty, so $\sum_{i=1}^n s_i=0$ (a bit by convention) and this algorithm, too, returns $0$.

Otherwise, let $n>0$. Assume that the algorithm correctly computes $s({m})$ for all lists of length $m=n-1$. Rewrite your above loop as

for i=1 to n-1 sum = sum + s[i] sum = sum + s[n]

You see that the first part is add_list(t,n-1) where $t$ is the list $(s_1,\ldots,s_{n-1})$, which, by assumption, correctly returns $s({n-1})$. Then your algorithm outputs $s({n-1})+s_n$, which, obviously, equals $s(n)$.