3.6: Mathematical Induction - An Introduction

Last updated
Save as PDF

Page ID: 24565

$kwong.jpg$
Harris Kwong
Professors (Mathematics) at State University of New York at Fredonia
Publisher: OpenSUNY

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

Mathematical induction can be used to prove that an identity is valid for all integers $n\geq1$. Here is a typical example of such an identity: \[1+2+3+\cdots+n = \frac{n(n+1)}{2}.\] More generally, we can use mathematical induction to prove that a propositional function $P(n)$ is true for all integers $n\geq a$.

Principal of Mathematical Induction (PMI)

Given a propositional function $P(n)$ defined for integers $n$, and a fixed integer $a.$

Then, if these two conditions are true

$P(a)$ is true.
if $P(k)$ is true for some integer $k\geq a$, then $P(k+1)$ is also true.

then the $P(n)$ is true for all integers $n\geq a$.

Outline for Mathematical Induction

To show that a propositional function $P(n)$ is true for all integers $n\geq a$, follow these steps:

Base Step: Verify that $P(a)$ is true.
Inductive Step: Show that if $P(k)$ is true for some integer $k\geq a$, then $P(k+1)$ is also true.
- Assume $P(n)$ is true for an arbitrary integer, $k$ with $k\geq a$. This is the inductive hypothesis.
- With this assumption (the inductive hypothesis), show $P(k+1)$ is true.
Conclude, by the Principle of Mathematical Induction (PMI) that $P(n)$ is true for all integers $n\geq a$.

The base step is also called the basis step or the anchor step or the initial step.

The base step and the inductive step, together, prove that \[P(a) \Rightarrow P(a+1) \Rightarrow P(a+2) \Rightarrow \cdots\,.\] Therefore, $P(n)$ is true for all integers $n\geq a$. Compare induction to falling dominoes. When the first domino falls, it knocks down the next domino. The second domino in turn knocks down the third domino. Eventually, all the dominoes will be knocked down. But it will not happen unless these conditions are met:

The first domino must fall to start the motion. If it does not fall, no chain reaction will occur. This is the base step.
The distance between adjacent dominoes must be set up correctly. Otherwise, a certain domino may fall down without knocking over the next. Then the chain reaction will stop, and will never be completed. Maintaining the right inter-domino distance ensures that $P(k)\Rightarrow P(k+1)$ for each integer $k\geq a$.

To prove the implication \[P(k) \Rightarrow P(k+1)\] in the inductive step, we need to carry out two steps: assuming that $P(k)$ is true, then using it to prove $P(k+1)$ is also true. So we can refine an induction proof into a 3-step procedure:

Verify that $P(a)$ is true.
Assume that $P(k)$ is true for some integer $k\geq a$.
Show that $P(k+1)$ is also true.

The second step, the assumption that $P(k)$ is true, is referred to as the inductive hypothesis. This is how a mathematical induction proof may look:

The idea behind mathematical induction is rather simple. However, it must be delivered with precision.

Be sure to say “Assume $P(n)$ holds for some integer $k\geq a$.” Do not say “Assume it holds for all integers $k\geq a$.” If we already know the result holds for all $k\geq a$, then there is no need to prove anything at all.
Be sure to specify the requirement $k\geq a$. This ensures that the chain reaction of the falling dominoes starts with the first one.
Do not say “let $n=k$” or “let $n=k+1$.” The point is, you are not assigning the value of $k$ and $k+1$ to $n$. Rather, you are assuming that the statement is true when $n$ equals $k$, and using it to show that the statement also holds when $n$ equals $k+1$.

Some proofs by induction

$1+2+3+\cdots+n$

Example $\PageIndex{1}\label{eg:induct1-01}$

Use mathematical induction to show proposition $P(n)$: \[1+2+3+\cdots+n = \frac{n(n+1)}{2}\] for all integers $n\geq1$.

Proof

Base Step: consider n = 1

On the Left-Hand Side (LHS) we get 1. On the Right-Hand Side ( RHS) we get $\frac{1(1+1)}{2}=\frac{2}{2}=1.$ Thus $P(n)$ is true for $n =1.$

Inductive step: Assume $P(n)$ is true for $n =k, k \geq 1.$ In other words, $P(k)$ is true so our inductive hypothesis is \[1+2+3+\cdots+k = \frac{k(k+1)}{2}.\]

