14.5: Mathematical Induction

From LibreTexts, under CC BY-NC-SA 3.0, as the source states it; its equations are written in TeX, which the PDF shows typeset. This page at LibreTexts.

Section Preview

Note to the Instructor (click to expand): Mathematical Induction is the first dedicated proof section in Algebra that the students are likely to have seen. This is a foundational moment—and one not to be shrugged off. Spend a good amount of time discussing proof styles and why we start with learning proofs by Mathematical Induction (it's because it's the most algorithmic of the proof styles). Also, make sure students understand that most proofs cannot be done using this niche technique.

(click to expand)

Sets and Numbers
- The Language of Algebra

The following is a list of learning objectives for this section.

Learning Objectives (click to expand)

Use the Principle of Mathematical Induction to prove algebraic identities.

The Chinese philosopher Laozi 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 previous sections. A good example is the formula for arithmetic sequences.

As mentioned previously, arithmetic sequences can be 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 go from one term to the next by successively adding $d$. In symbols,\[a, a+d, a+2d, a + 3d, a + 4d, \ldots\nonumber\]The pattern suggested here is that to reach the $n^{\text{th}}$ term, we start with $a$ and add $d$ to it exactly $n-1$ times, which leads us to our formula $a_{n} = a + (n-1)d$ for $n \geq 1$. But how do we prove this to be the case?

The Principle of Mathematical Induction (PMI)

The Principle of Mathematical Induction, or PMI for short, is exactly that—a principle (also known as an axiom). 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 a formula works for all natural numbers $n$, we start by showing it is true for $n=1$ (the "base case") and then show that if it is true for an arbitrary natural number $k$, it must be true for the next natural number, $k+1$ (the "inductive step").

The notation $P(n)$ acts just like function notation. For example, if $P(n)$ is the claim that "$n^2 + 1 = 3$," then $P(1)$ would be "$1^2 + 1 = 3$," which is false. The construction $P(k+1)$ 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 claim $a_{n} = a + (n-1)d$. We need to do two things to prove this claim is true for all natural numbers $n$. First, we need to establish that $P(1)$ is true. In other words, is it true that $a_{1} = a + (1-1)d$? The answer is yes since this simplifies to $a_{1} = 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(k+1)$ is true. In other words, we assume $P(k)$ is true (this is called the "induction hypothesis") and deduce (through logical arguments) that $P(k+1)$ 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 better, we show how this works for specific values of $n$. We've already established that $P(1)$ is true, and we now want to show that $P(2)$ is true. Thus, we need to show that $a_{2} = a + (2-1)d$. Since $P(1)$ is true, we have $a_{1} = a$, and by the definition of an arithmetic sequence, $a_{2}= a_{1} + d = a + d = a + (2-1)d$. So $P(2)$ is true.

We now use the fact that $P(2)$ is true to show that $P(3)$ 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 + 2d = a+(3-1)d$, so we have shown $P(3)$ is true. Similarly, we can use the fact that $P(3)$ is true to show that $P(4)$ 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(k+1)$ 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(k+1)$ is true.

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. 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 that $P(1)$ is true, we have established $P(k)$ is true for all natural numbers that follow $n=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 (or falling dominoes, which is the most widely used metaphor in mainstream College Algebra books). We get some more practice with induction in the following example.

Example $\PageIndex{1}$: Proving a Summation Formula

Prove the following, where $n \in \mathbb{N}$.\[\sum_{j=1}^{n} (a + (j-1)d) = \dfrac{n}{2}(2a + (n-1)d) \nonumber\]

