title: How do I prove merge works using mathematical induction?
body: <p>Here is the link to my <a href="https://www.dropbox.com/s/n5bhm08uxyoxqvs/a1.pdf?dl=0" rel="nofollow">homework</a>.</p>
  
  <p>I just want help with the first problem for merge and will do the second part myself. I understand the first part of induction is proving the algorithm is correct for the smallest case(s), which is if X is empty and the other being if Y is empty, but I don't fully understand how to prove the second step of induction: showing merge is correct with input sizes k + 1.</p>
  
  <p>I've done induction before on equations, never on an algorithm.</p>
  
  <p>Thanks! </p>