This website uses advertising and analytics technologies.

MATHEMATICAL INDUCTION


Mathematical induction is a mathematical proof technique; it is essentially used to prove that a statement P(n) holds for every natural number n = 0, 1, 2, 3, ...

A proof by induction consists of two cases: the first, the base case (or basis), proves the statement for 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 n=k, then it must also hold for the next case n=k+1; these two steps establish that the statement holds for every natural number n.

The simplest and most common form of mathematical induction infers that a statement involving a natural number n (that is, an integer n ≥ 0 or 1) holds for all values of n.

The proof consists of two steps: The initial or base case proves that the statement holds for 0, or 1; The induction step, inductive step, or step case proves that for every n, if the statement holds for n, then it holds for n + 1; in other words, assume that the statement holds for some arbitrary natural number n, and prove that the statement holds for n+1.

The hypothesis in the inductive step, that the statement holds for a particular n, is called the induction hypothesis or inductive hypothesis; to prove the inductive step, one assumes the induction hypothesis for n and then uses this assumption to prove that the statement holds for n+1.

P(n) is a property that depends on an index n ∈ ℕ: ∃ n0 ∈ ℕ | P(n0) true (basis of induction); P(n) true ⇒ P(n+1) true, ∀ n ≥ n0 (induction step); then P(n) true ∀ n ≥ n0.

Considering the Newton's binomial formula, P(n): (a + b)n = nΣk=0 C(n,k) an-kbk

P(n): nΣk=1 k = n(n+1)/2 ∀ n ≥ 1; n = 10, 10Σk=1 k = 10·11/2; n = 100, 100Σk=1 k = 100·101/2; Basis of induction: n = 1, 1Σk=1 k = 1·2/2, 1 = 1 true; Inductive step: hypothesis nΣk=1> k = n(n+1)/2, thesis n+1Σk=1 k = (n+1)((n+1)+1)/2 = (n+1)(n+2)/2; n+1Σk=1 k = nΣk=1 k + n+1Σk=n+1 k = n(n+1)/2 + (n+1) = (n(n+1) + 2(n+1))/2 = (n+1)(n+2)/2

P(n): 2n ≥ n, ∀ n ∈ ℕ, n ≥ 1; Basis of induction: n = 1, 21 ≥1 true; Inductive step: hypothesis 2n ≥ n, thesis 2n+1 ≥ n+1; 2n+1 = 2⋅2n ≥ 2n ≥ n+1

P(n): n2+n even ∀ n ∈ ℕ, n ≥ 1; Basis of induction: n = 1, 12+1 = 2 even; Inductive step: hypothesis n2+n even, thesis (n+1)2+(n+1) even; (n+1)2+(n+1) = n2+2n+1+n+1 = n2+n+2n+2 = n2+n+2(n+1) even, n2+n even for hypothesis and 2(n+1) even, and the sum of two even numbers is an even number ⇒ (n+1)2+(n+1) even

Bernoulli's inequality, (1+x)n ≥ 1+nx, ∀ x ∈ ℝ, x > -1, ∀ n ∈ ℕ; Basis of induction: n=0, (1+x)0 ≥ 1+0x, 1 ≥ 1 true; Inductive step: hypothesis (1+x)n ≥ 1+nx, thesis (1+x)n+1 ≥ 1+(n+1)x; (1+x)n+1 = (1+x)n(1+x) ≥ [1] (1+nx)(1+x) = (1+nx)+x(1+nx) = 1+nx+x+nx2 = 1+(n+1)x+nx2 ≥ [2] 1+(n+1)x; [1] (1+x) > 0, (1+x)n(1+x) ≥ (1+nx)(1+x); [2] 1+(n+1)x+nx2 ≥ 1+(n+1)x, if b ≥ 0 then a+b ≥ a