# Proving correctness of a recursive algorithm using induction

For the program

mean(A,n)

if n = 1 then

return A[n]

else

return A[n]/n+mean(A,n-1)*(n-1)/n

end


Show that if the recursive call to mean (A, n-1) returns the mean of A[1,...n-1] then the call mean (A,n) returns the mean of A[1,...n].

I know that the program always terminates with mean (A,1) as per the basis step where with inductive hypothesis we are proving n >=1 and we are in the else case, but I'm not sure how to show the last part using the n-1 inductive step.

• Well, show us as much of the proof by induction as you can. What is the predicate you are trying to prove by induction? The inductive hypothesis? Can you write out the base case? Can you write out as much of the inductive step as possible? – D.W. Jul 9 '15 at 17:37

Your inductive hypothesis is ´mean(A, n-1) is the mean of $A[1:n-1]$, i.e. the first $n-1$ elements of $A$.

Formally this can be written as ´mean(A,n-1)$= \frac{\sum_{i=1}^{n-1}{A[i]}}{n-1}$

Then we conpute mean(A,n) with that hypothesis.

When $n=1$, the result is $A[n]$, i.e., $A$ which is the mean of $A[1:1]$.

Otherwise the result is A[n]/n+mean(A,n-1)*(n-1)/n,
i.e. $A[n]/n + \frac{\sum_{i=1}^{n-1}{A[i]}}{n-1}\times \frac{n-1}n$ becaus of the induction hypothsis.

You only have to simplify this expression to reach the desired result.

The conclusion of all this is that the proof is very simple, but you have to write formally your hypothesis and computation. The best way to answer a question is to first express it clearly and completely.