Mathematical Induction

Discrete Math · Axiom Academy

A powerful proof technique that works like falling dominoes: prove the first falls, then prove each domino knocks down the next, and you've proven they all fall. Imagine an infinite line of dominoes, numbered 1, 2, 3, 4, and so on. To prove that all dominoes will fall, you only need to show two things: Mathematical induction has two essential steps that mirror the domino analogy: Inductive Step: Assume P(k) is true for some arbitrary k ≥ 1 (this assumption is called the inductive hypothesis ), then prove P(k+1) is true 3. Example: Sum of First n Natural Numbers Let's prove that for all n ≥ 1: 4. Example: Divisibility Proof Let's prove that for all n ≥ 1, the expression 4ⁿ - 1 is divisible by 3.

This is the written version of the interactive lesson above. See the full Discrete Math course.