Mathematical induction is a special way of proving a mathematical truth. It can be used to prove that something is true for all the natural numbers (or all positive numbers from a point onwards). The idea is that if:

1. Something is true for the first case (base case);
2. Whenever that same thing is true for a case, it will be true for the next case (inductive case),

then

• That same thing is true for every case by induction.

In the careful language of mathematics, a proof by induction often proceeds as follows:

• State that the proof will be by induction over \displaystyle{ n }. (\displaystyle{ n } is the induction variable.)
• Show that the statement is true when \displaystyle{ n } is 1.
• Assume that the statement is true for any natural number \displaystyle{ n }. (This is called the induction step.)
  • Show then that the statement is true for the next number, \displaystyle{ n+1 }.

Because it is true for 1, then it is true for 1+1 (=2, by the induction step), then it is true for 2+1 (=3), then it is true for 3+1 (=4), and so on.