Curriculum Objectives:
- use the method of mathematical induction to establish a given result (questions set may involve divisibility tests and inequalities, for example)
- recognise situations where conjecture based on a limited trial followed by inductive proof is a useful strategy, and carry this out in simple cases, e.g. find the nth derivative of $x{e^x}$
Proof by Induction
Many theorems and formulae relating to positive whole numbers can be proved by a process called mathematical induction. The method is summarised thusly:- assume that it is true for n = k, and prove that it is also true for n = k + 1
- prove that the result is true n = 1 (or perhaps for some other small number n = 2 or 3)
Note: In almost all the questions that follow the second step has been left to reader, however in the examinations you will have to show the second step with all its working.
Summation of Series
Consider the following, rather simple example:Ex. Prove the following:
$\sum\limits_{r = 1}^n {\frac{1}{{r(r + 1)}}} = \frac{n}{{n + 1}}$
We assume, to begin, that the relationship is correct for n = k, which is to say:
$\frac{1}{{1 \times 2}} + \frac{1}{{2 \times 3}} + \frac{1}{{3 \times 4}} + ... + \frac{1}{{k(k + 1)}} = \frac{k}{{k + 1}}$
We then prove that the sum of terms up to (k + 1) obeys the above relationship. We do this thusly:
$\sum\limits_{r = 1}^{k + 1} {\frac{1}{{r(r + 1)}}} = \frac{k}{{k + 1}} + \frac{1}{{(k + 1)(k + 2)}}$
$ = \frac{{k(k + 2) + 1}}{{(k + 1)(k + 2)}}$
$ = \frac{{{k^2} + 2k + 1}}{{(k + 1)(k + 2)}}$
$ = \frac{{{{(k + 1)}^2}}}{{(k + 1)(k + 2)}}$
$ = \frac{{k + 1}}{{(k + 2)}}$
Which is exactly the result we would have gotten by the relationship we set out to prove. We can then say with absolute surety that if the relationship holds for n = k, then it will surely stand for n = k + 1. The result obviously holds for n = 1, you may check this by inputting the one into the above relationship.
Ex. Prove that:
$\sum\limits_{r = 1}^n {{r^3}} = \frac{1}{4}{n^2}{(n + 1)^2}$
Sol.
Let us assume that it holds for n = k, i.e.
$\sum\limits_{r = 1}^k {{r^3}} = \frac{1}{4}{k^2}{(k + 1)^2}$
For n = k + 1, we have:
$\sum\limits_{r = 1}^{k + 1} {{r^3}} = \frac{1}{4}{k^2}{(k + 1)^2} + {(k + 1)^3}$
$= \frac{1}{4}{(k + 1)^2}({k^2} + 4k + 4)$
$ = \frac{1}{4}{(k + 1)^2}{(k + 2)^2}$
The case n = 1 is also obviously true.
Hence by the Principle of Mathematical Induction, this result holds.
Let us look at one more application of Mathematical Induction in summation, before we move on to its applications in sequences, divisibility test and inequalities.
Ex. Prove that:
$\sum\limits_{r = 1}^n {r \cdot r!} = (n + 1)! - 1$
Sol.
Supposing that it holds for n = k, i.e.
$1 \cdot 1! + 2 \cdot 2! + ... + k \cdot k! = (k + 1)! - 1$
For n = k + 1, we have:
$\sum\limits_{r = 1}^{k + 1} {r \cdot r!} = (k + 1)! - 1 + (k + 1) \cdot (k + 1)!$
$ = (k + 1)!(k + 1 + 1) - 1$
$ = (k + 2)(k + 1)! - 1$
$ = (k + 2)! - 1$
$ = \left( {\overline {k + 1} + 1} \right)! - 1$
N = 1, is easily proved, and therefore, by the Principle of Mathematical Induction, our hypothesis that the sum of this series is given by this expression, is true.
Sequences
The following example involves only proving a sequence to be true.Ex. A sequence, ${u_1},{u_2},{u_3}...$ is defined by the recursive formula:
${u_{n + 1}} = 3 - \frac{2}{{{u_n}}}$
Prove that the nth term of the series. is given by:
${u_n} = \frac{{{2^{n + 1}} - 1}}{{{2^n} - 1}}$
Sol.
Assuming that n = k is true then:
${u_k} = \frac{{{2^{k + 1}} - 1}}{{{2^k} - 1}}$
Using the result given, then:
${u_{k + 1}} = 3 - \frac{2}{{{u_k}}}$
${u_{k + 1}} = 3 - \frac{2}{{\frac{{{2^{k + 1}} - 1}}{{{2^k} - 1}}}}$
$= 3 - \frac{{2({2^k} - 1)}}{{{2^{k + 1}} - 1}}$
$ = \frac{{3 \cdot {2^{k + 1}} - 3 - {2^{k + 1}} + 2}}{{{2^{k + 1}} - 1}}$
$ = \frac{{2 \cdot {2^{k + 1}} - 1}}{{{2^{k + 1}} - 1}}$
$ = \frac{{{2^{\overline {k + 1} + 1}} - 1}}{{{2^{k + 1}} - 1}}$
${H_k} \Rightarrow {H_{k + 1}}$
This above notation simply reads, that the hypothesis n = k, implies n = k + 1. Instead writing it all over again, you can employ this notation. n = 1 is easily verified.
Ex. (October/November 2012 Paper 12 Q5)
The first part of the question requires the derivation of the reduction formula,
${I_n} = \frac{1}{2}n{I_{n - 1}}$
where $I_n$ is:
$\int_0^\infty {{x^n}{e^{ - 2x}}dx} $
You may disregard at this point, how we proved this relationship, till we reach the topic reduction formula. The second part is of significance here. Prove by Mathematical Induction that, for all positive integers n, ${I_n} = \frac{{n!}}{{{2^{n + 1}}}}$
Reemploying the strategy from the previous question:
Initial we make some substitutions so that the relationship better conforms with our chosen notation, i.e. replacing n by n + 1 and n - 1 by n.
${I_{n + 1}} = \frac{1}{2}(n + 1){I_n}$
The initial hypothesis is that n = k,
${I_k} = \frac{{k!}}{{{2^{k + 1}}}}$
For n = k + 1
${I_{k + 1}} = \frac{1}{2}(k + 1){I_k}$
${I_{k + 1}} = \frac{1}{2}k\left( {\frac{{k!}}{{{2^{k + 1}}}}} \right)$
${I_{k + 1}} = \frac{{(k + 1)!}}{{{2^{\overline {k + 1} + 1}}}}$
${H_k} \Rightarrow {H_{k + 1}}$
We prove that n = 1 or $H_1$ is true, by noting:
${I_0} = \int_0^\infty {{e^{ - 2x}}dx} = \left[ { - \frac{1}{2}{e^{ - 2x}}} \right]_0^\infty = \frac{1}{2}$
${I_{n + 1}} = \frac{1}{2}(n + 1){I_n}$
${I_1} = \frac{1}{2}(1){I_0} = \frac{1}{2}\left( {\frac{1}{2}} \right) = \frac{{1!}}{{{2^2}}}$
Hence by Principle of Mathematical Induction, this sequence is true for all positive integers.
Divisibility Tests
Now we look at an application of the Inductive proofs in divisibility tests.
Ex. Prove that, for all positive integers, n, ${3^{2n}} + 7$, is divisible by 8.
Sol.
In divisibility tests, we employ a slightly different strategy.
We begin, as before, by assuming $H_k$ ( n = k ) holds, which is to say ${3^{2k}} + 7$ is divisible by 8.
For n = k + 1, the expression becomes
${3^{2(k + 1)}} + 7$
${3^{2k + 2}} + 7$
${3^2} \cdot {3^{2k}} + 7$
We now consider the difference of these two expressions, i.e.,
${3^2} \cdot {3^{2k}} + 7 - ({3^{2k}} + 7) = 9 \cdot {3^{2k}} + 7 - {3^{2k}} - 7 = 8 \cdot {3^{2k}}$
This is obviously divisible by 8, and hence if $H_k$ holds, then $H_{k + 1}$ is also true. $H_1$ is obviously true. Then by Principle of Mathematical Induction, this is true.
In divisibility tests, the general strategy suggested is to consider the either the sum, or difference of any scalar multiple of the expressions derived for n = k +1 and n = k.
Inequalities
Now we consider its use in the context of series. Consider the following question from one of your past papers:Ex. (October/November 2005, Q2)
The sequence ${u_1},{u_2},{u_3}...$ is such that $u_1$ = 1 and:
${u_{n + 1}} = - 1 + \sqrt {{u_n} + 7}$
(I) Prove by Induction that $u_n$ < 2 for all $n \ge 1$.
(II) Show that if $u_n$ = 2 - $\varepsilon $, where $\varepsilon $ is small, then
${u_{n + 1}} \approx 2 - \frac{1}{6}\varepsilon $
Sol.
(I) We begin by assuming that the relationship holds for n = k, i.e.
${u_k} < 2$
For the case n = k +1
${u_{k + 1}} < 2$
As we know:
${u_{k + 1}} = - 1 + \sqrt {{u_k} + 7} $
Therefore
$ - 1 + \sqrt {{u_k} + 7} < 2$
$\sqrt {{u_k} + 7} < 3$
${u_k} + 7 < 9$
${u_k} < 2$
Therefore n = k implies n = k + 1. It is easily seen that n = 1 is true.
(II) For the second part, the only thing of note was that an approximation was expected.
Given:
${u_n} = 2 - \varepsilon $
Using the recursive function that defines the sequence:
${u_{n + 1}} = - 1 + {\left( {9 - \varepsilon } \right)^{\frac{1}{2}}}$
At this stage we use a binomial approximation up to the power one of $\varepsilon $
${u_{n + 1}} \approx - 1 + 3 - \frac{1}{6}\varepsilon = 2 - \frac{1}{6}\varepsilon $
Proving de Moivre's Theorem using Mathematical Induction
The de Moivre's Theorem is a very important theorem, which enriches the study of trigonometry and complex numbers, even further. The knowledge of it, and some of its uses are required by the syllabus, but they have been deferred till we reach the topic complex numbers. While the only past paper question I could find on it concerned itself with positive integer values of n, I shall for completeness discuss the cases where n is negative and zero.The de Moivre Theorem states:
${\left( {\cos \theta + \iota \sin \theta } \right)^n} = \cos (n\theta ) + \iota \sin (n\theta )$, where n is any integer and $\iota = \sqrt { - 1} $
For the case n is positive
n = 1 is true is quite easily seen.
For the case n = k, we have:
${\left( {\cos \theta + \iota \sin \theta } \right)^k} = \cos (k\theta ) + \iota \sin (k\theta )$
For the case, n = k + 1, we have that
${\left( {\cos \theta + \iota \sin \theta } \right)^{k + 1}} = (\cos (k\theta ) + \iota \sin (k\theta ))(cos(\theta ) + \iota sin(\theta ))$
$ = (cos(k\theta )cos(\theta ) + \iota sin(k\theta )cos(\theta ) + \iota \sin (\theta )(cos(k\theta ) + {\iota ^2}\sin (k\theta )sin(\theta ))$
Using the value of ${\iota ^2}$ and the trigonometric identities:
$\cos (A + B) = \cos (A)\cos (B) - \sin (A)sin(B)$
$sin(A + B) = sin(A)cos(B) + sin(B)cos(A)$
We have:
$ = \cos (k + 1)\theta + i\sin (k + 1)\theta $
For the case that n is a negative number, we begin with the following setting n equal to -m, where m is a positive integer.
${\left( {\cos \theta + \iota \sin \theta } \right)^{ - m}} = \frac{1}{{{{(\cos \theta + \iota \sin \theta )}^m}}} = \frac{1}{{\cos (m\theta ) + \iota \sin (m\theta )}}$
$ = \frac{1}{{\cos (m\theta ) + \iota \sin (m\theta )}} \times \frac{{\cos (m\theta ) - i\sin (m\theta )}}{{\cos (m\theta ) - \theta \sin (m\theta )}}$
$ = \frac{{(\cos (m\theta ) - \iota \sin (m\theta ))}}{{{{\cos }^2}(m\theta ) + {{\sin }^2}(m\theta )}} = \cos (m\theta ) - \iota \sin (m\theta )$
$ = \cos ( - m\theta ) + \iota \sin ( - m\theta )$
$ = \cos (n\theta ) + \iota \sin (n\theta )$
These trigonometric identities were used in the third last step:
$\cos (\theta ) = \cos ( - \theta )$
$ - \sin (\theta ) = \sin ( - \theta )$
While I do believe I have covered majority of the possibilities, we should not underestimate the ingenuity of the examiner. There have been questions of induction that involve calculus or some high level algebra. I will get to them, once I have completed all the topics.
No comments:
Post a Comment