Table of Contents | Proof Methods | Glossary
A Proof by Strong Induction only differs from a proof by normal induction in the Inductive Hypothesis and Step..
(3) Formulate the Inductive Hypothesis and state that you are assuming the hypothesis to be true for all i < k or, alternatively, i <= k, depending on how you plan to formulate the inductive step.(4) Prove your Inductive Step. You're still proving that the Inductive Hypothesis is true for the next case, either k or k+1, respectively (depending on how you stated your Inductive Hypothesis) but your approach can now take advantage of the stronger assumptions stated in your Inductive Hypothesis.
Why is this called Strong Induction? You might need one or every previous case to prove the kth case. This is like saying that each domino is bigger than the previous one, so the combined weight of all the previous dominoes is needed to push over the next one.
An example of a proof by Strong Induction can be found in the proof of correctness for Quicksort.