10.3 Mathematical Induction

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 10.1 and 10.2 by starting with just a single step. A good example is the formula for arithmetic sequences we touted in Equation 10.1. Arithmetic sequences are defined recursively, starting with $a sub 1 equals a$ and then $a_{n + 1} = a_{n} + d$ for $n greater than or equal to 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 + 2 d, a + 3 d, a + 4 d + \dots$

The pattern suggested here is that to reach the $n$ th term, we start with $a$ and add $d$ to it exactly $n minus 1$ times, leading to the formula $a_{n} = a + (n - 1) d$ for $n greater than or equal to 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$ .

$P ⁢ open parenthesis 1 close parenthesis$ is true and
whenever $P (k)$ is true, it follows that $P ⁢ open parenthesis k plus 1 close parenthesis$ 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.¹ 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 ⁢ open parenthesis 1 close parenthesis$ would be ` $1^{2} + 1 = 3$ ', which is false. In this case, the construction $P ⁢ open parenthesis k plus 1 close parenthesis$ 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 equals 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 plus 1$ (the `inductive step'). In essence, by showing that $P ⁢ open parenthesis k plus 1 close parenthesis$ must always be true when $P (k)$ is true, we are showing that the formula $P ⁢ open parenthesis 1 close parenthesis$ can be used to get the formula $P ⁢ open parenthesis 2 close parenthesis$ , which in turn can be used to derive the formula $P ⁢ open parenthesis 3 close parenthesis$ , which in turn can be used to establish the formula $P ⁢ open parenthesis 4 close parenthesis$ , and so on, for all natural numbers $n$ .

One might liken Mathematical Induction to a repetitive process like climbing stairs.² 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.³ We get some more practice with induction in the following example.

Example 1

Prove the following assertions using the Principle of Mathematical Induction.

If $a sub 1 equals 4$ and $a_{n + 1} = - \frac{a_{n}}{2}$ for $n greater than or equal to 1$ , then prove $a_{n} = {(- 1)}^{n - 1} 2^{3 - n}$ for $n greater than or equal to 1$ .
$1 + 3 + 5 + \dots + (2 n - 1) = n^{2}$
$3 to the power n greater than 100 ⁢ n$ for $n greater than 5$ .

