1.2: Proof by Induction

In this section, I list a number of statements that can be proved by use of The Principle of Mathematical Induction. I will refer to this principle as PMI or, simply, induction. A sample proof is given below. The rest will be given in class hopefully by students.

A Sample Proof using Induction:

I will give two versions of this proof. In the first proof I explain in detail how one uses the PMI. The second proof is less pedagogical and is the type of proof I expect students to construct. I call the statement I want to prove a proposition. It might also be called a theorem, lemma or corollary depending on the situation.

Proposition \(\PageIndex{1}\)

If \(n \ge 5\) then \(2^n>5n\).

Proof

Here we use The Principle of Mathematical Induction. Note that PMI has two parts which we denote by PMI (a) and PMI (b).

We let \(P(n)\) be the statement \(2^n>5n\). For \(n_0\) we take \(5\). We could write simply: \[\begin{aligned} P(n) &=2^n>5n \mbox{ and } n_0 =5.\end{aligned}\] Note that \(P(n)\) represents a statement, usually an inequality or an equation but sometimes a more complicated assertion. Now if \(n=4\) then \(P(n)\) becomes the statement \(2^4>5\cdot 4\) which is false! But if \(n=5\), \(P(n)\) is the statement \(2^5>5\cdot 5\) or \(32>25\) which is true and we have established PMI (a).

Now to prove PMI (b) we begin by assuming that \[P(n) \text{ is true for } 5 \le n \le k.\nonumber\] That is, we assume \[ \label{eq:1} 2^n>5n\text{ for } 5 \le n \le k.\]

The assumption \(\eqref{eq:1}\) is called the induction hypothesis. We want to use it to prove that \(P(n)\) holds when \(n=k+1\). So here’s what we do. By \(\eqref{eq:1}\) letting \(n=k\) we have \[2^k>5k.\nonumber\] Multiply both sides by two and we get \[\label{eq:2} 2^{k+1} >10k.\] Note that we are trying to prove \(2^{k+1}>5(k+1)\). Now \(5(k+1)=5k+5\) so if we can show \(10k\geq 5k+5\) we can use \(\eqref{eq:2}\) to complete the proof.

Now \(10k=5k+5k\) and \(k\geq 5\) by \(\eqref{eq:1}\) so \(k\geq 1\) and hence \(5k\geq 5\). Therefore \[10k=5k+5k\geq 5k+5=5(k+1).\nonumber\] Thus \[2^{k+1}>10k\geq 5(k+1)\nonumber \] so \[\label{eq:3}2^{k+1}>5(k+1).\] that is, \(P(n)\) holds when \(n=k+1\). So assuming the induction hypothesis \(\eqref{eq:1}\) we have proved \(\eqref{eq:3}\). Thus we have established PMI (b).

We have established that parts (a) and (b) of PMI hold for this particular \(P(n)\) and \(n_0\). So the PMI tells us that \(P(n)\) holds for \(n\geq 5\). That is, \(2^n>5n\) holds for \(n\geq 5\).

I now give a more streamlined proof.

Proposition \(\PageIndex{2}\)

If \(n \ge 5\) then \(2^n>5n\).

Proof

We prove the proposition by induction on the variable \(n\).

If \(n=5\) we have \(2^5>5 \cdot 5\) or \(32>25\) which is true.

Assume \[2^n>5n \quad \text{ for }5 \le n \le k \quad \text{(the induction hypothesis)}.\nonumber \] Taking \(n = k\) we have \[2^k>5k.\nonumber \] Multiplying both sides by 2 gives \[2^{k+1}>10k.\nonumber \] Now \(10k=5k+5k\) and \(k\geq 5\) so \(k\geq 1\) and therefore \(5k\geq 5\). Hence \[10k=5k+5k\geq 5k+5=5(k+1).\nonumber \] It follows that \[2^{k+1}>10k\geq 5(k+1)\nonumber \] and therefore \[2^{k+1}>5(k+1).\nonumber \]

Hence by PMI we conclude that \(2^n>5n\) for \(n\geq 5\).

The 8 Major Parts of a Proof by Induction:

