Consider the following algorithm. Assume the input array contains numbers.

1
2
3
4
5
6

function SUMMATION(array[1..n])
    sum = array[1]
    for k = 2 to n do
        # The invariant is here.
        sum = sum + array[k]
    return sum

For any value of k between 2 and n, sum is equal to the sum of elements of array[1..k-1].

You will need to show:

• The initialisation step
• The maintenance step

You do not need the termination step.