Use induction to prove that L = M by showing that LCM and M C L on the length of w. Let L be the language of strings w over (0,1) such that every non-empty even-length prefix of w ends with a 1. Let M be the language defined by the following recursive definition: Base case: & M; 0 M; 1 M General case: For any w = M, 01w, 11w are in M. Clearly state the: > Basis > Induction hypothesis > Statement to show in the inductive step > Proof of the inductive step