Consider the following algorithm that returns the maximum of a list of distinct positive integers

$(a_0,....,a_{n-1})$

FindMax$($a$0,$a$1,...$an$-1))$:

largest $=$ a$0$

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

if largest ai :

largest $=$ ai

return largest

Consider the loop invariant:

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

Fill in the blanks of the proof t $\_\_\_\_\_\_\_($regular$/$strong$)$induction

Base Case: After $0$ iterations of the for loop $($before the loop begins:$)\_\_\_\_\_\_\_\_\_\_\_($largest is smaller than a$\_0,$ largest is maximum of the empty list, largest is maximum of the list $[$a$\_0,$a$\_1,$ largest is maximum of the list $[$a$\_0])$

Inductive Hypothesis: Assume that for some $k,$ with $k>0,$ that after $k-1$ iterations, largest is equal to the maximum of $\_\_\_\_\_\_\_\_\_[($a$\_1,...$a$\_$k$),($a$\_1,...,$a$\_($k$-1)),($a$\_0,...$a$\_$k$),($a$\_0,...$a$\_($k$-1))]$

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 $\_\_\_\_\_\_\_\_[($a$\_1,...$a$\_$k$),($a$\_1,...,$a$\_($k$-1)),($a$\_0,...$a$\_$k$),($a$\_0,...$a$\_($k$-1))]$

and since $,a_k$ largest, $a_k$

Case $2$: largest $>a_k$ By the induction hypothesis largest is the maximum of $\_\_\_\_\_\_\_[($a$\_1,...$a$\_$k$),($a$\_1,...$a$\_($k$-1)),($a$\_0,...$a$\_$k$),($a$\_0,...$a$\_($k$-1))]$

and since $,a_k$ largest, is the max of $($a$0,...$ak$)$