Consider the left-hand side of $P(k+1)$. \[1+2+3+\cdots+(k+1) = 1+2+\cdots+k+(k+1),\]

we can regroup this as

\[1+2+3+\cdots+(k+1) = [1+2+\cdots+k]+(k+1),\]

so that $1+2+\cdots+k$ can be replaced by $\frac{k(k+1)}{2}$, by the inductive hypothesis.

Using the inductive hypothesis, we find

\[\begin{aligned} 1+2+3+\cdots+(k+1) &=& 1+2+3+\cdots+k+(k+1) \\ &=& \frac{k(k+1)}{2}+(k+1) \\ &=& (k+1)\left(\frac{k}{2}+1\right) \\ &=& (k+1)\cdot\frac{k+2}{2}\\ &=& \frac{(k+1)(k+2)}{2}. \end{aligned}\]

Therefore, the identity also holds when $n=k+1$.

Thus, by the Principle of Mathematical Induction (PMI), \[1+2+3+\cdots+n = \frac{n(n+1)}{2}\] for all integers $n\geq1$.

We can use the summation notation (also called the sigma notation) to abbreviate a sum. For example, the sum in the last example can be written as

\[\sum_{i=1}^n i.\]

The letter $i$ is the index of summation. By putting $i=1$ under $\sum$ and $n$ above, we declare that the sum starts with $i=1$, and ranges through $i=2$, $i=3$, and so on, until $i=n$. The quantity that follows $\sum$ describes the pattern of the terms that we are adding in the summation. Accordingly,

\[\sum_{i=1}^{10} i^2 = 1^2+2^2+3^2+\cdots+10^2.\]

In general, the sum of the first $n$ terms in a sequence $\{a_1,a_2,a_3,\ldots\,\}$ is denoted $\sum_{i=1}^n a_i$. Observe that

\[\sum_{i=1}^{k+1} a_i = \left(\sum_{i=1}^k a_i\right) + a_{k+1},\]

which provides the link between $P(k+1)$ and $P(k)$ in an induction proof.

$\sum_{i=1}^n i^2$

Example $\PageIndex{2}$

Use mathematical induction to show that, for all integers $n\geq1$, \[\sum_{i=1}^n i^2 = 1^2+2^2+3^2+\cdots+n^2 = \frac{n(n+1)(2n+1)}{6}.\]

Proof: Base Step: When $n=1$, the left-hand side reduces to $1^2=1$, and the right-hand side becomes $\frac{1\cdot2\cdot3}{6}=1$; hence, the identity holds when $n=1$.
Inductive Step: Assume it holds when $n=k$ for some integer $k\geq1$; that is, assume for some integer $k\geq1$ that \[\sum_{i=1}^k i^2 = \frac{k(k+1)(2k+1)}{6}\] .
Consider $n=k+1$. \[\sum_{i=1}^{k+1} i^2 =1^2+2^2+3^2+\cdots+k^2+(k+1)^2. \] From the inductive hypothesis, we find \[\sum_{i=1}^{k+1} i^2 = \sum_{i=1}^k i^2 + (k+1)^2\]
\[=\frac{k(k+1)(2k+1)}{6}+(k+1)^2\]
\[=\frac{k(k+1)(2k+1)+6(k+1)^2}{6}\]
\[\frac{(k+1)[k(2k+1)+6(k+1)]}{6}\]
\[\frac{(k+1)(2k^2+7k+6)}{6}\]
\[\frac{(k+1)(k+2)(2k+3)}{6}\]
\[\frac{(k+1)(k+2)(2(k+1)+1)}{6}.\] Therefore, the identity also holds when $n=k+1$.
Thus, by PMI for all integers $n\geq1$, \[\sum_{i=1}^n i^2 = 1^2+2^2+3^2+\cdots+n^2 = \frac{n(n+1)(2n+1)}{6}.\]

hands-on exercise $\PageIndex{1}\label{he:induct1-01}$

It is time for you to write your own induction proof. Prove that \[1\cdot2 + 2\cdot3 + 3\cdot4 + \cdots + n(n+1) = \frac{n(n+1)(n+2)}{3}\] for all integers $n\geq1$.

