Induction

From Math Images

Induction is a very useful method of proof used in mathematics. Induction is used when we have discrete, ordered cases. Imagine a simple, standing row of dominoes--we are not talking about those amazing set ups that people make for competitions. These dominoes have some necessary order to them; one clearly comes after another. If we knock down one domino, all the ones after it will fall, too. Our cases are like the dominos: they are ordered, and if we prove (ie knock down) one case, we prove all of the cases that come after it. This is particularly useful because it proves statements for a (countably) infinite set of ordered cases.

Without some way to get around proving every single case, we would literally have to sit proving something forever! This is why induction is an incredibly powerful mathematical tool. We do not have to sit and watch all of the dominos fall forever--we can simply trust that every single domino will fall eventually.

When we use induction, we show a simple base case to be true, and then we show that if the kth case is true, then the (k+1)th case must also be true. Therefore, we manually knock down our first domino, and then show that each domino will knock down the one after it. By invoking the Principle of Mathematical Induction, we then prove our claim for all cases.

(Text is from a discrete math homework assignment of Anna.