Table of Contents

Proof by Induction

Process

  1. State your P(n).
    1. State your P(n), which should be a property as a function of n
    2. Also state for which n you will prove your P(n) to be true
  2. State your base case.
    1. State for which n your base case is true
    2. Prove it!
  3. State your induction hypothesis
    1. State your induction hypothesis! Without it, the whole proof falls apart. Usually it is just restating your P(n) with no restriction on n
  4. Inductive Step.
    1. Now consider P (n + 1). This is where you try to prove a larger case of the problem than you assumed in your induction hypothesis. What are you trying to prove? Keep this in mind when you do this step. Remember, use your induction hypothesis somewhere, and clearly state where. If you haven’t used your induction hypothesis in this step, then you are not doing a proof by induction. So you’d better need to use it.
  5. Conclusion
    1. Optionally, you can restate the problem.

Resources