hands-on exercise $\PageIndex{2}\label{he:induct1-02}$

Use induction to prove that, for all positive integers $n$, \[1\cdot2\cdot3 + 2\cdot3\cdot4 + \cdots + n(n+1)(n+2) = \frac{n(n+1)(n+2)(n+3)}{4}.\]

hands-on exercise $\PageIndex{3}\label{he:sumfourn}$

Use induction to prove that, for all positive integers $n$, \[1+4^1+4^2+\cdots+4^n = \frac{4^{n+1}-1}{3}.\]

All three steps in an induction proof must be completed; otherwise, the proof may not be correct.

Example $\PageIndex{3}\label{eg:induct1-03}$

Can we just use examples?

Never attempt to prove $P(k)\Rightarrow P(k+1)$ by examples alone. Consider \[P(n): \qquad n^2+n+11 \mbox{ is prime}.\] In the inductive step, we want to prove that \[P(k) \Rightarrow P(k+1) \qquad\mbox{ for ANY } k\geq1.\] The following table verifies that it is true for $1\leq k\leq 9$: \[\begin{array}{|*{10}{c|}} \hline n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline n^2+n+11 & 13 & 17 & 23 & 31 & 41 & 53 & 67 & 83 & 101 \\ \hline \end{array}\] Nonetheless, when $n=10$, $n^2+n+11=121$ is composite. So $P(9) \Rightarrow P(10)$ is false. The inductive step breaks down when $k=9$.

Example $\PageIndex{4}\label{eg:induct1-04}$

The base step is equally important. Consider proving \[P(n): \qquad 3n+2 = 3q \mbox{ for some integer $q$}\] for all $n\in\mathbb{N}$. Assume $P(k)$ is true for some integer $k\geq1$; that is, assume $3k+2=3q$ for some integer $q$. Then \[3(k+1)+2 = 3k+3+2 = 3+3q = 3(1+q).\] Therefore, $3(k+1)+2$ can be written in the same form. This proves that $P(k+1)$ is also true. Does it follow that $P(n)$ is true for all integers $n\geq1$? We know that $3n+2$ cannot be written as a multiple of 3. What is the problem?

Solution: The problem is: we need $P(k)$ to be true for at least one value of $k$ so as to start the sequence of implications \[P(1) \Rightarrow P(2), \qquad P(2) \Rightarrow P(3), \qquad P(3) \Rightarrow P(4), \qquad\ldots\] The induction fails because we have not established the basis step. In fact, $P(1)$ is false. Since the first domino does not fall, we cannot even start the chain reaction.

Remark

Thus far, we have learned how to use mathematical induction to prove identities. In general, we can use mathematical induction to prove a statement about $n$. This statement can take the form of an identity, an inequality, or simply a verbal statement about $n$. We shall learn more about mathematical induction in the next few sections.

Summary and Review

Mathematical induction can be used to prove that a statement about $n$ is true for all integers $n\geq a$.
We have to complete three steps.
In the base step, verify the statement for $n=a$.
In the inductive hypothesis, assume that the statement holds when $n=k$ for some integer $k\geq a$.
In the inductive step, use the information gathered from the inductive hypothesis to prove that the statement also holds when $n=k+1$.
Be sure to complete all three steps.
Pay attention to the wording. At the beginning, follow the template closely. When you feel comfortable with the whole process, you can start venturing out on your own.

Exercises

Exercise $\PageIndex{1}\label{ex:induct1-01}$

Use induction to prove that \[1^3+2^3+3^3+\cdots+n^3 = \frac{n^2(n+1)^2}{4}\] for all integers $n\geq1$.

Exercise $\PageIndex{2}$

Use induction to prove that the following identity holds for all integers $n\geq1$: \[1+3+5+\cdots+(2n-1) = n^2.\]

Proof

Base Case: consider $n=1$. $2(1)-1=1$ and $1^2=1$ so the LHS & RHS are both 1. This works for $n=1$.

Inductive Step: Assume this works for some integer, $k \geq 1.$ In other words, $1+3+5+\cdots+(2k-1) = k^2.$ (Inductive Hypothesis)

Consider the case of $n=k+1.$ $1+3+5+\cdots +(2k-1)+(2(k+1)-1)$