Solution: We set $P(n)$ to be the equation we are asked to prove. For $n=1$, we compare both sides of the equation given in $P(n)$:\[\begin{array}{rcl} \displaystyle{\sum_{j=1}^{1} (a + (j-1)d)} & \stackrel{\text{?}}{=} & \dfrac{1}{2}(2a + (1-1)d) \\[6pt] a + (1-1) d & \stackrel{\text{?}}{=} & \dfrac{1}{2} (2a) \\[6pt] a & = & a \, \checkmark \\[6pt] \end{array}\nonumber\]This shows the base case $P(1)$ is true. Next we assume $P(k)$ is true, that is, we assume\[\displaystyle{\sum_{j=1}^{k} (a + (j-1)d) = \dfrac{k}{2}(2a + (k-1)d)}\nonumber\]and attempt to use this to show $P(k+1)$ is true. Namely, we must show\[\displaystyle{\sum_{j=1}^{k+1} (a + (j-1)d) = \dfrac{k+1}{2}(2a + (k+1-1)d)}.\nonumber\]To see how we can use $P(k)$ in this case to prove $P(k+1)$, we note that the sum in $P(k+1)$ is the sum of the first $k+1$ terms of the sequence $a_{k} = a + (k-1)d$ for $k \geq 1$ while the sum in $P(k)$ is the sum of the first $k$ terms. We compare both sides of the equation in $P(k+1)$.\[\begin{array}{rcl} \underbrace{\displaystyle{\sum_{j=1}^{k+1} (a + (j-1)d)}}_{\text{summing the first $k+1$ terms}} & \stackrel{\text{?}}{=} & \dfrac{k+1}{2}(2a + (k+1- 1)d) \\[6pt] \underbrace{\displaystyle{\sum_{j=1}^{k} (a + (j-1)d)}}_{\text{summing the first $k$ terms}} + \underbrace{\vphantom{\displaystyle{\sum_{j=1}^{k +1}}}(a+(k+1-1)d)}_{\text{adding the ($k+1$)st term}} & \stackrel{\text{?}}{=} & \dfrac{k+1}{2}(2a + kd) \\[6pt] \underbrace{\dfrac{k}{2}(2a + (k-1)d)}_{\text{Using $P(k)$}} + (a + kd) & \stackrel{\text{?}}{=} & \dfrac{(k+1)(2a+kd)}{2} \\[6pt] \dfrac{k(2a+(k-1)d) + 2(a + kd)}{2} & \stackrel{\text{?}}{=} & \dfrac{2ka+k^2d + 2a + kd}{2} \\[6pt] \dfrac{2ka + 2a + k^2d + kd}{2} & = & \dfrac{2ka + 2a + k^2d + kd}{2} \, \checkmark \\[6pt] \end{array}\nonumber\]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(k+1)$ is true. By the Principle of Mathematical Induction, we have that $P(n)$ is true for all natural numbers $n$.

Caution: Unknown Equality

Pay close attention to the fact that we used the symbol $\stackrel{\text{?}}{=}$, called an unknown equality, when comparing both sides of the equations in Example $\PageIndex{1}$ for $P(1)$ and $P(k + 1)$. This symbol means that we are not certain if those two sides are actually equal. As such, we cannot treat it like an equality. That is, we are not allowed to add, subtract, multiply, or divide between sides (as you can only do that if you have an equality or inequality). In fact, we cannot perform any operations between sides!

To be clear, it would be mathematically illegal to do the following when comparing both sides of $P(n)$ for $n = 1$:\[\begin{array}{rcl} \displaystyle{\sum_{j=1}^{1} (a + (j-1)d)} & \stackrel{\text{?}}{=} & \dfrac{1}{2}(2a + (1-1)d) \\[6pt] a + (1-1) d & \stackrel{\text{?}}{=} & \dfrac{1}{2} (2a) \\[6pt] a & \stackrel{\text{?}}{=} & \dfrac{1}{2} (2a) \\[6pt] \textcolor{red}{0} & \stackrel{\text{?}}{=} & \dfrac{1}{2} (2a) - \textcolor{red}{a} \quad \left( \text{subtracting }a\text{ from both sides} \right)\\[6pt] 0 & \stackrel{\text{?}}{=} & a - a \\[6pt] 0 & = & 0 \, \checkmark \\[6pt] \end{array}\nonumber\]Once you have performed an operation between the two sides of the $\stackrel{\text{?}}{=}$ symbol, you have assumed that the equation is already true.