1. First state what proposition you are going to prove. Precede the statement by Proposition, Theorem, Lemma, Corollary, Fact, or To Prove:.
2. Write the Proof or Pf. at the very beginning of your proof.
3. Say that you are going to use induction (some proofs do not use induction!) and if it is not obvious from the statement of the proposition identify clearly \(P(n)\), the statement to be proved, the variable \(n\) and the starting value \(n_0\). Even though this is usually clear, sometimes these things may not be obvious. And, of course, the variable need not be \(n\). It could be represented in many different ways.
4. Prove that \(P(n)\) holds when \(n = n_0\).
5. Assume that \(P(n)\) holds for \(n_0\le n\le k\). This assumption will be referred to as the induction hypothesis.
6. Use the induction hypothesis and anything else that is known to be true to prove that \(P(n)\) holds when \(n=k+1\).
7. Conclude that since the conditions of the PMI have been met then \(P(n)\) holds for \(n\ge n_0\).
8. Write QED or \(\blacksquare\) or \(//\) or something to indicate that you have completed your proof.

Exercise \(\PageIndex{1}\)

Prove that \(2^n>6n\) for \(n\geq 5\).

Exercise \(\PageIndex{2}\)

Prove that \(1+2+\cdots +n=\dfrac{n(n+1)}2\) for \(n\geq 1\).

Exercise \(\PageIndex{3}\)

Prove that if \(0 < a < b\) then \(0 < a^n<b^n\) for all \(n \in \mathbb{N}\).

Exercise \(\PageIndex{4}\)

Prove that \(n!<n^n\) for \(n\geq 2\).

Exercise \(\PageIndex{5}\)

Prove that if \(a\) and \(r\) are real numbers and \(r\neq 1\), then for \(n \ge 1\) \[a+ar+ar^2+\cdots +ar^n=\dfrac{a\left( r^{n+1}-1\right)}{r-1}.\nonumber\] This can be written as follows \[a(r^{n+1}-1) = (r-1)(a+ar+ar^2+\cdots +ar^n).\nonumber\] And important special case of which is \[(r^{n+1}-1) = (r-1)(1+r+r^2+\cdots +r^n).\nonumber\]

Exercise \(\PageIndex{6}\)

Prove that \(1+2+2^2+\cdots +2^n=2^{n+1}-1\) for \(n \ge 1\).

Exercise \(\PageIndex{7}\)

Prove that \(\underbrace{111\cdots 1}_{n \,1\mbox {'s}}=\dfrac{10^n-1}9\) for \(n \ge 1\).

Exercise \(\PageIndex{8}\)

Prove that \(1^2+2^2+3^2+\cdots +n^2=\dfrac{n(n+1)(2n+1)}6\) if \(n\geq 1\).

Exercise \(\PageIndex{9}\)

Prove that if \(n\geq 12\) then \(n\) can be written as a sum of \(4\)’s and \(5\)’s. For example, \(23=5+5+5+4+4=3 \cdot 5+2 \cdot 4\).

Hint

In this case it will help to do the cases \(n=12\), \(13\), \(14\), and \(15\) separately. Then use induction to handle \(n\geq 16\).

Exercise \(\PageIndex{10}\)

1. For \(n\ge 1\), the triangular number \(t_n\) is the number of dots in a triangular array that has \(n\) rows with \(i\) dots in the \(i\)-th row. Find a formula for \(t_n\), \(n\ge 1\).
2. Suppose that for each \(n \ge 1\). Let \(s_n\) be the number of dots in a square array that has \(n\) rows with \(n\) dots in each row. Find a formula for \(s_n\). The numbers \(s_n\) are usually called squares.

Exercise \(\PageIndex{11}\)

Find the first 10 triangular numbers and the first 10 squares. Which of the triangular numbers in your list are also squares? Can you find the next triangular number which is a square?

Exercise \(\PageIndex{12}\)

Some propositions that can be proved by induction can also be proved without induction. Prove Exercise \(\PageIndex{2}\) and Exercise \(\PageIndex{5}\) without induction.

Hint

For Exercise \(\PageIndex{2}\) write \(s=1+2+\dots+(n-1)+n\). Directly under this equation write \(s=n+(n-1)+\dots+2+1\). Add these equations to obtain \(2s = n(n+1)\). Solve for \(s\). For Exercise \(\PageIndex{5}\) write \(p=a+ar+ar^2+\dots+ar^n\). Then multiply both sides of this equation by \(r\) to get a new equation with \(rp\) as the left hand side. Subtract these two equation to obtain \(pr-p=ar^{n+1}-a\). Now solve for \(p\).