The function sum below computes the sum of the elements on its given list by adding the first element to the sum of the remaining elements; the latter sum is computed by a recursive call on the remainder of the list. Prove that sum correctly computes the sum of the list elements. What statement S(i) do you prove inductively? What is the basis value for i?

int sum (LIST L) if (L== NULL) return 0; else return(L->element + sum (L->next))