To prove $a_{n} = {(- 1)}^{n - 1} 2^{3 - n}$ for $n greater than or equal to 1$ by induction, we first identify the sentence $P (n)$ as the equation $a_{n} = {(- 1)}^{n - 1} 2^{3 - n}$ . The sentence $P ⁢ open parenthesis 1 close parenthesis$ is the equation $a_{1} = {(- 1)}^{1 - 1} 2^{3 - 1}$ or, after simplifying, $a sub 1 equals 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 ⁢ open parenthesis k plus 1 close parenthesis$ 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
$a_{k + 1} = - \frac{a_{k}}{2} = - \frac{{(- 1)}^{k - 1} 2^{3 - k}}{2} = {(- 1)}^{1} \frac{{(- 1)}^{k - 1} 2^{3 - k}}{2^{1}} = {(- 1)}^{k - 1 + 1} 2^{3 - k + 1} = {(- 1)}^{k} 2^{2 - k},$
as required. Hence, by induction, $a_{n} = {(- 1)}^{n - 1} 2^{3 - n}$ for $n greater than or equal to 1$ .
We take a moment and recognize the sequence here, as described, is a geometric sequence with $a equals 4$ and $r = - \frac{1}{2}$ . Using Equation 10.1 we arrive at the explicit formula for $a_{n} = 4 {(- \frac{1}{2})}^{n - 1}$ for $n greater than or equal to 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 10.1 in Exercise.)
As above, our first step is to identify the sentence $P (n)$ which is the equation $1 + 3 + 5 + \dots + (2 n - 1) = n^{2}$ which is more precisely written using summation notation: $\sum_{j = 1}^{n} (2 j - 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 ⁢ open parenthesis 1 close parenthesis$ is $\sum_{j = 1}^{1} (2 j - 1) = 1^{2}$ which reduces to $2 (1) - 1 = 1$ which is true. Next, we assume $P (k)$ is true, $\sum_{j = 1}^{k} (2 j - 1) = k^{2}$ , and use it to show $P ⁢ open parenthesis k plus 1 close parenthesis$ is true: $\sum_{j = 1}^{k + 1} (2 j - 1) = {(k + 1)}^{2}$ . We have:
$\underset{adding k + 1 terms}{\underset{⏟}{\sum_{j = 1}^{k + 1} (2 j - 1)}} = \underset{adding the first k terms}{\underset{⏟}{\sum_{j = 1}^{k} (2 j - 1)}} + \underset{adding the first k + 1 term}{\underset{⏟}{(2 (k + 1) - 1)}} = \underset{P (k)}{\underset{⏟}{k^{2}}} + \underset{simplify}{\underset{⏟}{2 k + 1}} = \underset{factor}{\underset{⏟}{{(k + 1)}^{2}}},$
as required. Hence, by induction, $1 + 3 + 5 + \dots + (2 n - 1) = n^{2}$ for all natural numbers $n greater than or equal to 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 + \dots + (2 n - 1) = n^{2}$ is arithmetic, so Equation 10.2 applies to give the sum as $\frac{n}{2} (1 + (2 n - 1)) = n^{2}$ . We'll prove Equation 10.2 for arithmetic sequences in the next example. We leave the case for geometric sequences to the reader in Exercise.
The first wrinkle we encounter in this problem is that we are asked to prove this formula for $n greater than 5$ instead of $n greater than or equal to 1$ . Since $n$ is a natural number, this means our base step occurs at $n equals 6$ . We can still use the PMI in this case, but our conclusion will be that the formula is valid for all $n greater than or equal to 6$ .
We let $P (n)$ be the inequality $3 to the power n greater than 100 ⁢ n$ , and check that $P ⁢ open parenthesis 6 close parenthesis$ is true. Comparing $3^{6} = 729$ and $100 ⁢ open parenthesis 6 close parenthesis equals 600$ , we see $3 to the power 6 greater than 100 ⁢ open parenthesis 6 close parenthesis$ as required.
Next, we assume that $P (k)$ is true, that is we assume $3 to the power k greater than 100 ⁢ k$ . We need to show that $P ⁢ open parenthesis k plus 1 close parenthesis$ 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 (100 k) = 300 k$ .
To complete the proof, we need to show $300 ⁢ k greater than 100 ⁢ open parenthesis k plus 1 close parenthesis$ for $k greater than or equal to 6$ . Solving $300 ⁢ k greater than 100 ⁢ open parenthesis k plus 1 close parenthesis$ we get $k > \frac{1}{2}$ . Since $k greater than or equal to 6$ , we know this is true.
Putting all of this together, we have $3^{k + 1} = 3 \cdot 3^{k} > 3 (100 k) = 300 k > 100 (k + 1)$ , and hence $P ⁢ open parenthesis k plus 1 close parenthesis$ is true. By induction, $3 to the power n greater than 100 ⁢ n$ for all $n greater than or equal to 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 ⁢ open parenthesis k plus 1 close parenthesis$ 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 10.1 and 10.2. 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 sub 1 equals a$ and $a_{n + 1} = a_{n} + d$ for $n greater than or equal to 1$ . We need to prove $a_{n} = a + (n - 1) d$ for $n greater than or equal to 1$ . Identifying $P (n)$ as the formula $a_{n} = a + (n - 1) d$ , we see $P ⁢ open parenthesis 1 close parenthesis$ 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 ⁢ open parenthesis k plus 1 close parenthesis$ , or $a_{k + 1} = a + ((k + 1) - 1) d$ or $a_{k + 1} = a + k d$ 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 + k d,$

as required. Hence, $a_{n} = a + (n - 1) d$ , for all natural numbers $n greater than or equal to 1$ .

We conclude this section with three more proofs by induction.

Example 2

Prove the following assertions using the Principle of Mathematical Induction.

The sum formula for arithmetic sequences: $\sum_{j = 1}^{n} (a + (j - 1) d) = \frac{n}{2} (2 a + (n - 1) d)$ .
For a complex number $z$ , ${(\bar{z})}^{n} = \bar{z^{n}}$ for $n greater than or equal to 1$ .
Let $A$ be an $n \times n$ matrix and let $A^{'}$ be the matrix obtained by replacing a row $R$ of $A$ with $c R$ for some real number $c$ . Use the definition of determinant to show $det (A^{'}) = c det (A)$ .

