induction

Induction is a method of proof via the principle of mathematical induction.

to show the induction hypothesis $P(n)$ is true for every natural number $n$:

• show the base case "$n=0$ or $n=1$ is true"
• show the induction step "if $n=k$ is true, then $n=k+1$ is true."