88. Mathematical Induction

Mathematical induction is a mathematical proof technique. It is used to prove that a statement \(P(n)\) holds for every natural number \(n = 0, 1, 2, 3, \ldots ;\) that is, the overall statement is a sequence of infinitely many cases \(P(0), P(1), P(2), P(3), \ldots\)

The earliest rigorous use of induction was by Gersonides (1288–1344). The first explicit formulation of the principle of induction was given by Pascal in his Traité du triangle arithmétique (1665).

In boolean algebra, a statement which is either true or false is called a proposition. \(P(n)\) will denote a proposition whose truth value depends on natural numbers.

For example, we recall the sum of first \(n\) natural numbers from arithmetic progression as \(1 + 2 + \ldots + n = \frac{n(n + 1)}{2}\) is denoted by \(P(n),\) then we can write

\(P(n) = 1 + 2 + \ldots + n = \frac{n(n + 1)}{2}\)

Here \(P(2)\) is true means that sum of first two natural numbers is equal to \(1 + 2 = \frac{2*3}{2} = 3\)

Mathematical induction is used to prove propositions in many branches of algebra, geometry and analysis.

88.1. Principle of Finite Mathematical Induction

The proposition \(P(n)\) is assumed to be true for all natural numbers if the following two conditions are satisfied:

  1. The proposition \(P(n)\) is true for \(n = 1\) i.e. \(P(1)\) is true

  2. \(P(m)\) is true \(\Rightarrow P(m + 1)\) is true where \(m\) is an arbitrary natural number

88.2. Extended Form of Mathematical Induction

  1. If \(P(n)\) is a proposition such that

    1. \(P(1), P(2), \ldots, P(k)\) are true

    2. \(P(m), P(m + 1), \ldots, P(m + k - 1)\) are true implies \(P(m + k)\) is true

  1. If \(P(n)\) is a proposition such that

    1. \(P(r)\) is true

    2. \(P(r), P(r + 1), \ldots, P(m)\) are true imlpies \(P(m + 1)\) is true.