Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
What was the program? It would be hard to say without seeing how the recursion was... –  Aryabhata Mar 2 '11 at 22:34

2 Answers 2

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!

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.