Mastering Mathematics Smartly
by Wee Wen Shih

A unique self-help website that provides comprehensive coverage of mathematics at A-level & beyond, written in a student-friendly style.

Mathematical induction

This topic typically features 3 types of question:

  • Prove a known result, usually a sum.
  • Prove the formula of a recurrence relation.
  • Prove a conjecture.

The steps of mathematical induction are quite systematic:

  • Show that the statement is true for the first value of the variable, e.g. n = 1. It is important to note that the first value need not always be 1.

  • Assume that the statement is true for n = k.

  • Show that the statement is true for n = k + 1, by applying the assumption.

  • State the conclusion.

Now, let us look at a worked example of induction related to a recurrence relation.

Conjectures

In this short article, we look at three sequences and how we go about observing patterns to obtain conjectures.

Example 1: U_1 = 3, U_2 = 7, U_3 = 15, U_4 = 31, U_5 = 63.

We can rewrite the terms as U_1 = 2^2 - 1, U_2 = 2^3 - 1, U_3 = 2^4 - 1, U_4 = 2^5 - 1, U_5 = 2^6 - 1.

Notice that the power of 2 is one more than the subscript of U for every term. This leads us to say that U_n = 2^{n + 1} - 1, n \ge 1.

So, a good starting point is to observe whether the values in the sequence follow the form U_n = a^{m} \pm b where n, m are closely related.

Example 2: U_1 = \frac{1}{2}, U_2 = \frac{3}{5}, U_3 = \frac{2}{3}, U_4 = \frac{5}{7}, U_5 = \frac{3}{4}.

First, we notice that a pattern arising from U_2, U_4 in which the denominator's value is two more than the numerator's value and the numerator's value is one more than the subscript of U.

With this observation, we now look closely at U_1, U_3, U_5 and determine whether they follow the same pattern.

Yes, they do because U_1 = \frac{1}{2} = \frac{2}{4}, U_3 = \frac{2}{3} = \frac{4}{6}, U_5 = \frac{3}{4} = \frac{6}{8}. We can therefore conclude that U_n = \frac{n + 1}{n + 3}, n \ge 1.

Thus, a good starting point is to observe whether there is any relationship between the numerator and the denominator.

Example 3: U_1 = \frac{5}{3}, U_2 = \frac{1}{3}, U_3 = \frac{1}{7}, U_4 = \frac{5}{63}, U_5 = \frac{5}{99}.

To begin with, we see a pattern from U_1, U_4, U_5 in which the numerator is always 5 and the denominator can be factorised, i.e. (1)(3), (7)(9), (9)(11). Also, the larger factor is two more than the smaller one.

We then verify if U_2, U_3 stick to this observation by rewriting them as U_2 = \frac{1}{3} = \frac{5}{(3)(5)}, U_3 = \frac{1}{7} = \frac{5}{(5)(7)}, so indeed they do.

So, we guess that U_n = \frac{5}{(2n - 1)(2n + 1)}, n \ge 1.

Therefore, a good starting point is to factorise any number which is not prime.

Upon obtaining a conjecture, it is natural for us to follow up by validating it via mathematical induction in the next step.

Exercise: It is given that U_n = \sum_{r = 1}^{n} (r)(r!).  Write down the values of U_1, U_2, U_3 and U_4, and give a possible formula of U_n in terms of n. Prove your conjecture by mathematical induction.