Example $\PageIndex{2}$: Proving an Algebraic Claim

Prove that, for a complex number $z$, $\left( \overline{z} \right)^n = \overline{z^{n}}$, where $n \ge 1$ and $n \in \mathbb{N}$.

Solution

Let $P(n)$ be the formula $\left(\overline{z}\right)^n = \overline{z^{n}}$.

For $n = 1$, we have $\left(\overline{z}\right)^1 = \overline{z} = \overline{z^1}$. Thus, $P(1)$ is true.

Induction Hypothesis: Assume $P(k)$ is true. That is, assume $\left(\overline{z}\right)^k = \overline{z^{k}}$.

To show $P(k + 1)$ is true, we need to show that $\left(\overline{z}\right)^{k + 1} = \overline{z^{k + 1}}$.\[\begin{array}{rclr} \left(\overline{z}\right)^{k+1} & = & \left(\overline{z}\right)^{k} \, \overline{z} & \\[6pt] & = & \overline{z^k} \, \overline{z} & \left( \text{Induction Hypothesis} \right) \\[6pt] & = & \overline{z^k z} & \left( \text{Product Rule for Conjugates} \right) \\[6pt] & = & \overline{z^{k+1}} & \\[6pt] \end{array} \nonumber\]This establishes $\left(\overline{z}\right)^{k+1} = \overline{z^{k+1}}$, so that $P(k+1)$ is true. Hence, by the Principle of Mathematical Induction, $\left(\overline{z}\right)^n = \overline{z^{n}}$ for all $n \geq 1$.

Example $\PageIndex{3}$: Proving a Summation Formula

Prove that $1^3 + 2^3 + 3^3 + \cdots + n^3 = \frac{n^2 (n + 1)^2}{4}$, where $n \in \mathbb{N}$.

Solution

Let $P(n)$ be the formula $1^3 + 2^3 + 3^3 + \cdots + n^3 = \frac{n^2 (n + 1)^2}{4}$.

For $n = 1$, we have $1^3 = \frac{1^2 (1 + 1)^2}{4}$. Thus, $P(1)$ is true.

Induction Hypothesis: Assume $P(k)$ is true. That is, assume $1^3 + 2^3 + 3^3 + \cdots + k^3 = \frac{k^2 (k + 1)^2}{4}$.

To show $P(k + 1)$ is true, we need to show that $1^3 + 2^3 + 3^3 + \cdots + k^3 + (k + 1)^3 = \frac{(k + 1)^2 (k + 1 + 1)^2}{4} = \frac{(k + 1)^2(k + 2)^2}{4}$.\[\begin{array}{rclr} 1^3 + 2^3 + 3^3 + \ldots + k^3 + (k + 1)^3 & = & \left( 1^3 + 2^3 + 3^3 + \ldots + k^3 \right) + (k + 1)^3 & \\[6pt] & = & \dfrac{k^2 (k + 1)^2}{4} + (k + 1)^3 & \left( \text{Induction Hypothesis} \right) \\[6pt] & = & \dfrac{k^2 (k + 1)^2 + 4(k + 1)^3}{4} & \\[6pt] & = & \dfrac{(k + 1)^2 \left(k^2 + 4 (k + 1) \right)}{4} & \\[6pt] & = & \dfrac{(k + 1)^2 \left(k^2 + 4 k + 4 \right)}{4} & \\[6pt] & = & \dfrac{(k + 1)^2 (k + 2)^2}{4} & \\[6pt] \end{array} \nonumber\]Therefore, $1^3 + 2^3 + 3^3 + \cdots + k^3 + (k + 1)^3 = \frac{(k + 1)^2 (k + 1 + 1)^2}{4} = \frac{(k + 1)^2(k + 2)^2}{4}$, and so $P(k+1)$ is true. Hence, by the Principle of Mathematical Induction, $1^3 + 2^3 + 3^3 + \cdots + n^3 = \frac{n^2 (n + 1)^2}{4}$ for all natural numbers $n$.

