Proof by induction

A proof by induction consists of two cases. The first, the base case, proves the statement for ${\displaystyle n=0}$ without assuming any knowledge of other cases. The second case, the induction step, proves that if the statement holds for any given case ${\displaystyle n=k}$, then it must also hold for the next case ${\displaystyle n=k+1}$. These two steps establish that the statement holds for every natural number ${\displaystyle n}$. The base case does not necessarily begin with ${\displaystyle n=0}$, but often with ${\displaystyle n=1}$, and possibly with any fixed natural number ${\displaystyle n=N}$, establishing the truth of the statement for all natural numbers ${\displaystyle n\geq N}$.