You are currently browsing the category archive for the ‘Mathematics’ category.

The principle of mathematical induction is a simple but powerful technique for proving mathematical results. In its most basic form, it says the following:

If something’s true for an integer $n_0$, and if it being true for the number $k$ implies it is true for the number $k+1$, then it is true for all integers $n \ge n_0$.

This is a more-or-less “obvious” statement. It has two components: the base case and the inductive step. The base case establishes truth for one number. The inductive step does not actually establish truth of the statement for any particular value. Instead, it establishes the truth of a logical implication. In formal terms, the above box reads:

If $P(n)$ is a proposition for the integer $n$, then if $P(n_0)$ is true and $P(k) \Rightarrow P(k+1)$, then $P(n)$ is true for all integers $n \ge n_0$.

Think of induction as a string of dominos. Establishing the base case is like knocking down the first domino. Establishing the inductive step is like setting up the dominos so that if the $k$-th domino falls, it knocks over the $(k+1)$-th domino. Thinking of it this way, it should be obvious that once these two things are established, then all the dominos will fall. This is one of the concepts that is best learned through examples.