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 ∈ ℕ: ∃ n_{0} ∈ ℕ | P(n_{0}) true (basis of induction); P(n) true ⇒ P(n+1) true, ∀ n ≥ n_{0} (induction step); then P(n) true ∀ n ≥ n_{0}.

Considering the Newton's binomial formula, P(n): (a + b)^{n} = ^{n}Σ_{k=0} C(n,k) a^{n-k}b^{k}

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): 2^{n} ≥ n, ∀ n ∈ ℕ, n ≥ 1; Basis of induction: n = 1, 2^{1} ≥1 true; Inductive step: hypothesis 2^{n} ≥ n, thesis 2^{n+1} ≥ n+1; 2^{n+1} = 2⋅2^{n} ≥ 2n ≥ n+1

P(n): n^{2}+n even ∀ n ∈ ℕ, n ≥ 1; Basis of induction: n = 1, 1^{2}+1 = 2 even; Inductive step: hypothesis n^{2}+n even, thesis (n+1)^{2}+(n+1) even; (n+1)^{2}+(n+1) = n^{2}+2n+1+n+1 = n^{2}+n+2n+2 = n^{2}+n+2(n+1) even, n^{2}+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+nx^{2} = 1+(n+1)x+nx^{2} ≥ [2] 1+(n+1)x; [1] (1+x) > 0, (1+x)^{n}(1+x) ≥ (1+nx)(1+x); [2] 1+(n+1)x+nx^{2} ≥ 1+(n+1)x, if b ≥ 0 then a+b ≥ a