Proof by induction

A proof by induction is a technique of mathematical proof. It is one of the axioms of Zermelo-Fraenkel set theory, allowing a mathematician to have proofs that proceed in order through all the natural numbers. Proofs by induction are divided into three categories: weak (or classic) induction, strong induction, and transfinite induction. As the names suggest, weak induction proofs require fewer assumptions than strong induction proofs. Sometimes these assumptions are too weak, in which case strong induction is necessary. Transfinite induction involves infinitary mathematics, including the Axiom of Choice. Many mathematicians avoid transfinite induction when possible.

Weak Induction

Hypothesis A is true for 0. Then assume hypothesis A is true for the number n. Prove that it must be true for n+1.

Strong Induction

Hypothesis A is true for 0. Then assume hypothesis A is true for all the numbers less than n. Prove that it must be true for n.

Technique of Induction

Both Weak and Strong Induction are based on the Peano Axioms, especially the Induction Axiom:

If a set S of numbers contains zero and the successor of every number in S, then S contains every number.

If you want to show that an hypothesis A is true for all Natural Numbers, you look at the set S of all numbers for which the hypothesis is true: you show, that

1. zero is an element of the set S
   Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \in S}
2. with any number n, S contains the successor of n
   Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \in S \Rightarrow (n+1) \in S }

By the Induction Axiom, S then includes all Natural Numbers, i.e., the hypothesis A hold for all Natural Numbers. A standard example for this kind of reasoning is the following:
Hypothesis A: For any Natural Number n, the sum of the numbers less or equal to n is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{n(n+1)}{2}}

1. Show: A holds for zero, i.e., zero is in S: That's easy: The sum of all natural numbers less or equal to zero is zero, and this equals Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{0(0+1)}{2}}
2. Show: If A holds for n, then A holds for n+1: So, we assume that A is true for n:
   (*) Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 + 2 + 3 + ... + n = \frac{n(n+1)}{2}}
   We have to show, that then A is true for n+1:
   Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 + 2 + 3 + ... + n + (n+1)= \frac{(n+1)((n+1)+1}{2}}
   How to do this? For example, the following way, starting with (*):
   Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 + 2 + 3 + ... + n = \frac{n(n+1)}{2}\quad |} adding (n+1) on both sides
   Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Leftrightarrow}
   Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 + 2 + 3 + ... + n + (n+1)= \frac{n(n+1)}{2} + (n+1)\quad|} simplify the right side
   Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Leftrightarrow}
   Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 + 2 + 3 + ... + n + (n+1)=\frac{n(n+1)}{2} + \frac{2(n+1)}{2}=\frac{n(n+1)+2(n+1)}{2}=\frac{(n+1)(n+2)}{2}}

Now, we're finished: the hypothesis A holds for all the Natural Numbers.

Transfinite Induction

Assume hypothesis A is true for a finite number n or an infinite cardinal k. Prove it must be true for n+1 (respectively, k+1).

See also

• Proof by contradiction
• Proof by contraposition