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
Best Answer
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!