FindMax $((a_0,a_1,$dots,$a_{n-1}))$ :

largest $=a_0$

for $i=1,$dots,$n-1$:

$if$ largest $a_i$:

largest $=a_i$

return largest

Consider the loop invariant:

After $t$ iterations, largest is equal to the maximum of $(a_0,a_1,$dots,$a_t)$

Fill in the blanks of the proof that the loop invariant is correct:

The proof will be by using: $$ induction

Base Case: After $0$ iterations of the for loop $($before the loop begins:$)$

$$

Inductive Hypothesis: Assume that for some $k,$ with $k>0,$ that after $k-1$ iterations, largest is equal to the maximum of $$ Inductive Step: in the $k$ th iteration, there are $2$ cases:

Case $1$: largest $a_k$ By the induction hypothesis largest is the maximum of

$$ and since $,a_k$ largest, $a_k$ is the max of $(a_0,$dots,$a_k).$ largest $=a_k,$

Case $2$: largest $>a_k$ By the induction hypothesis largest is the maximum of

$$ and since $a_k$ largest, largest is the max of $(a_0,$dots,$a_k)$