About

Mathematical induction is a proof technique which applies to inductive sets, especially the set of non-negative integers. An induction proof on a set $S$ is carried out in two steps: in the induction basis, the claim is shown to hold for the minimal element in $S$; in the induction step, it is proven that, if the claim holds for a single but arbitrary $k \in S$ (the induction hypothesis), then it holds for the next element in $S$ ($k+1$ in case $S = \mathbb{N}$).

Induction can be generalized to inductively defined structures such as trees and Boolean formulae. Proofs of this type are named structural induction proofs.