Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true for all natural numbers (non-negative integers). It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite sequence of statements is true, then so is the next one.

The simplest and most common form of mathematical induction proves that a statement involving a natural number

- The basis (base case): showing that the statement holds when
$n$ is equal to the lowest value that$n$ is given in the question. Usually,$n=0$ or$n=1$ . - The inductive step: showing that if the statement holds for some
$n$ , then the statement also holds when$n+1$ is substituted for$n$ .

The assumption in the inductive step that the statement holds for some

The choice between

This method works by first proving the statement is true for a starting value, and then proving that the process used to go from one value to the next is valid. If these are both proven, then any value can be obtained by performing the process repeatedly.

# Visualization

It may be helpful to think of the domino effect. If one is presented with a long row of dominoes standing on end, one can be sure that:

- The first domino will fall
- Whenever a domino falls, its next neighbor will also fall

So it is concluded that all of the dominoes will fall, and that this fact is inevitable.

## Dominoes

Mathematical induction can be informally illustrated by reference to the sequential effect of falling dominoes.

## Example

Prove the following statement: For each positive integer

Base Case: We first have to check that the statement holds for

Inductive Step: Assume that the statement holds for

Note that we can use the induction hypothesis that the statement holds for

We can now rewrite this statement and show that it equals the right-hand side of the previous statement. In other words, if we can show that the following holds true, we will show that

We can rewrite

This is exactly we wanted to prove. We have shown that