Proof by Induction

By $\mathbb{N}$ we denote the set of all $\text{natural numbers}$ (i.e. $\mathbb{N}:=\{0,1,2,3,...\}$)

Let $P(n)$ be a statement about a natural number $n$

• This is called the $\text{induction hypothesis}$
  The aim is to prove that statement $P(n)$ is true for every $n\in \mathbb{N}$. One method to do this is by $\text{mathematical induction}$:

1. First, we prove that statement $P(n)$ is true for $n=0$.
   We call this step $\text{basis of the induction}$, or simply $\text{basis step}$
2. In the second step, we prove for every natural number $n\in \mathbb{N}$:
   If statement $P(n)$ is true, then the statement $P(n+1)$ is true as well.
   This step is called the $\text{inductive step}$

Altogether, this proves that statement $P(n)$ is true $\text{for all}$ $n\in \mathbb{N}$

Strong Induction

Equivalent to 'normal' induction, however you can assume that every number in the set less than $n$ ( $n_0\le i\le n$ ) is also true when proving $P(n+1)$