We set $P (n)$ to be the equation we are asked to prove, namely $\sum_{j = 1}^{n} (a + (j - 1) d) = \frac{n}{2} (2 a + (n - 1) d)$ . The statement $P ⁢ open parenthesis 1 close parenthesis$ , $\sum_{j = 1}^{1} (a + (j - 1) d) = \frac{1}{2} (2 a + (1 - 1) d)$ , reduces to $a + (0) d = \frac{1}{2} (2 a)$ or $a = a$ , which is true. Next we assume $P (k)$ is true, that is, we assume $\sum_{j = 1}^{k} (a + (j - 1) d) = \frac{k}{2} (2 a + (k - 1) d)$ and use this to show $P ⁢ open parenthesis k plus 1 close parenthesis$ is true: $\sum_{j = 1}^{k + 1} (a + (j - 1) d) = \frac{k + 1}{2} (2 a + (k + 1 - 1) d) = \frac{k + 1}{2} (2 a + k d)$ :
$\underset{adding k + 1 terms}{\underset{⏟}{\sum_{j = 1}^{k + 1} (a + (j - 1) d)}} = \underset{adding the first k terms}{\underset{⏟}{\sum_{j = 1}^{k} (a + (j - 1) d)}} + \underset{adding the first k + 1 term}{\underset{⏟}{(a + ((k + 1) - 1) d)}} = \underset{P (k)}{\underset{⏟}{\frac{k}{2} (2 a + (k - 1) d)}} + \underset{simplify}{\underset{⏟}{a + k d}} .$
We leave it to the reader to show that, indeed,
$\frac{k}{2} (2 a + (k - 1) d) + a + k d = \frac{k + 1}{2} (2 a + d),$
which completes the proof that $P ⁢ open parenthesis k plus 1 close parenthesis$ is true. By induction, $\sum_{j = 1}^{n} (a + (j - 1) d) = \frac{n}{2} (2 a + (n - 1) d)$ for all natural numbers $n$ .
We let $P (n)$ be the equation ${(\bar{z})}^{n} = \bar{z^{n}}$ . The base case $P ⁢ open parenthesis 1 close parenthesis$ is ${(\bar{z})}^{1} = \bar{z^{1}}$ reduces to $\bar{z} = \bar{z}$ which is true. We now assume $P (k)$ is true, that is, we assume ${(\bar{z})}^{k} = \bar{z^{k}}$ and use this to show that $P ⁢ open parenthesis k plus 1 close parenthesis$ is true, namely ${(\bar{z})}^{k + 1} = \bar{z^{k + 1}}$ .
Since ${(\bar{z})}^{k + 1} = {(\bar{z})}^{k} \bar{z}$ , we can use the induction hypothesis to write ${(\bar{z})}^{k} = \bar{z^{k}}$ . Hence,
${(\bar{z})}^{k + 1} = {(\bar{z})}^{k} \bar{z} = \bar{z^{k}} \bar{z} = \bar{z^{k} z} = \bar{z^{k + 1}},$
where the second-to-last equality is courtesy of the product rule for conjugates⁴ This shows $P ⁢ open parenthesis k plus 1 close parenthesis$ is true and hence, by induction, ${(\bar{z})}^{n} = \bar{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^{'} = [c a]$ . By definition, $det (A) = a$ and $det (A^{'}) = c a$ 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,
$det (A^{'}) = \sum_{p = 1}^{n} a_{1 p}^{'} C_{1 p}^{'}$
where the $1 ⁢ p$ cofactor of $A^{'}$ is $C_{1 p}^{'} = {(- 1)}^{(1 + p)} det (A_{1 p}^{'})$ and $A sub 1 ⁢ p prime$ is the $k \times k$ matrix obtained by deleting the $1$ st row and $p$ th column of $A^{'}$ .⁵
Since the first row of $A^{'}$ is $c$ times the first row of $A$ , we have $a sub 1 ⁢ p prime equals c ⁢ a sub 1 ⁢ p$ . In addition, since the remaining rows of $A^{'}$ are identical to those of $A$ , $A sub 1 ⁢ p prime equals A sub 1 ⁢ p$ . (To obtain these matrices, the first row of $A^{'}$ is removed.) Hence $det open parenthesis A sub 1 ⁢ p prime close parenthesis equals det open parenthesis A sub 1 ⁢ p close parenthesis$ , so that $C sub 1 ⁢ p prime equals C sub 1 ⁢ p$ . As a result, we get
$det (A^{'}) = \sum_{p = 1}^{n} a_{1 p}^{'} C_{1 p}^{'} = \sum_{p = 1}^{n} c a_{1 p} C_{1 p} = c \sum_{p = 1}^{n} a_{1 p} C_{1 p} = c det (A),$
as required. Hence, $P ⁢ open parenthesis k plus 1 close parenthesis$ is true in this case, which means the result is true in this case for all natural numbers $n greater than or equal to 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,
$det (A^{'}) = \sum_{p = 1}^{n} a_{1 p}^{'} C_{1 p}^{'},$
where in this case, $a sub 1 ⁢ p prime equals a sub 1 ⁢ p$ , since the first rows of $A$ and $A^{'}$ are the same. The matrices $A sub 1 ⁢ p prime$ and $A sub 1 ⁢ p$ , on the other hand, are different but in a very predictable way the row in $A sub 1 ⁢ p prime$ which corresponds to the row $c R$ in $A^{'}$ is exactly $c$ times the row in $A sub 1 ⁢ p$ which corresponds to the row $R$ in $A$ .
This means $A sub 1 ⁢ p prime$ and $A sub 1 ⁢ p$ are $k \times k$ matrices which satisfy the induction hypothesis. Hence, we know $det open parenthesis A sub 1 ⁢ p prime close parenthesis equals c ⁢ det open parenthesis A sub 1 ⁢ p close parenthesis$ and $C sub 1 ⁢ p prime equals c ⁢ C sub 1 ⁢ p$ . We get
$det (A^{'}) = \sum_{p = 1}^{n} a_{1 p}^{'} C_{1 p}^{'} = \sum_{p = 1}^{n} a_{1 p} c C_{1 p} = c \sum_{p = 1}^{n} a_{1 p} C_{1 p} = c det (A),$
which establishes $P ⁢ open parenthesis k plus 1 close parenthesis$ to be true. Hence by induction, we have shown that the result holds in this case for $n greater than or equal to 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 10.4 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.

Exercises

In Exercises -, prove each assertion using the Principle of Mathematical Induction.

$\sum_{j = 1}^{n} j^{2} = \frac{n (n + 1) (2 n + 1)}{6}$
$\sum_{j = 1}^{n} j^{3} = \frac{n^{2} {(n + 1)}^{2}}{4}$
$2 to the power n greater than 500 ⁢ n$ for $n greater than 12$
$3 to the power n greater than or equal to n cubed$ for $n greater than or equal to 4$
Use the Product Rule for Absolute Value to show $| x^{n} | = {| x |}^{n}$ for all real numbers $x$ and all natural numbers $n greater than or equal to 1$
Use the Product Rule for Logarithms to show $\log (x^{n}) = n \log (x)$ for all real numbers $x greater than 0$ and all natural numbers $n greater than or equal to 1$ .
${[\begin{matrix} a & 0 \\ 0 & b \end{matrix}]}^{n} = [\begin{matrix} a^{n} & 0 \\ 0 & b^{n} \end{matrix}]$ for $n greater than or equal to 1$ .
Prove Equations 10.1 and 10.2 for the case of geometric sequences. That is:
1. For the sequence $a sub 1 equals a$ , $a_{n + 1} = r a_{n}$ , $n greater than or equal to 1$ , prove $a_{n} = a r^{n - 1}$ , $n greater than or equal to 1$ .
2. $\sum_{j = 1}^{n} a r^{j - 1} = a (\frac{1 - r^{n}}{1 - r})$ , if $r not equal to 1$ , $\sum_{j = 1}^{n} a r^{j - 1} = n a$ , if $r equals 1$ .
Prove that the determinant of a lower triangular matrix is the product of the entries on the main diagonal. (See Exercise in Section 9.3.) Use this result to then show $det open parenthesis I sub n close parenthesis equals 1$ where $I_{n}$ is the $n \times n$ identity matrix.
Prove the Power Rule for Limits (see Theorem 6.2 in Section ): $lim_{x \to a} {[f (x)]}^{n} = {[lim_{x \to a} f (x)]}^{n} = L^{n}$ , where $n$ is any natural number.
Discuss the classic `paradox' All Horses are the Same Color problem with your classmates.

Selected Answers

Let $P (n)$ be the sentence $\sum_{j = 1}^{n} j^{2} = \frac{n (n + 1) (2 n + 1)}{6}$ . For the base case, $n equals 1$ , we get
$\begin{matrix} \sum_{j = 1}^{1} j^{2} & \overset{?}{=} & \frac{(1) (1 + 1) (2 (1) + 1)}{6} \\ 1^{2} & = & 1 ✓ \end{matrix}$
We now assume $P (k)$ is true and use it to show $P ⁢ open parenthesis k plus 1 close parenthesis$ is true. We have
$\begin{matrix} \sum_{j = 1}^{k + 1} j^{2} & \overset{?}{=} & \frac{(k + 1) ((k + 1) + 1) (2 (k + 1) + 1)}{6} \\ \sum_{j = 1}^{k} j^{2} + {(k + 1)}^{2} & \overset{?}{=} & \frac{(k + 1) (k + 2) (2 k + 3)}{6} \\ \underset{Using P (k)}{\underset{⏟}{\frac{k (k + 1) (2 k + 1)}{6}}} + {(k + 1)}^{2} & \overset{?}{=} & \frac{(k + 1) (k + 2) (2 k + 3)}{6} \\ \frac{k (k + 1) (2 k + 1)}{6} + \frac{6 {(k + 1)}^{2}}{6} & \overset{?}{=} & \frac{(k + 1) (k + 2) (2 k + 3)}{6} \\ \frac{k (k + 1) (2 k + 1) + 6 {(k + 1)}^{2}}{6} & \overset{?}{=} & \frac{(k + 1) (k + 2) (2 k + 3)}{6} \\ \frac{(k + 1) (k (2 k + 1) + 6 (k + 1))}{6} & \overset{?}{=} & \frac{(k + 1) (k + 2) (2 k + 3)}{6} \\ \frac{(k + 1) (2 k^{2} + 7 k + 6)}{6} & \overset{?}{=} & \frac{(k + 1) (k + 2) (2 k + 3)}{6} \\ \frac{(k + 1) (k + 2) (2 k + 3)}{6} & = & \frac{(k + 1) (k + 2) (2 k + 3)}{6} ✓ \end{matrix}$
By induction, $\sum_{j = 1}^{n} j^{2} = \frac{n (n + 1) (2 n + 1)}{6}$ is true for all natural numbers $n greater than or equal to 1$ .
Let $P (n)$ be the sentence $3 to the power n greater than n cubed$ . Our base case is $n equals 4$ and we check $3^{4} = 81$ and $4 cubed equals 64$ so that $3 to the power 4 greater than 4 cubed$ as required. We now assume $P (k)$ is true, that is $3 to the power k greater than k cubed$ , and try to show $P ⁢ open parenthesis k plus 1 close parenthesis$ is true. We note that $3^{k + 1} = 3 \cdot 3^{k} > 3 k^{3}$ and so we are done if we can show $3 ⁢ k cubed greater than open parenthesis k plus 1 close parenthesis cubed$ for $k greater than or equal to 4$ . We can solve the inequality $3 ⁢ x cubed greater than open parenthesis x plus 1 close parenthesis cubed$ using the techniques of Section 4.1, and doing so gives us $x > \frac{1}{\sqrt[3]{3} - 1} \approx 2.26 .$ Hence, for $k greater than or equal to 4$ , $3^{k + 1} = 3 \cdot 3^{k} > 3 k^{3} > {(k + 1)}^{3}$ so that $3^{k + 1} > {(k + 1)}^{3}$ . By induction, $3 to the power n greater than n cubed$ is true for all natural numbers $n greater than or equal to 4$ .
Let $P (n)$ be the sentence $\log (x^{n}) = n \log (x)$ . For the duration of this argument, we assume $x greater than 0$ . The base case $P ⁢ open parenthesis 1 close parenthesis$ amounts checking that $\log (x^{1}) = 1 \log (x)$ which is clearly true. Next we assume $P (k)$ is true, that is $\log (x^{k}) = k \log (x)$ and try to show $P ⁢ open parenthesis k plus 1 close parenthesis$ is true. Using the Product Rule for Logarithms along with the induction hypothesis, we get
$\log (x^{k + 1}) = \log (x^{k} \cdot x) = \log (x^{k}) + \log (x) = k \log (x) + \log (x) = (k + 1) \log (x)$
Hence, $\log (x^{k + 1}) = (k + 1) \log (x)$ . By induction $\log (x^{n}) = n \log (x)$ is true for all $x greater than 0$ and all natural numbers $n greater than or equal to 1$ .
Let $A$ be an $n \times n$ lower triangular matrix. We proceed to prove the $det (A)$ is the product of the entries along the main diagonal by inducting on $n$ . For $n equals 1$ , $A = [a]$ and $det (A) = a$ , so the result is (trivially) true. Next suppose the result is true for $k \times k$ lower triangular matrices. Let $A$ be a $(k + 1) \times (k + 1)$ lower triangular matrix. Expanding $det (A)$ along the first row, we have
$det (A) = \sum_{p = 1}^{n} a_{1 p} C_{1 p}$
Since $a sub 1 ⁢ p equals 0$ for $2 less than or equal to p less than or equal to k plus 1$ , this simplifies $det open parenthesis A close parenthesis equals a sub 11 ⁢ C sub 11$ . By definition, we know that $C_{11} = {(- 1)}^{1 + 1} det (A_{11}) = det (A_{11})$ where $A sub 11$ is $k \times k$ matrix obtained by deleting the first row and first column of $A$ . Since $A$ is lower triangular, so is $A sub 11$ and, as such, the induction hypothesis applies to $A sub 11$ . In other words, $det open parenthesis A sub 11 close parenthesis$ is the product of the entries along $A sub 11$ 's main diagonal. Now, the entries on the main diagonal of $A sub 11$ are the entries $a sub 22$ , $a sub 33$ , …, $a_{(k + 1) (k + 1)}$ from the main diagonal of $A$ . Hence,
$det (A) = a_{11} det (A_{11}) = a_{11} (a_{22} a_{33} \dots a_{(k + 1) (k + 1)}) = a_{11} a_{22} a_{33} \dots a_{(k + 1) (k + 1)}$
We have $det (A)$ is the product of the entries along its main diagonal. This shows $P ⁢ open parenthesis k plus 1 close parenthesis$ is true, and, hence, by induction, the result holds for all $n \times n$ upper triangular matrices. The $n \times n$ identity matrix $I_{n}$ is a lower triangular matrix whose main diagonal consists of all $1$ 's. Hence, $det open parenthesis I sub n close parenthesis equals 1$ , as required.

Another word for this you may have seen is `axiom.' ↩
Falling dominoes is the most widely used metaphor in the mainstream College Algebra books. ↩
This is how Carl climbed the stairs in the Cologne Cathedral. Well, that, and encouragement from Kai. ↩
See Exercise in Section 2.4: $\bar{z} \bar{w} = \bar{z w}$ . ↩
See Section 9.5 for a review of this notation. ↩

Adapted from Precalculus, Preliminary 4th Edition (integrated calculus), by Carl Stitz and Jeff Zeager (stitz-zeager.com), licensed under CC BY-NC-SA 3.0. Changes were made: reformatted as an accessible XYZ web edition. License: CC-BY-NC-SA-3.0.