9.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 and by starting with just a single step. A good example is the formula for arithmetic sequences we touted in Equation. 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, which lead us to our formula $a_{n} = a + (n - 1) d$ for $n greater than or equal to 1$ . But how do we prove this to be the case? We have the following.

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. In English, it 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$ , it must be true for the next natural number, $k plus 1$ (the `inductive step'). The notation $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. The construction $P ⁢ open parenthesis k plus 1 close parenthesis$ would be ` ${(k + 1)}^{2} + 1 = 3$ '. As usual, this new concept is best illustrated with an example. Returning to our quest to prove the formula for an arithmetic sequence, we first identify $P (n)$ as the formula $a_{n} = a + (n - 1) d$ . To prove this formula is valid for all natural numbers $n$ , we need to do two things. First, we need to establish that $P ⁢ open parenthesis 1 close parenthesis$ is true. In other words, is it true that $a_{1} = a + (1 - 1) d$ ? The answer is yes, since this simplifies to $a sub 1 equals a$ , which is part of the definition of the arithmetic sequence. The second thing we need to show is that whenever $P (k)$ is true, it follows that $P ⁢ open parenthesis k plus 1 close parenthesis$ is true. In other words, we assume $P (k)$ is true (this is called the `induction hypothesis') and deduce that $P ⁢ open parenthesis k plus 1 close parenthesis$ is also true. Assuming $P (k)$ to be true seems to invite disaster - after all, isn't this essentially what we're trying to prove in the first place? To help explain this step a little better, we show how this works for specific values of $n$ . We've already established $P ⁢ open parenthesis 1 close parenthesis$ is true, and we now want to show that $P ⁢ open parenthesis 2 close parenthesis$ is true. Thus we need to show that $a_{2} = a + (2 - 1) d$ . Since $P ⁢ open parenthesis 1 close parenthesis$ is true, we have $a sub 1 equals a$ , and by the definition of an arithmetic sequence, $a_{2} = a_{1} + d = a + d = a + (2 - 1) d$ . So $P ⁢ open parenthesis 2 close parenthesis$ is true. We now use the fact that $P ⁢ open parenthesis 2 close parenthesis$ is true to show that $P ⁢ open parenthesis 3 close parenthesis$ is true. Using the fact that $a_{2} = a + (2 - 1) d$ , we show $a_{3} = a + (3 - 1) d$ . Since $a_{3} = a_{2} + d$ , we get $a_{3} = (a + (2 - 1) d) + d = a + 2 d = a + (3 - 1) d$ , so we have shown $P ⁢ open parenthesis 3 close parenthesis$ is true. Similarly, we can use the fact that $P ⁢ open parenthesis 3 close parenthesis$ is true to show that $P ⁢ open parenthesis 4 close parenthesis$ is true, and so forth. In general, if $P (k)$ is true (i.e., $a_{k} = a + (k - 1) d$ ) we set out to show that $P ⁢ open parenthesis k plus 1 close parenthesis$ is true (i.e., $a_{k + 1} = a + ((k + 1) - 1) d$ ). Assuming $a_{k} = a + (k - 1) d$ , we have by the definition of an arithmetic sequence that $a_{k + 1} = a_{k} + d$ so we get $a_{k + 1} = (a + (k - 1) d) + d = a + k d = a + ((k + 1) - 1) d$ . Hence, $P ⁢ open parenthesis k plus 1 close parenthesis$ is true.

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. Thus as long as $P (k)$ is true for some natural number $k$ , $P (n)$ is true for all of the natural numbers $n$ which follow $k$ . Coupling this with the fact $P ⁢ open parenthesis 1 close parenthesis$ is true, we have established $P (k)$ is true for all natural numbers which follow $n equals 1$ , in other words, 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.

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$ .
$3 to the power n greater than 100 ⁢ n$ for $n greater than 5$ .
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. For $n equals 1$ , we compare both sides of the equation given in $P (n)$
$\begin{matrix} \sum_{j = 1}^{1} (a + (j - 1) d) & \overset{?}{=} & \frac{1}{2} (2 a + (1 - 1) d) \\ a + (1 - 1) d & \overset{?}{=} & \frac{1}{2} (2 a) \\ a & = & a ✓ \end{matrix}$
This shows the base case $P ⁢ open parenthesis 1 close parenthesis$ 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 attempt to use this to show $P ⁢ open parenthesis k plus 1 close parenthesis$ is true. Namely, we must show
$\sum_{j = 1}^{k + 1} (a + (j - 1) d) = \frac{k + 1}{2} (2 a + (k + 1 - 1) d)$
To see how we can use $P (k)$ in this case to prove $P ⁢ open parenthesis k plus 1 close parenthesis$ , we note that the sum in $P ⁢ open parenthesis k plus 1 close parenthesis$ is the sum of the first $k plus 1$ terms of the sequence $a_{k} = a + (k - 1) d$ for $k greater than or equal to 1$ while the sum in $P (k)$ is the sum of the first $k$ terms. We compare both side of the equation in $P ⁢ open parenthesis k plus 1 close parenthesis$ .
$\begin{matrix} \underset{summing the first k + 1 terms}{\underset{⏟}{\sum_{j = 1}^{k + 1} (a + (j - 1) d)}} & \overset{?}{=} & \frac{k + 1}{2} (2 a + (k + 1 - 1) d) \\ \underset{summing the first k terms}{\underset{⏟}{\sum_{j = 1}^{k} (a + (j - 1) d)}} + \underset{adding the (k + 1)st term}{\underset{⏟}{(a + (k + 1 - 1) d)}} & \overset{?}{=} & \frac{k + 1}{2} (2 a + k d) \\ \underset{Using P (k)}{\underset{⏟}{\frac{k}{2} (2 a + (k - 1) d)}} + (a + k d) & \overset{?}{=} & \frac{(k + 1) (2 a + k d)}{2} \\ \frac{k (2 a + (k - 1) d) + 2 (a + k d)}{2} & \overset{?}{=} & \frac{2 k a + k^{2} d + 2 a + k d}{2} \\ \frac{2 k a + 2 a + k^{2} d + k d}{2} & = & \frac{2 k a + 2 a + k^{2} d + k d}{2} ✓ \end{matrix}$
Since all of our steps on both sides of the string of equations are reversible, we conclude that the two sides of the equation are equivalent and hence, $P ⁢ open parenthesis k plus 1 close parenthesis$ is true. By the Principle of Mathematical Induction, we have that $P (n)$ is true for all natural numbers $n$ .
We let $P (n)$ be the formula ${(\bar{z})}^{n} = \bar{z^{n}}$ . The base case $P ⁢ open parenthesis 1 close parenthesis$ is ${(\bar{z})}^{1} = \bar{z^{1}}$ , which 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 attempt to show that $P ⁢ open parenthesis k plus 1 close parenthesis$ is true. Since ${(\bar{z})}^{k + 1} = {(\bar{z})}^{k} \bar{z}$ , we can use the induction hypothesis and write ${(\bar{z})}^{k} = \bar{z^{k}}$ . Hence, ${(\bar{z})}^{k + 1} = {(\bar{z})}^{k} \bar{z} = \bar{z^{k}} \bar{z}$ . We now use the product rule for conjugates⁴ to write $\bar{z^{k}} \bar{z} = \bar{z^{k} z} = \bar{z^{k + 1}}$ . This establishes ${(\bar{z})}^{k + 1} = \bar{z^{k + 1}}$ , so that $P ⁢ open parenthesis k plus 1 close parenthesis$ is true. Hence, by the Principle of Mathematical Induction, ${(\bar{z})}^{n} = \bar{z^{n}}$ for all $n greater than or equal to 1$ .
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$ . We are done if we can 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$ .
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)$ as required. 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 whether or not 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 to the power ′$ 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_{1 p}^{'} = c a_{1 p}$ . In addition, since the remaining rows of $A^{'}$ are identical to those of $A$ , $A_{1 p}^{'} = A_{1 p}$ . (To obtain these matrices, the first row of $A^{'}$ is removed.) Hence $det (A_{1 p}^{'}) = det (A_{1 p})$ , so that $C_{1 p}^{'} = C_{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, and we stand by our approach because of its pedagogical value.)
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_{1 p}^{'} = a_{1 p}$ , since the first rows of $A$ and $A^{'}$ are the same. The matrices $A sub 1 ⁢ p to the power ′$ and $A sub 1 ⁢ p$ , on the other hand, are different but in a very predictable way the row in $A sub 1 ⁢ p to the power ′$ 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$ . In other words, $A sub 1 ⁢ p to the power ′$ and $A sub 1 ⁢ p$ are $k \times k$ matrices which satisfy the induction hypothesis. Hence, we know $det (A_{1 p}^{'}) = c det (A_{1 p})$ and $C_{1 p}^{'} = c C_{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 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 and 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^{n - 1} = a (\frac{1 - r^{n}}{1 - r})$ , if $r not equal to 1$ , $\sum_{j = 1}^{n} a r^{n - 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.) 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.
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, 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.

Adapted from Precalculus, 3rd corrected edition, 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.