\[=k^2+(2(k+1)-1) \text{ by inductive hypothesis}\]
\[=k^2+2k+2-1=k^2+2k+1=(k+1)^2 \text{ by algebra} \]

$1+3+5+\cdots+(2(k+1)-1)=(k+1)^2$; assuming our proposition works for $k$ it will also work for $k+1.$

By PMI, $1+3+5+\cdots+(2n-1) = n^2$ for all integers, $n\geq1$.

$W^5$

Exercise $\PageIndex{3}\label{ex:induct1-03}$

Use induction to show that \[1+\frac{1}{3}+\frac{1}{3^2}+\cdots+\frac{1}{3^n} = \frac{3}{2}\left(1-\frac{1}{3^{n+1}}\right)\] for all positive integers $n$.

Exercise $\PageIndex{4}\label{ex:induct1-04}$

Use induction to establish the following identity for any integer $n\geq1$: \[1-3+9-\cdots+(-3)^n = \frac{1-(-3)^{n+1}}{4}.\]

Exercise $\PageIndex{5}\label{ex:induct1-05}$

Use induction to show that, for any integer $n\geq1$: \[\sum_{i=1}^n i\cdot i! = (n+1)!-1.\]

Exercise $\PageIndex{6}\label{ex:induct1-06}$

Use induction to prove the following identity for integers $n\geq1$: \[\sum_{i=1}^n \frac{1}{(2i-1)(2i+1)} = \frac{n}{2n+1}.\]

Exercise $\PageIndex{7}$

Prove $2^{2n}-1$ is divisible by 3, for all integers $n\geq0.$

Proof

Base Case: consider $n=0$. $2^{2(0)}-1=1-1=0.$ $0$ is divisible by 3 because 0 = 0(3).

Inductive Step: Assume this works for some integer, $k \geq 0.$ In other words, $2^{2k}-1$ is divisible by 3. (Inductive Hypothesis)

Since $2^{2k}-1$ is divisible by 3, there exists some integer, m such that $2^{2k}-1=3m,$ by definition of divides.

Consider the case of $n=k+1.$ By algebra: \[2^{2(k+1)}-1=2^{2k+2}-1=2^{2k}\cdot 2^2-1=2^{2k}\cdot 4 -1=2^{2k}\cdot (3+1)-1=3 \cdot 2^{2k}+2^{2k}-1\]
\[=3 \cdot 2^{2k}+3m \text{ by inductive hypothesis}\]

\[=3(2^{2k}+m) \text{ by algebra}\]

$2^{2(k+1)}-1=3(2^{2k}+m)$ and $(2^{2k}+m)\in \mathbb{Z}$ since the integers are closed under addition and multiplication.

So, $2^{2(k+1)}-1$ is divisible by 3 by the definition of divisible.

Thus assuming our proposition works for $k$ it will also work for $k+1.$

By PMI, $2^{2n}-1$ is divisible by 3, for all integers $n\geq0.$

$W^5$

Exercise $\PageIndex{8}\label{ex:induct1-08}$

Evaluate $\sum_{i=1}^n \frac{1}{i(i+1)}$ for a few values of $n$. What do you think the result should be? Use induction to prove your conjecture.

Exercise $\PageIndex{9}\label{ex:induct1-09}$

Use induction to prove that \[\sum_{i=1}^n (2i-1)^3 = n^2(2n^2-1)\] whenever $n$ is a positive integer.

Exercise $\PageIndex{10}\label{ex:induct1-10}$

Use induction to show that, for any integer $n\geq1$: \[1^2-2^2+3^2-\cdots+(-1)^{n-1}n^2 = (-1)^{n-1}\,\frac{n(n+1)}{2}.\]

Exercise $\PageIndex{11}\label{ex:induct1-11}$

Use mathematical induction to show that \[\sum_{i=1}^n \frac{i+4}{i(i+1)(i+2)} = \frac{n(3n+7)}{2(n+1)(n+2)}\] for all integers $n\geq1$.

Exercise $\PageIndex{12}$

Use mathematical induction to show that \[3+\sum_{i=1}^n (3+5i) = \frac{(n+1)(5n+6)}{2}\] for all integers $n\geq1$.

Answer: No answer here at this time.

\(1+2+3+\cdots+n\)

\(\sum_{i=1}^n i^2\)

Can we just use examples?