Applications of Induction

Applications of Induction

Mathematical induction is a powerful proof technique used to establish the truth of an infinite number of statements. It is particularly useful for proving statements about integers, sequences, and series. In this section, we will explore various applications of induction, including proving formulas, inequalities, and properties of sequences.

Understanding the Principle of Mathematical Induction

Before diving into applications, let us briefly review the principle of mathematical induction. To prove a statement P(n) for all integers n ≥ k (where k is some integer), you typically follow these two steps:

1. Base Case: Prove that P(k) is true.
2. Inductive Step: Assume that P(n) is true for some integer n ≥ k, and then prove that P(n + 1) is also true.

Application 1: Proving a Formula for the Sum of the First n Natural Numbers

One common application of induction is to prove the formula for the sum of the first n natural numbers:

S(n) = 1 + 2 + 3 + ... + n = n(n + 1)/2

Step 1: Base Case

We start with n = 1:

S(1) = 1

According to the formula:

1(1 + 1)/2 = 1

Both sides are equal, so the base case holds.

Step 2: Inductive Step

Assume that the formula holds for n = k, i.e.,

S(k) = k(k + 1)/2

Now, we need to prove it for n = k + 1:

S(k + 1) = S(k) + (k + 1)

Substituting the assumption:

S(k + 1) = k(k + 1)/2 + (k + 1)

To combine the terms, we need a common denominator:

S(k + 1) = k(k + 1)/2 + 2(k + 1)/2

S(k + 1) = (k(k + 1) + 2(k + 1))/2

S(k + 1) = ((k + 1)(k + 2))/2

This matches the formula for n = k + 1. Thus, by induction, the formula holds for all natural numbers n.

Application 2: Proving Inequalities

Induction can also be used to prove inequalities. For example, we can prove that:

2^n > n^2 for all integers n ≥ 5.

Step 1: Base Case

First, we check the base case for n = 5:

2^5 = 32 and 5^2 = 25.

Since 32 > 25, the base case holds.

Step 2: Inductive Step

Assume that the statement holds for n = k, i.e.,

2^k > k^2.

Now we need to prove it for n = k + 1:

We want to show that 2^(k + 1) > (k + 1)^2.

From our assumption:

2^(k + 1) = 2 × 2^k > 2 × k^2.

Now we need to show that:

2 × k^2 > (k + 1)^2.

Expanding the right side gives:

2k^2 > k^2 + 2k + 1.

Rearranging gives:

2k^2 - k^2 - 2k - 1 > 0.

Thus, we need to prove:

k^2 - 2k - 1 > 0.

This is a quadratic inequality. We can find the roots using the quadratic formula:

k = (2 ± √(2^2 + 4 × 1))/2 = (2 ± √8)/2 = 1 ± √2.

Since √2 is approximately 1.41, the roots are approximately -0.41 and 2.41. Thus, the inequality holds for k ≥ 5. Therefore, by induction, 2^n > n^2 for all integers n ≥ 5.

Application 3: Proving Properties of Sequences

Another application of induction is to prove properties of sequences. For example, consider the Fibonacci sequence defined as:

F(0) = 0, F(1) = 1, and F(n) = F(n - 1) + F(n - 2) for n ≥ 2.

We want to prove that F(n) ≤ 2^n for all integers n ≥ 0.

Step 1: Base Case

Check the base cases:

• For n = 0: F(0) = 0 ≤ 2^0 = 1.
• For n = 1: F(1) = 1 ≤ 2^1 = 2.
• For n = 2: F(2) = 1 ≤ 2^2 = 4.

All base cases hold.

Step 2: Inductive Step

Assume that F(k) ≤ 2^k for n = k and n = k - 1:

Now, we need to show that F(k + 1) ≤ 2^(k + 1):

F(k + 1) = F(k) + F(k - 1).

By the inductive hypothesis:

F(k) ≤ 2^k and F(k - 1) ≤ 2^(k - 1).

Thus:

F(k + 1) ≤ 2^k + 2^(k - 1).

Factoring out 2^(k - 1) gives:

F(k + 1) ≤ 2^(k - 1)(2 + 1) = 3 × 2^(k - 1).

Since 3 × 2^(k - 1) = 1.5 × 2^k, we need to prove:

1.5 × 2^k ≤ 2^(k + 1).

This holds true, so we conclude that F(n) ≤ 2^n for all integers n ≥ 0.

Summary

• Mathematical induction is a method for proving statements about integers.
• It consists of a base case and an inductive step.
• Induction can be used to prove formulas, inequalities, and properties of sequences.

Check your understanding

1. What are the two main steps in the principle of mathematical induction?
2. Prove that the sum of the first n odd numbers is n^2 using induction.
3. Show that 3^n > n^3 for all integers n ≥ 3 using induction.
4. Prove that the Fibonacci sequence is bounded above by 2^n for all integers n ≥ 0 using induction.