Principle of mathematical induction

The principle of mathematical induction states: if $P(n)$ is a statement depending on $n\in\mathbb{N}$ and

• $P(1)$ is true (base case), and
• for every $n\in\mathbb{N}$, $P(n)\Rightarrow P(n+1)$ (inductive step), then $P(n)$ is true for all $n\in\mathbb{N}$.

Induction underlies virtually every rigorous argument about integers, sequences, and series, and is used to prove inequalities, formulas for sums, and structural properties of $\mathbb{N}$.