Mathematical Induction Proof

Mathematical induction is a technique for proving a statement – a theorem, or a formula — that is asserted about every natural number. It is a mathematical proof technique used to prove a given statement about any well-ordered set. Most commonly, it is used to establish statements for the set of all natural numbers.

1 + 2 + 3 + 4 + ..… + n = {n(n + 1)}/2.

For all positive integers n.

We denote this mathematical statement by P(n). If n = 1, then we find that {1(1 + 1)}/2= 1.

Hence the above statement is true for n = 1.

Suppose n = 2. Then 1 + 2 = 3 and {2(2 + 1)}/2= 3. So we find that the statement is true for n = 2.

Thus, it is easy to verify that P(n) is true for n = 1, 2, 3 or 4. But it is impossible to verify that the above statement is true for all positive integers.

To prove that the above statement P(n) is true for all positive integers we generally follow a method of proof which is known as proof by the Principle of Mathematical Induction or simply proof by mathematical induction. For this we assume the following important property of integers.

Mathematical Induction – Problems with Solutions (induction proof):

1. Using the principle of mathematical induction, prove that n(n + 1)(n + 5) is a multiple of 3 for all n ∈ N.

Solution:

Let P(n): n(n + 1)(n + 5) is a multiple of 3.

For n = 1, the given expression becomes (1 × 2 × 6) = 12, which is a multiple of 3.

So, the given statement is true for n = 1, i.e. P(1) is true.

Let P(k) be true. Then,

P(k): k(k + 1)(k + 5) is a multiple of 3

⇒ K(k + 1)(k + 5) = 3m for some natural number m, … (i)

Now, (k + 1l)(k + 2)(k + 6) = (k + 1)(k + 2)k + 6(k + 1)(k + 2)

= k(k + 1)(k + 2) + 6(k + 1)(k + 2)

= k(k + 1)(k + 5 – 3) + 6(k + 1)(k + 2)

= k(k + 1)(k + 5) – 3k(k + 1) + 6(k + 1)(k + 2)

= k(k + 1)(k + 5) + 3(k + 1)(k +4) [on simplification]

= 3m + 3(k + 1 )(k + 4) [using (i)]

= 3[m + (k + 1)(k + 4)], which is a multiple of 3

⇒ P(k + 1): (k + 1 )(k + 2)(k + 6) is a multiple of 3

⇒ P(k + 1) is true, whenever P(k) is true.

Thus, P(1) is true and P(k + 1) is true, whenever P(k) is true.

Hence, by the principle of mathematical induction, P(n) is true for all n ∈ N.

2. Induction Proof- Using the principle of mathematical induction, prove that (n² + n) is even for all n ∈ N.

Solution:

Let P(n): (n² + n) is even.

For n = 1, the given expression becomes (1² + 1) = 2, which is even.

So, the given statement is true for n = 1, i.e., P(1)is true.

Let P(k) be true. Then,

P(k): (k² + k) is even

⇒ (k² + k) = 2m for some natural number m. … (i)

Now, (k + 1)² + (k + 1) = k² + 3k + 2

= (k² + k) + 2(k + 1)

= 2m + 2(k + 1) [using (i)]

= 2[m + (k + 1)], which is clearly even.

Therefore, P(k + 1): (k + 1)² + (k + 1) is even

⇒ P(k + 1) is true, whenever P(k) is true.

Thus, P(1) is true and P(k + 1) is true, whenever P(k) is true.

Hence, by the principle of mathematical induction, P(n)is true for all n ∈ N.

3. Induction Proof- Using the principle of mathematical induction, prove that

(1 + x)n ≥ (1 + nx)for all n ∈ N, where x > – 1.

Solution:

Let P(n): (1 + x) )n ≥ (1 + nx).

For n = 1, we have LHS = (1 + x)¹ = (1 + x),and

RHS = (1 + 1 ∙ x) = (1 + x).

Therefore LHS ≥ RHS is true.

Thus, P(1) is true.

Let P(k) is true. Then,

P(k): (1 + X)k ≥ (1 + kx). …….. (i)

Now,(1 + x)k + 1 = (1 + x)k (1 + x) ≥ (1 + kx)(1 + x) [using (i)]

=1 + (k + 1)x + kx² ≥ 1 + (k + 1)x + x [Since kx² ≥ 0]

Therefore P(k + 1): (1 + x)k + 1 ≥ 1 + (k + 1)x

⇒ P(k +1) is true, whenever P(k) is true.

Thus, P(1) is true and P(k + 1) is true, whenever P(k) is true. Hence, by the principle of mathematical induction, P(n) is true for all n ∈ N.

Information Source:

• www.math-only-math.com