Induction is a very powerful technique used regularly by mathematicians. Initially, it can be confusing because it looks like we assume what is to be proved. As we know, that never proves theorems. On the plus side, spotting when to use it is easy and we need only check two conditions to apply it.

Induction is applied when we have an infinite number of statements indexed by the natural numbers such as

It is not sufficient to prove this for a sample of natural numbers, whether that sample involves hundreds, millions or even billions of numbers; we have to prove it for all n.

With induction we don't prove the statements directly. What we do is perhaps best described by analogy with domino toppling. As you are probably aware, this is where dominoes are standing on their ends in such a way that when you push the first one over, it knocks the second domino over, that in turn knocks the third down, and so on. Provided the dominoes are arranged so that each knocks down the next, then all of them will fall.

The process of induction is that we prove that ‘if the kth statement is true, then the k + 1th statement is true’, i.e. the truth of one statement implies the truth of the next one. This is analogous to one domino knocking down the next one.