.png)
The Induction Principle is of great importance in discrete mathematics: Number Theory, Graph Theory, Enumerative Combinatorics, Combinatorial Geometry, and other subjects.
Usually one proves the validity of a relationship f(n) = g(n) if one has a guess from small values of n.
Then one checks that f(1) = g(1), and, by making the assumption f(n) = g(n) for some n, one proves that also f(n + 1) = g(n + 1).
From this one concludes by the Induction Principle that f(n) = g(n) for all n ∈ N. There are many variations of this principle.
The relationship f(n) = g(n) is valid for 0 already, or, starting from some n0 > 1.
The inductive assumption is often f(k) = g(k) for all k < n, and, from this assumption, one proves the validity of f(n) = g(n).
We assume familiarity with all this and apply induction in unusual circumstances to make nontrivial proofs.
