Correctness for Recurrence - Induction

1. Setup Predicate Merge Sort: $P(n):l \in List[\N]$ be a list of length $n$, merge_sort(l) returns sorted $l$ Claim: $\forall n\in\N, P(n)$ Binary Search: Induction on the length of the search interval $b-a=n$
2. Proof base cases Merge Sort: Prove lists of length 0 and 1
3. Setup inductive hypothesis Merge Sort: Let $k\in\N,k\ge1,$ assume $\forall i \in \N, 0 \le i \le k, P(i)$ Want to show $P(k + 1)$
   1. Show that the parameters passed to recursive calls are in the inductive hypothesis Merge Sort: l[:(k + 1)//2] have length at least $k$