Basic induction

🔗

Section 6.2 Basic induction

🔗

Suppose we want to show that

$n!$ is at least

$2^n-2\text{,}$ for every

$n \ge 1$ (where

$n$ must be an integer). We could start verifying this fact for each of the possible values for

$n\text{:}$

$\begin{align*} 1!\amp= 1\ge 2^1-2 = 0;\\ 2!\amp= 2 \ge 2^2-2=2;\\ 3!\amp= 6 \ge 2^3 -2=6;\\ 4!\amp= 24 \ge 2^4-2=14\text{.} \end{align*}$

🔗

We could continue verifying the values one at a time, but the process would go on forever, so we'd never be able to complete the proof.

🔗

Instead, think about the following method. We know that the inequality holds for

$n=1\text{.}$ Let's suppose that the inequality holds for some value

$n=k\text{,}$ i.e. that

$\begin{equation*} k!\ge 2^k-2\text{.} \end{equation*}$

🔗

Now let's use the fact that we can easily calculate

$(k+1)!$ from

$k!$ together with our supposition, to deduce that the inequality holds when

$n=k+1\text{,}$ i.e. that

$\begin{equation*} (k+1)! \ge 2^{k+1}-2\text{.} \end{equation*}$

🔗

This is enough to prove the inequality for every integer

$n \ge 1\text{,}$ because applying our supposition and deduction enough times will prove the inequality for any value at all that interests us! For example, if we wanted to be sure that the inequality holds for

$n=100\text{,}$ we could take the fact that we know it holds for

$1\text{,}$ to deduce that it holds for

$2\text{,}$ then the fact that it holds for

$2$ allows us to deduce that it holds for

$3\text{.}$ By repeating this

$97$ more times, eventually we see that since it holds for

$99\text{,}$ we can deduce that it holds for

$100\text{.}$

🔗

Theorem 6.2.1 (Principle of Mathematical Induction).

Let $P(n)$ be an assertion about the integer $n\text{.}$ If we know that

the assertion $P(n_0)$ is true for some particular integer $n_0\text{;}$ and
for any integer $k \ge n_0\text{,}$ if $P(k)$ is true then $P(k+1)$ must also be true,

then $P(n)$ is true for every integer $n \ge n_0\text{.}$

🔗

Definition 6.2.2.

In a proof by induction, determining that $P(n_0)$ is true for some particular integer $n_0$ is called the base case. Proving the conditional statement that $P(k) \Rightarrow P(k+1)$ for every $k \ge n_0$ is called the inductive step. The assumption we make in the inductive step, that $P(k)$ is true for some arbitrary $k \ge n_0\text{,}$ is called the inductive hypothesis, and can be referred to by (IH) when it is being used in the proof.

🔗

Now that we've gone through the formalities, let's write a proper proof by induction for the inequality we used to introduce this idea.

🔗

Example 6.2.3.

Prove by induction that $n!\ge 2^n-2\text{,}$ for every integer $n \ge 2\text{.}$ (This inequality is actually true for every $n \ge 0\text{,}$ but the proof is considerably simpler if we restrict our attention to $n \ge 2\text{.}$)

Proof.

Base case: $n=2\text{.}$ We have $n!=2!=2\text{,}$ and

\begin{equation*} 2^n-2=2^2-2=4-2=2\text{.} \end{equation*}

Certainly $2 \ge 2\text{,}$ so the inequality holds for $n=2\text{.}$ This completes the proof of the base case.

Inductive step: We begin with the inductive hypothesis. Let $k \ge 2$ be arbitrary, and suppose that the inequality holds for $n=k\text{;}$ that is, assume that $k! \ge 2^k-2\text{.}$

Now we want to deduce that

\begin{equation*} (k+1)! \ge 2^{k+1}-2\text{.} \end{equation*}

Let's start from the left-hand side of this inequality. By the definition of factorial, we know that

\begin{equation*} (k+1)!=(k+1)k!\text{.} \end{equation*}

Now that we have $k!$ in the expression, we're in a position to apply the inductive hypothesis; that is,

\begin{equation*} (k+1)!=(k+1)k! \ge (k+1)(2^k-2)\text{.} \end{equation*}

Since $k \ge 2\text{,}$ we have $k+1 \ge 3\text{,}$ so

\begin{equation*} (k+1)(2^k-2) \ge 3(2^k-2)=2(2^k)+2^k-6 = 2^{k+1}+2^k-6\text{.} \end{equation*}

Again, since $k \ge 2\text{,}$ we have $2^k \ge 4\text{,}$ so $2^k-6 \ge -2\text{.}$ Hence

\begin{equation*} (k+1)! \ge 2^{k+1}+2^k-6 \ge 2^{k+1}-2\text{,} \end{equation*}

which is what we wanted to deduce. This completes the proof of the inductive step.

