Proof by Induction

State your P(n), which should be a property as a function of n

Also state for which n you will prove your P(n) to be true

State for which n your base case is true

Prove it!

State your induction hypothesis! Without it, the whole proof falls apart. Usually it is just restating your P(n) with no restriction on n

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.

Optionally, you can restate the problem.