Proving insertion sort using induction A while back when I was taking a first year cs course, our professor had us write the algorithm for insertion sort in The Scheme programming language. There were also several other similar recursion type programs for us to write, and one of the question in the assignment was to prove that the programs are correct using Mathematical Induction. At first I tried to justify my program using "Weak Induction", however my professor insisted on me using "Strong Induction" and I lost marks for not using it. I was not confident at the time to engage in an argument or ask for reasons why Strong over Weak and this has been bugging me ever since. 
So, the question is this: Using weak induction in the ordinary sense such as, proving n = 0 for base case and proving the inductive step of the algorithm, was there anything wrong other than pedagogy? If so, could you enlighten me by explaining why there was a need to use strong induction to prove recursion type algorithms such as insertion sort?
Thanks in advance
 A: This is certainly an issue of pedagogy.  With Strong Induction, one doesn't have to mention a base case explicitly.  However, one has to be able to consider an empty set of inductive hypotheses.
See:  http://en.wikipedia.org/wiki/Strong_induction#Complete_induction
It would seem that a proof that uses Strong Induction as a tool is actually a weaker proof!
A: The adjectives "weak" and "strong" are misleading, because both forms of induction have the same expressive power. Choosing one other the other depends on the statement S to be proved. If, for proving P(n), only P(n-1) is necessary (don't forget the base case, of course), then this is weak induction. If you need P(m) for some m < n-1, then this is strong induction. I prefer to call the former "mathematical induction" and the latter "complete induction".
So, in some sense, it is a matter of pedagogy, but, if you claimed to use weak induction, and used an hypothesis P(m) with m < n-1, then you made an error: just say that you use strong induction.
