Proof by induction

What you'll learn

1. 1

   Imagine a row of dominoes 🎳. If you push the first one, it knocks over the second, which knocks over the third… and so on. That's proof by induction!

2. 2

   What are the two things we need to prove in induction?

3. 3

   Let's prove that 1 + 2 + 3 + … + n = n(n+1)/2 for all positive integers n.

4. 4

   Drag the dominoes to build the proof: show the base case and the inductive step for the formula 1 + 2 + … + n = n(n+1)/2.

5. 5

   For the inductive step, what do we add to both sides of the assumption?

6. 6

   Another example: Prove that 2^n > n for all positive integers n.

7. 7

   In the inductive step for 2^n > n, we multiply the assumption by what?