Je bent je ingevulde velden bij deze pagina aan het verwijderen. Ben je zeker dat je dit wilt doen?
You are erasing your filled-in fields on this page. Are you sure that is what you want?
Nieuwe Versie BeschikbaarNew Version Available
Er is een update van deze pagina. Als je update naar de meest recente versie, verlies je mogelijk je huidige antwoorden voor deze pagina. Hoe wil je verdergaan ?
There is an updated version of this page. If you update to the most recent version, then your current progress on this page will be erased. Regardless, your record of completion will remain. How would you like to proceed?
The Chinese philosopher Confucius is credited with the saying, “A journey of a thousand miles begins with a single step.” In
many ways, this is the central theme of this section. Here we introduce a method of proof, Mathematical Induction, which
allows us to prove many of the formulas we have merely motivated in Sections Sequences and Summation by starting with just a single step. A good
example is the formula for arithmetic sequences we touted in Equation arithgeoformula. Arithmetic sequences are defined recursively, starting
with \(a_{1} = a\) and then \(a_{n+1} = a_{n} + d\) for \(n \geq 1\). This tells us that we start the sequence with \(a\) and we go from one term to the next by successively adding \(d\).
In symbols,
\[ a, a+d, a+2d, a + 3d, a + 4d + \ldots \]
The pattern suggested here is that to reach the \(n\)th term, we start with \(a\) and add \(d\) to it exactly \(n-1\) times, leading to the formula \(a_{n} = a + (n-1)d\) for \(n \geq 1\).
In order to prove this is the case, we have:
The Principle of Mathematical Induction (PMI):
Suppose \(P(n)\) is a sentence involving the natural number \(n\).
IF
\(P(1)\) is true and
whenever \(P(k)\) is true, it follows that \(P(k+1)\) is also true
THEN the sentence \(P(n)\) is true for all natural numbers \(n\).
The Principle of Mathematical Induction, or PMI for short, is exactly that - a principle. (Another word for this you may
have seen is ‘axiom.’) It is a property of the natural numbers we either choose to accept or reject. The notation which is used
here, ‘\(P(n)\),’ acts just like function notation. For example, if \(P(n)\) is the sentence (formula) ‘\(n^2 + 1 = 3\)’, then \(P(1)\) would be ‘\(1^2 + 1 = 3\)’, which is false. In this
case, the construction \(P(k+1)\) would be ‘\((k+1)^2 + 1 = 3\)’.
In English, the PMI says that if we want to prove that a formula works for all natural numbers \(n\), we start by
showing it is true for \(n=1\) (the ‘base step’) and then show that if it is true for a generic natural number \(k\), then it must
be true for the next natural number, \(k+1\) (the ‘inductive step’). In essence, by showing that \(P(k+1)\) must always be true
when \(P(k)\) is true, we are showing that the formula \(P(1)\) can be used to get the formula \(P(2)\), which in turn can be used to
derive the formula \(P(3)\), which in turn can be used to establish the formula \(P(4)\), and so on, for all natural numbers
\(n\).
One might liken Mathematical Induction to a repetitive process like climbing stairs. (Falling dominoes is the
most widely used metaphor in the mainstream College Algebra books.) If you are sure that (1) you can get
on the stairs (the base case) and (2) you can climb from any one step to the next step (the inductive step),
then presumably you can climb the entire staircase. (This is how Carl climbed the stairs in the Cologne
Cathedral. Well, that, and encouragement from Kai.) We get some more practice with induction in the following
example.
Prove the following assertions using the Principle of Mathematical Induction.
If \(a_{1} = 4\) and \(a_{n+1} = -\frac {a_{n}}{2}\) for \(n \geq 1\), then prove \(a_{n} = (-1)^{n-1} 2^{3-n}\) for \(n \geq 1\).
\(1 + 3 + 5 + \ldots + (2n-1) = n^2\)
\(3^{n} > 100n\) for \(n > 5\).
Solution.
To prove \(a_{n} = (-1)^{n-1} 2^{3-n}\) for \(n \geq 1\) by induction, we first identify the sentence \(P(n)\) as the equation \(a_{n} = (-1)^{n-1} 2^{3-n}\). The sentence \(P(1)\) is the equation \(a_{1} = (-1)^{1-1}2^{3-1}\) or,
after simplifying, \(a_{1} = 4\), which we are told is true.
Next, we assume the sentence \(P(k)\) is true, that is, \(a_{k}= (-1)^{k-1} 2^{3-k}\) (this is called the ‘induction hypothesis’) and must use this to
deduce\(P(k+1)\) is true. That is, we need to use the fact that \(a_{k}= (-1)^{k-1} 2^{3-k}\) to show \(a_{k+1} = (-1)^{(k+1)-1}2^{3-(k+1)}\) or, after simplifying, \(a_{k+1} = (-1)^{k} 2^{2-k}\).
We are told \(a_{k+1} = -\frac {a_{k}}{2}\) and we are assuming \(a_{k}= (-1)^{k-1} 2^{3-k}\), so we put these together to get
as required. Hence, by induction, \(a_{n} = (-1)^{n-1} 2^{3-n}\) for \(n \geq 1\).
We take a moment and recognize the sequence here, as described, is a geometric sequence with \(a = 4\) and \(r = -\frac {1}{2}\). Using
Equation arithgeoformula we arrive at the explicit formula for \(a_{n} = 4 \left (- \frac {1}{2} \right )^{n-1}\) for \(n \geq 1\) which we leave to the reader to show reduces to \(a_{n} = (-1)^{n-1} 2^{3-n}\). (Note:
You’ll be asked to prove Equation arithgeoformula in Exercise proofgeosequeneex.)
As above, our first step is to identify the sentence \(P(n)\) which is the equation \(1 + 3 + 5 + \ldots + (2n-1) = n^2\) which is more precisely written using
summation notation: \(\displaystyle { \sum _{j=1}^{n} (2j-1) = n^2}\). (Note we use ‘\(j\)’ as our dummy variable here since ‘\(n\)’ is already used and we usually
reserve ‘\(k\)’ for the induction variable.)
The sentence \(P(1)\) is \(\displaystyle { \sum _{j=1}^{1} (2j-1) = 1^2}\) which reduces to \(2(1)-1 = 1\) which is true. Next, we assume \(P(k)\) is true, \(\displaystyle { \sum _{j=1}^{k} (2j-1) = k^2}\), and use it to show \(P(k+1)\) is true: \(\displaystyle { \sum _{j=1}^{k+1} (2j-1) = (k+1)^2}\). We
have:
as required. Hence, by induction, \(1 + 3 + 5 + \ldots + (2n-1) = n^2\) for all natural numbers \(n \geq 0\).
As with the first example, this problem, too, can be shown using a previous result. The sequence being added
in the equation \(1 + 3 + 5 + \ldots + (2n-1)=n^2\) is arithmetic, so Equation arithgeosum applies to give the sum as \(\frac {n}{2} (1 + (2n-1)) = n^2\). We’ll prove Equation arithgeosum for arithmetic
sequences in the next example. We leave the case for geometric sequences to the reader in Exercise proofgeosumex.
The first wrinkle we encounter in this problem is that we are asked to prove this formula for \(n > 5\) instead of \(n \geq 1\). Since \(n\) is
a natural number, this means our base step occurs at \(n=6\). We can still use the PMI in this case, but our conclusion
will be that the formula is valid for all \(n \geq 6\).
We let \(P(n)\) be the inequality \(3^{n} > 100n\), and check that \(P(6)\) is true. Comparing \(3^6 = 729\) and \(100(6) = 600\), we see \(3^6 > 100(6)\) as required.
Next, we assume that \(P(k)\) is true, that is we assume \(3^{k} > 100k\). We need to show that \(P(k+1)\) is true, that is, we need to show \(3^{k+1} > 100(k+1)\).
Since \(3^{k+1} = 3 \cdot 3^{k}\), the induction hypothesis gives \(3^{k+1} = 3 \cdot 3^{k} > 3(100k) = 300k\).
To complete the proof, we need to show \(300k > 100(k+1)\) for \(k \geq 6\). Solving \(300k > 100(k+1)\) we get \(k > \frac {1}{2}\). Since \(k \geq 6\), we know this is true.
Putting all of this together, we have \(3^{k+1} = 3 \cdot 3^{k} > 3(100k) = 300k > 100(k+1)\), and hence \(P(k+1)\) is true. By induction, \(3^{n} > 100n\) for all \(n \geq 6\). □
One of the things that may seem troubling about proving statements by induction is the induction hypothesis: that is, assuming
that \(P(k)\) is true. After all, isn’t that what we are trying to prove? When we assume \(P(k)\) is true, we are doing so with the
express purpose of showing that \(P(k+1)\) follows. That is, we are interested in showing how we go ‘from one step to the
next.’
As mentioned at the beginning of this section, induction is the formal way to prove many the formulas we’ve used in Sections Sequences
and Summation. Indeed, now that we have some experience using the PMI to prove formulas, we return to proving the formula for an
arithmetic sequence.
Recall we define an arithmetic sequence recursively as: \(a_{1} = a\) and \(a_{n+1} = a_{n} + d\) for \(n \geq 1\). We need to prove \(a_{n} = a + (n-1) d\) for \(n \geq 1\). Identifying \(P(n)\) as the formula \(a_{n} = a + (n-1)d\), we see \(P(1)\)
is \(a_{1} = a + (1-1) d = a\), which is true.
Next, we assume \(P(k)\) is true, that is, \(a_{k} = a + (k-1)d\) and use this to show \(P(k+1)\), or \(a_{k+1} = a+((k+1)-1)d\) or \(a_{k+1} = a + kd\) is true. We know \(a_{k+1} = a_{k} + d\) from the definition of arithmetic sequence,
hence
\[ a_{k+1} = a_{k} + d = a + (k-1)d + d= a + kd,\]
as required. Hence, \(a_{n} = a + (n-1)d\), for all natural numbers \(n \geq 1\).
We conclude this section with three more proofs by induction.
Prove the following assertions using the Principle of Mathematical Induction.
The sum formula for arithmetic sequences: \(\displaystyle {\sum _{j=1}^{n} (a + (j-1)d) = \frac {n}{2}(2a + (n-1)d)}\).
For a complex number \(z\), \(\left (\overline {z}\right )^n = \overline {z^{n}}\) for \(n \geq 1\).
Let \(A\) be an \(n \times n\) matrix and let \(A'\) be the matrix obtained by replacing a row \(R\) of \(A\) with \(cR\) for some real number \(c\). Use the
definition of determinant to show \(\det (A') = c \det (A)\).
Solution.
We set \(P(n)\) to be the equation we are asked to prove, namely \(\displaystyle {\sum _{j=1}^{n} (a + (j-1)d) = \frac {n}{2}(2a + (n-1)d)}\). The statement \(P(1)\), \(\displaystyle {\sum _{j=1}^{1} (a + (j-1)d) = \frac {1}{2}(2a + (1-1)d)}\) , reduces to \(a+(0)d = \frac {1}{2} (2a)\) or \(a = a\), which is true.
Next we assume \(P(k)\) is true, that is, we assume \(\displaystyle {\sum _{j=1}^{k} (a + (j-1)d) = \frac {k}{2}(2a + (k-1)d)}\) and use this to show \(P(k+1)\) is true: \(\displaystyle {\sum _{j=1}^{k+1} (a + (j-1)d) = \frac {k+1}{2}(2a + (k+1-1)d) = \frac {k+1}{2}(2a + kd)}\):
\[ \underbrace {\displaystyle {\sum _{j=1}^{k+1} (a + (j-1)d)}}_{\text {adding $k+1$ terms}} = \underbrace {\displaystyle {\sum _{j=1}^{k} (a + (j-1)d)}}_{\text {adding the first $k$ terms}} + \underbrace {(a+((k+1)-1)d ) \vphantom {\displaystyle {\sum _{j=1}^{k+1}}} }_{\text {adding the first $k+1$ term}} = \underbrace {\frac {k}{2}(2a + (k-1)d)\vphantom {\displaystyle {\sum _{j=1}^{k+1}}} }_{\text {$P(k)$}} +\underbrace {a+kd \vphantom {\displaystyle {\sum _{j=1}^{k+1}}} }_{\text {simplify}}.\]
which completes the proof that \(P(k+1)\) is true. By induction, \(\displaystyle {\sum _{j=1}^{n} (a + (j-1)d) = \frac {n}{2}(2a + (n-1)d)}\) for all
natural numbers \(n\).
We let \(P(n)\) be the equation \(\left (\overline {z}\right )^n = \overline {z^{n}}\). The base case \(P(1)\) is \(\left (\overline {z}\right )^1 = \overline {z^{1}}\) reduces to \(\overline {z} = \overline {z}\) which is true. We now assume \(P(k)\) is true, that is, we
assume \(\left (\overline {z}\right )^k = \overline {z^{k}}\) and use this to show that \(P(k+1)\) is true, namely \(\left (\overline {z}\right )^{k+1} = \overline {z^{k+1}}\).
Since \(\left (\overline {z}\right )^{k+1} = \left (\overline {z}\right )^{k} \, \overline {z}\), we can use the induction hypothesis to write \(\left (\overline {z}\right )^k = \overline {z^{k}}\). Hence,
where the second-to-last equality is courtesy of
the product rule for conjugates (See Exercise zbarexercise in Section ComplexZeros: \(\overline {z} \, \overline {w} = \overline {zw}\).) This shows \(P(k+1)\) is true and hence, by induction,
\(\left (\overline {z}\right )^n = \overline {z^{n}}\) for all natural numbers \(n\).
To prove this determinant property, we use induction on \(n\), where we take \(P(n)\) to be that the property we wish to
prove is true for all \(n \times n\) matrices. For the base case, we note that if \(A\) is a \(1 \times 1\) matrix, then \(A = [a]\) so \(A' = [ca]\). By definition, \(\det (A) = a\) and \(\det (A') = ca\) so
we have \(\det (A') = c \det (A)\).
Now suppose that the property we wish to prove is true for all \(k \times k\) matrices. Let \(A\) be a \((k+1) \times (k+1)\) matrix. We have two cases,
depending on if the row \(R\) being replaced is the first row of \(A\).
CASE 1: The row \(R\) being replaced is the first row of \(A\). By definition,
where the \(1p\) cofactor of \(A'\) is \(C'_{1p} = (-1)^{(1+p)} \det \left (A'_{1p}\right )\) and \(A'_{1p}\) is the \(k \times k\) matrix obtained by deleting the \(1\)st row and \(p\)th column of \(A'\). (See
Section Determinants for a review of this notation.)
Since the first row of \(A'\) is \(c\) times the first row of \(A\), we have \(a'_{1p} = c \, a_{1p}\). In addition, since the remaining rows of \(A'\) are identical
to those of \(A\), \(A'_{1p} = A_{1p}\). (To obtain these matrices, the first row of \(A'\) is removed.) Hence \(\det \left (A'_{1p}\right ) = \det \left (A_{1p}\right )\), so that \(C'_{1p} = C_{1p}\). As a result, we get
\[ \det (A') = \displaystyle {\sum _{p=1}^{n} a'_{1p} C'_{1p}} = \displaystyle {\sum _{p=1}^{n} c \, a_{1p} C_{1p}} = c \displaystyle {\sum _{p=1}^{n} a_{1p} C_{1p}} = c \det (A), \]
as required. Hence, \(P(k+1)\) is true in this case, which means the result is true in this case for all natural numbers \(n \geq 1\).
(You’ll note that we did not use the induction hypothesis at all in this case. It is possible to restructure the proof
so that induction is only used where it is needed. While mathematically more elegant, it is less intuitive.)
CASE 2: The row \(R\) being replaced is the not the first row of \(A\). By definition,
where in this case, \(a'_{1p} = a_{1p}\), since the first rows of \(A\) and \(A'\) are the same. The matrices \(A'_{1p}\) and \(A_{1p}\), on the other hand, are
different but in a very predictable way \(-\) the row in \(A'_{1p}\) which corresponds to the row \(cR\) in \(A'\) is exactly \(c\) times the row in
\(A_{1p}\) which corresponds to the row \(R\) in \(A\).
This means \(A'_{1p}\) and \(A_{1p}\) are \(k \times k\) matrices which satisfy the induction hypothesis. Hence, we know \(\det \left (A'_{1p}\right ) = c \det \left (A_{1p}\right )\) and \(C'_{1p} = c \, C_{1p}\). We get
which establishes \(P(k+1)\) to be true. Hence by induction, we have shown that the result holds in this case for \(n \geq 1\) and we
are done. □
While we have used the Principle of Mathematical Induction to prove some of the formulas we have merely motivated in the
text, our main use of this result comes in Section Binomial to prove the celebrated Binomial Theorem. The ardent Mathematics student
will no doubt see the PMI in many courses yet to come. Sometimes it is explicitly stated and sometimes it remains hidden in
the background. If ever you see a property stated as being true ‘for all natural numbers \(n\)’, it’s a solid bet that the formal proof
requires the Principle of Mathematical Induction.
PreCalculus