2.9.2: The function sum in Fig. 2.32 computes the sum of the elements on its given list (whose cells are of the usual type as defined by the macro DefCell of Section 1.6 and used in the merge-sort program of Section 2.8) 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?

DefCell(int, CELL, LIST); int sum(LIST L) if (LNULL) return 0 else return(L->element + sum (L->next)); int findo (LIST L) if (LNULL) return FALSE; else if (L->element- 0) return TRUE ; else return findo (L->next) Fig. 2.32. Two recursive functions,u and findo