Proof by Mathematical Induction

Mathematical induction is a powerful technique used in mathematics to prove that a statement is true for all natural numbers. This concept may seem complicated at first, but it can be understood with some simple steps and examples.

Understanding induction

Let's start by understanding what mathematical induction is. Imagine you have a long row of dominoes standing upright. If you push the first domino, and each domino pushes the next, all the dominoes will eventually fall. This is how mathematical induction works. It consists of two main steps:

1. Base case: Show that the statement is true for the initial value (usually when n = 1).
2. Inductive step: Show that if the statement is true for some arbitrary value n = k, then it must also be true for n = k + 1.

If both these steps are completed successfully, then it can be concluded that this statement is true for all natural numbers.

Stages of induction

Step 1: Base case

The base case is the starting point of induction. Often, you will verify that the statement is true for n = 1. Proving this base case is like making sure that the first domino is set to fall correctly.

Phase 2: Inductive phase

The inductive phase comprises two sub-phases:

1. Assume that the statement is true for n = k. This assumption is known as the "inductive hypothesis."
2. Prove that the statement is true for n = k + 1.

Examples to illustrate induction

Let us consider a simple example.

Prove that the sum of the first n natural numbers is given by the formula:

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

Base case

First, we check if the statement is true for n = 1:

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

Thus, the original case is true.

Inductive phase

Now, let us assume that the statement is true for n = k, that is:

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

We need to show that this also works for n = k + 1.

If the formula is true for n = k, then we have:

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

According to the recognition:

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

Add k + 1 to both sides:

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

Combine and simplify the expressions:

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

This corresponds to the form (k+1)((k+1)+1)/2, which proves the inductive step.

Conclusion

Since both the base case and the inductive step have been proven by mathematical induction, the formula:

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

is true for all natural numbers n.

Visual example

This shows the terms being placed together like rectangles placed together, which visually simulates an increasing sum.

More textual examples

Example 2: Proving power of 2

Let us prove that for any natural number n, the sum of powers of 2 is:

1 + 2 + 4 + ... + 2^{n-1} = 2^n - 1

Base case

For n = 1:

1 = 2^1 - 1 = 1

Inductive phase

Assume that for n = k it is true:

1 + 2 + 4 + ... + 2^{k-1} = 2^k - 1

Prove that for n = k + 1:

1 + 2 + 4 + ... + 2^{k-1} + 2^k = (2^k - 1) + 2^k = 2^(k+1) - 1

Thus, the formula is true for all natural numbers n.

Why does induction work?

Induction is effective because it is based on established truths. Once you prove the statement for the first case, and you show that if it works on any 'n', it works on 'n+1', it logically follows that it works for every subsequent value.

Common mistakes and how to avoid them

There are several pitfalls when using mathematical induction. Always make sure:

• You have a correct and valid base case.
• The inductive hypothesis is properly stated.
• You have correctly set up the inductive step from k to k + 1.

These elements are crucial to rigorous proof.

Practice problems

1. Prove that the sum of the first n odd numbers is n^2.
2. Verify by induction that 2^n > n^2 for all n ≥ 5.
3. Show that 3^n > 2n+3 where n > 1.

Conclusion

Mathematical induction is not only a technique, but a way of thinking that logically extends truth from one domain to a wider domain. With practice, it becomes a powerful tool in your mathematical toolkit, helping you prove statements that are true for an infinite set of numbers. As you gain confidence with induction, you will find it much easier to tackle a variety of problems, especially those involving sequences, sums, and inequalities.

Happy learning!

Comments