By the Principle of Mathematical Induction, $n! \ge 2^n-2$ for every integer $n \ge 2\text{.}$

🔗

Proofs by induction work very naturally with recursively-defined sequences, since the recurrence relation gives us information about the (

$k+1$ )st term of the sequence, based on previous terms.

🔗

Example 6.2.4.

Consider the sum of the first $n$ integers. We can think about this as a recursively-defined sequence, by defining $s_1=1\text{,}$ and $s_{n}=s_{n-1}+n\text{,}$ for every $n \ge 2\text{.}$ Thus, $s_2=1+2\text{;}$

\begin{equation*} s_3=s_2+3=1+2+3\text{,} \end{equation*}

and so on. Prove by induction that $s_n=n(n+1)/2\text{,}$ for every $n \ge 1\text{.}$

Proof.

Base case: $n=1\text{.}$ We have $s_n=s_1=1\text{,}$ and

\begin{equation*} n(n+1)/2=1(2)/2=1\text{,} \end{equation*}

so the equality holds for $n=1\text{.}$ This completes the proof of the base case.

Inductive step: We begin with the inductive hypothesis. Let $k \ge 1$ be arbitrary, and suppose that the equality holds for $n=k\text{;}$ that is, assume that $s_k=k(k+1)/2\text{.}$

Now we want to deduce that

\begin{equation*} s_{k+1}=(k+1)(k+2)/2\text{.} \end{equation*}

Using the recursive relation, we have $s_{k+1}=s_k+(k+1)$ since $k+1 \ge 2\text{,}$ and using the inductive hypothesis, we have $s_k=k(k+1)/2\text{,}$ so putting these together, we see that

\begin{equation*} s_{k+1}=k(k+1)/2+(k+1)\text{.} \end{equation*}

Taking out a common factor of $k+1$ gives

\begin{equation*} s_{k+1}=(k+1)(k/2+1)=(k+1)(k+2)/2\text{,} \end{equation*}

which is what we wanted to deduce. This completes the proof of the inductive step.

By the Principle of Mathematical Induction, $s_n=n(n+1)/2$ for every $n \ge 1\text{.}$

🔗

Caution: the steps of a proof by induction are precisely defined, and if you leave any of them out, or forget the conditions required, things can go badly wrong. The base case may seem obvious, but can't be left out; also, the hypothesis that

$k \ge n_0$ may be critical to the proof, as we saw in Example 6.2.3.

🔗

Let's look at an example where, by forgetting to include the base case, we can give a “proof by induction” of something that is clearly false.

🔗

Example 6.2.5.

Here is a “proof by induction” (without a base case) that every integer $n$ is at least $1000\text{.}$

Proof.

Inductive step: We begin with the inductive hypothesis. Let $k$ be arbitrary, and suppose that $k \ge 1000\text{.}$

Now we want to deduce that $k+1 \ge 1000\text{.}$ But clearly,

\begin{equation*} k+1 \ge k \ge 1000 \end{equation*}

(by our inductive hypothesis), which is what we wanted to deduce. This completes the proof of the inductive step.

By the Principle of Mathematical Induction, $n \ge 1000$ for every integer $n\text{.}$

🔗

Now it's your turn to try a few. Don't leave out any of the steps!

🔗

Exercises 6.2.6.

Use the Principle of Mathematical Induction to prove the following:

For the recursively-defined sequence given by $b_1=5$ and $b_n=b_{n-1}+4$ for all $n \ge 2\text{,}$ prove that for every integer $n \ge 1\text{,}$ $b_n=5+4(n-1)\text{.}$
For the recursively-defined sequence given by $c_1=3$ and $c_n=c_{n-1}+3 \cdot 2^{n-1}$ for all $n \ge 2\text{,}$ prove that for every integer $n \ge 1\text{,}$ $c_n=3(2^n-1)\text{.}$
Prove that for every integer $n \ge 0\text{,}$ $n! \ge n\text{.}$
Prove that for every integer $n \ge 0\text{,}$ $4^{n}-1$ is divisible by 3.
Starting with $n=2$ and increasing $n$ from there, calculate the first few values for the product

\begin{equation*} t_n=\prod_{j=2}^n (1-\frac{1}{j})\text{.} \end{equation*}

Conjecture a closed formula for $t_n$ based on the values you have calculated, and use induction to prove that your formula is correct.
Prove that for every integer $n \ge 1\text{,}$

\begin{equation*} \sum_{j=1}^{n}j! \le \frac{1}{2}(n+1)! \end{equation*}
Define $c_0=1$ and for $n \ge 1\text{,}$ define $c_n=n c_{n-1}+1\text{.}$ Prove by induction: for $n \ge 0\text{,}$

\begin{equation*} c_n = \sum_{j=0}^n\frac{n!}{(n-j)!}\text{.} \end{equation*}