Domino Effect

• Imagine many pieces of dominos are standing up on a table. You want to make sure everyone of the pieces fall with the first one's falling. Firstly, does the falling of the first one sufficiently guarantee the collapse of all pieces?
• Well, not quite. How do we know all the other pieces are aligned properly? However, if you are told that the first piece falls AND for any arbitrary piece falling, the very next piece falls, then you are certain that all the pieces will fall.
• This seems obvious, but this is the very basis of mathematical induction.

Induction

• Mathematical Induction is a powerful method for proofs in all areas of mathematics. Imagine we want to prove this simple fact:

1 + 2 + 3 + ... + n = n (n +1) / 2

• The first simple step is to prove this for the case of n = 1. Obviously 1 = 1 (1 + 1) / 2.

• The next step is to assume the fact is true for n = k, k being any arbitrary integer. So, we assume 1 + 2 + 3 + ... + k = k (k + 1) / 2. It is very important to note that this is an assumption, not a fact yet.

• The last and most important step, called the inductive step, is to prove the expression for n = k + 1 using the assumption.

1 + 2 + 3 + ... + k + k + 1 = k (k + 1) / 2 + k + 1 = (k + 1) (k + 2) / 2.

• Looking carefully at the result, we can see it is exactly n ( n + 1) / 2 for n = k + 1. Therefore, we have proved the expression is true for n = 1, and assuming it is true for n = k, it is true for n = k + 1.

• Very much like the domino effect, this proves the expression is true for all n.

• Prove the following by induction: (Hint: Prove for n = k + 2 this time.)

1 + 3 + 5 + ... + (2n - 1) = n²