Proof by induction

• The three common types of proof by induction involve:

  • (M)Matrices
  • (D)Divisibility
  • (E)Exponentials
• To prove something using induction, you must:

  1. Prove a basis case
  2. Assume that the proposition is true for some k
  3. Prove that the proposition is true for k+1
  4. Conclude the proof
• A basis case is a small numerical result, usually 1, but always the lowest possible positive (if applicable) value allowed by the propsition
• In the inductive hypothesis, you assume that the proposition is true for some value “k” and then substitute k into the proposition
• In the inductive step, you substitute k+1 into one side of the equation and use the inductive hypothesis to prove that the proposition is true for k+1
• The conclusion is always in the following format:

  ”P([basis case]) is true. If P(k) is true then P(k+1) is true. This means that P(n) is true for all [conditions of the proposition].”