My objective is to give a recursive algorithm for finding the maximum of a finite set of integers, "making use of the fact that the maximum of n integers is the larger of the last integer in the list and the maximum of the first n-1 integers in the list".
procedure maximum(L, i, j)
if (i != j) return maximum(L, i+1, j)
else if (i = j) return L[j]
else return 0
end if
This is what I came up with, and now I'm supposed to prove it correct using induction.
As a basis step, I claimed that a list L containing the integer 1 with leftbound interval i = 1 and rightbound interval j = 1 would lead us to the second if statement and successfully returns 1.
In the inductive step I said that the inductive hypothesis is the statement that maximum(L, i, j) returns k whenever k is the maximum element in the list.
So I decided that I must show that maximum(L, i, j) returns L[j] = k+1 when $k+1$ is the maximum element in the list, or in other words, the element located at the ``furthest right'' since the list is sorted.
Because k+1 is not anywhere before the end of the list, the algorithm will continuously take the path of the first if-statement until i = j, when it will return L[j]. Since k+1 is the largest element in the sorted list and $j$ is the last index in the list, the algorithm returns the correct value.
Would this be a valid manner of proving a recursive algorithm as correct through the use of induction?