Advice

Notice in the Induction Hypothesis step of Example $\PageIndex{3}$ that we clearly stated, "Assume $P(k)$ is true. That is, assume $1^3 + 2^3 + 3^3 + \cdots + k^3 = \frac{k^2 (k + 1)^2}{4}$." This statement is intentional. It tells us that, from this point forward, whenever we see $1^3 + 2^3 + 3^3 + \cdots + k^3$, we can replace it with $\frac{k^2 (k + 1)^2}{4}$. This replacement always happens in the next step of the proof.

Additionally, when starting our work on $P(k + 1)$, we clearly stated that, "we need to show that $1^3 + 2^3 + 3^3 + \cdots + k^3 + (k + 1)^3 = \frac{(k + 1)^2 (k + 1 + 1)^2}{4} = \frac{(k + 1)^2(k + 2)^2}{4}$." Clearly stating what we need to show, and simplifying that down to $\frac{(k + 1)^2(k + 2)^2}{4}$, provides us with a goal—we need to manipulate $P(k + 1)$ (using the Induction Hypothesis) to eventually become $\frac{(k + 1)^2(k + 2)^2}{4}$.

Example $\PageIndex{4}$: Proving an Inequality Claim

Prove that $3^{n} \gt 100n$ for $n \gt 5$, where $n \in \mathbb{N}$.

Solution

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, our base step occurs at $n=6$. We can still use the PMI in this case, but we will conclude that the formula is valid for all $n \geq 6$.

Let $P(n)$ be the inequality $3^{n} > 100n$.

For $n = 6$, we have $3^6 = 729 \gt 600 = 100(6)$. Thus, $P(6)$ is true.

Induction Hypothesis: Assume $P(k)$ is true. That is, assume $3^{k} > 100k$.

To show $P(k + 1)$ is true, we need to show $3^{k+1} \gt 100(k+1) = 100k + 100$.\[\begin{array}{rclr} 3^{k + 1} & = & 3^k \cdot 3 & \\[6pt] & \gt & 100k \cdot 3 & \left( \text{Induction Hypothesis} \right) \\[6pt] & = & 100k + 200 k & \left( \text{our goal is to get to }100k + 100\text{, so isolating }100k\text{ is helpful} \right) \\[6pt] & \gt & 100k + 100 & \left( 200k \gt 100 \text{ when } k \gt \frac{1}{2}\text{. Since }k \ge 6\text{, }200k \gt 100 \right) \\[6pt] \end{array} \nonumber\]Hence $P(k+1)$ is true. By induction, $3^{n} > 100n$ for all $n \geq 6$.

Example $\PageIndex{4}$ showcases a challenge when working with inequalities and Mathematical Induction—you need to be very creative and truly understand your prerequisite mathematics to do well with these types of induction proofs. Read through Example $\PageIndex{4}$ a few times to truly understand what we did.

Example $\PageIndex{5}$: Proving a Divisibility Claim

Prove $n^2 + n$ is divisible by $2$, where $n \in \mathbb{N}$.

Solution

Let $P(n)$ be the statement that $n^2 + n$ is divisible by $2$.

For $n = 1$, we have $1^2 + 1 = 2$. This is definitely divisible by $2$ (since $\frac{2}{2} = 1$), so $P(1)$ is true.

Induction Hypothesis: Assume $P(k)$ is true. That is, assume $k^2 + k$ is divisible by $2$.

