title: Using induction to prove bubble sort is correct
body: <p>How can we show, using induction, that bubble sort is correct?  How do we choose the invariant to follow throughout the formulation of the proof (this step seems like an arbitrary task to me, so if it can be explained more deeply I would greatly appreciate it)?</p>
  
  <p>I understand that the largest elements will always end up at the end of the list after each iteration, but I don't know how to use this fact to show that the algorithm is correct.</p>
  
  <p>Thanks for the help!</p>