To show $P(k + 1)$ is true, we need to show that $(k + 1)^2 + (k + 1)$ is divisible by $2$.\[\begin{array}{rclr} (k + 1)^2 + (k + 1) & = & k^2 + 2k + 1 + k + 1 & \\[6pt] & = & (k^2 + k) + 2k + 1 + 1 & \left( \text{Associative and Commutative Properties of Addition} \right) \\[6pt] & = & (k^2 + k) + 2k + 2 & \\[6pt] & = & (k^2 + k) + 2(k + 1) & \\[6pt] \end{array} \nonumber\]We know that $k^2 + k$ is divisible by $2$, by the Induction Hypothesis. We also know that $2(k + 1)$ is divisible by $2$. The sum of numbers divisible by $2$ is also divisible by $2$, so $(k + 1)^2 + (k + 1)$ must be divisible by $2$. Hence, $P(k + 1)$ is true. Thus, the claim is true for all natural numbers $n$ by Mathematical Induction.

While we have used the Principle of Mathematical Induction to prove some of the formulas we have merely motivated in the text, our primary use of this result is to prove the celebrated Binomial Theorem. The ardent Mathematics student will undoubtedly see the PMI in many courses that have yet to be taught. Sometimes, it is explicitly stated, and sometimes, it remains hidden in the background. If ever you see a property expressed as being true "for all natural numbers $n$," it's a solid bet that the formal proof requires the Principle of Mathematical Induction.

Success in College: Learning From Tests (Part 4)

Tests and quizzes have two purposes. First, they assess your performance. Your test scores are part of a professor's information to assign you a grade for the course. Tests also allow you to see what you do not know. It is your responsibility to use tests to improve your skills and knowledge.

Often, a passing score on a test is 70%. However, the missing 30% is still critically important. When preparing for the next test, you must study your mistakes from the last test. Perhaps you will realize that you still do not understand an important concept. This concept will not disappear. Now is the time to get extra help. When it reappears, you will be ready. Perhaps you will realize that you are making many careless mistakes. Now is the time to plan strategies for checking your work on the next test. Perhaps you will realize that you made most of your mistakes on the last few questions of the exam. Now is the time to ponder how to pace yourself as you work on a test.

Learning from tests takes self-discipline. It is tempting to throw the test away or hide it in a folder. It is your responsibility to review your tests critically. Your ability to do well in the future depends on it.

Describe what you usually do with a returned math test.
Does what you do with a returned math test depend on whether you earned a good or poor grade on the test? Explain.

Success in College: Groupwork Learning Preferences

Most students are very intimidated by working in groups. It usually takes quite a while for students to realize that studying together can be very rewarding.

Think about the following questions regarding learning or practicing complicated math.

Do you prefer to do homework by yourself, or do you like to do homework with others?
Do you like to do homework at school, or do you like to do homework at home?
If you need help, do you prefer to get it from friends or a spouse, or do you prefer to get it from your professor or a tutor?
Do you concentrate on learning what you don't know by yourself, or do you prefer to help others because it helps you learn it better?

Do you work in conditions that match these preferences when you do your math homework? Why or why not?
Spending time with old and new friends is an integral part of college. However, studying with friends is not always practical. Do you ever feel peer pressure to study in ways that are not the best for you?

This page titled 14.5: Mathematical Induction was last modified on Tue, 08 Jul 2025 17:47:56 GMT and is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Roy Simpson, Cosumnes River College via source content that was edited to the style and standards of the LibreTexts platform.

Contents

Text

Section Preview

The Principle of Mathematical Induction (PMI)

Example \(\PageIndex{1}\): Proving a Summation Formula

Caution: Unknown Equality

Example \(\PageIndex{2}\): Proving an Algebraic Claim

Example \(\PageIndex{3}\): Proving a Summation Formula

Advice

Example \(\PageIndex{4}\): Proving an Inequality Claim

Example \(\PageIndex{5}\): Proving a Divisibility Claim

Success in College: Learning From Tests (Part 4)

Success in College: Groupwork Learning Preferences