6.3: More Advanced Induction

Last updated
Save as PDF

Page ID: 60217

Joy Morris
University of Lethbridge

$ \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}}$

Now that we’ve reviewed the basic form of induction, it’s important to consider some more advanced forms that are often used. The first form we’ll look at is strong induction. When we have a recursively-defined sequence that depends on the previous terms, sometimes we need to know not just about the single term that comes immediately before the $n^{\text{th}}$ term, but about other previous terms. Only by putting all of this information together will we be able to deduce the result we need about the $n^{\text{th}}$ term.

Example $\PageIndex{1}$

Let’s define a recursively-defined sequence by $a_1 = 2$ and for every integer $n ≥ 2$, we have

$a_n = \sum_{i=1}^{n-1} a_i$.

Thus, $a_2 = a_1 = 2$;

$\begin{equation} \begin{split} a_3&= a_1 + a_2 = 2 + 2 = 4; \\ a_4&= a_1 + a_2 + a_3 = 2 + 2 + 4 = 8, \end{split} \end{equation} $

and so on. Prove by induction that for every $n ≥ 2$, we have $a_n = 2^{n−1}$.

Solution

We begin with the base case: when $n = 2$, we have $a_2 = 2 = 2^{2−1}$, so the equality is true for the base case. Now for the inductive hypothesis, we let $k ≥ 2$ be arbitrary, and suppose that the equality is true for $n = k$, so $a_k = 2^{k−1}$. Now when $n = k + 1$, we have

$a_n = a_{k+1} = \sum_{i=1}^{k} a_i$,

by the recursive relation for this sequence. We know what $a_1$ is, by our initial condition; we know that $a_k = 2^{k−1}$, but what about the values in between? The Principle of Mathematical Induction as we’ve learned it so far, doesn’t allow us to assume anything about (for example) $a_{k−1}$.

Actually, though, the way the concept of induction works, by the time we’re trying to prove something about an, we’ve actually already deduced it for every value between $n_0$ and $n − 1$(inclusive). So there is nothing wrong with assuming that $P(i)$ is true for every value between $n_0$ and $k$, rather than just for $k$, in order to deduce that $P(k + 1)$ is true. More concretely, this is saying the following. Suppose that by knowing $P(0)$ we can deduce $P(1)$, and then by knowing $P(0)$ and $P(1)$ we can deduce $P(2)$, and so on, so that eventually by knowing that everything from $P(0)$ through $P(k)$ is true, we can deduce that $P(k + 1)$ is true.

Then $P(n)$ is true for every integer $n ≥ 0$. Of course, we don’t have to start with $0$; we can start with any integer $n_0$. This is the strong form of mathematical induction:

Theorem $\PageIndex{1}$: Strong Induction

Suppose we have a statement $P(n)$ about the integer $n$. If we know that

The statement $P(n_0)$ is true for some particular integer $n_0$; and
For any integer $k ≥ n_0$, if every $P(i)$ is true for $n_0 ≤ i ≤ k$, then $P(k + 1)$ must also be true,

then $P(n)$ is true for every integer $n ≥ n_0$.

Using this, we can complete the example we started above. We have $a_1 = 2$ (by the initial condition), and the strong induction hypothesis allows us to assume that $a_i = 2^{i−1}$ for every integer $i$ with $2 ≤ i ≤ k$. So using the recursive relation

\[a_{k+1} = \sum_{i=1}^{k} a_i\]

we see that

\[a_{k+1} = 2 + \sum_{i=2}^{k} 2^{i-1}\]

You probably learned in high school how to add up geometric sequences like this; in particular, that

\[\sum_{j=0}^{k} 2^{j} = 2^{k+1} - 1 \]

and we can re-write what we have as

\[a_{k+1} = 1 + \left( 1 + \sum_{j=1}^{k-1} 2^{j} \right) = 1 + \sum_{j=0}^{k-1} 2^{j} = 1+ (2^{(k-1)+1} - 1) = 2^k \]

This is precisely what we needed to deduce, so this completes the proof.

Let’s go over one more example that involves strong induction. In this example, we’ll need strong induction for a slightly different reason: we’ll need the statement to be true for some values between $n_0$ and $k$, but we’re not necessarily sure which ones.

Example $\PageIndex{2}$

Shawna is building a tower with lego. Prove that if she has n pieces of lego (where $n ≥ 1$), and a “move” consists of sticking two smaller towers together into one (where a tower may consist of one or more pieces of lego), then it will take her $n − 1$ moves to complete the tower

Solution

Base case: $n = 1$. Shawna’s “tower” is already complete after $n − 1 = 0$ moves. This completes the proof of the base case.

Induction step: we begin with the induction hypothesis, that when $1 ≤ i ≤ k$, it takes Shawna $i − 1$ moves to build a tower that contains $i$ pieces of lego.

Now we want to deduce that when Shawna has $k + 1$ pieces of lego, it takes her $k$ moves to stick them together into a single tower. Notice that when she makes her final move, it must consist of sticking together two smaller towers, one of which contains $j$ pieces of lego, and the other of which contains the remaining $k + 1 − j$ pieces. Both $j$ and $k + 1 − j$ must lie between $1$ and $k$ (if either of the smaller towers had $k+1$ pieces then the tower would already be complete), so the induction hypothesis applies to each of them. Thus, it has taken Shawna $j − 1$ move to build the tower that contains $j$ pieces, and $k − j$ moves to build the tower that contains $k − j + 1$ pieces. Together with her final move, then, it must take Shawna

$(j − 1) + (k − j) + 1$

moves in total to complete her tower of $k + 1$ pieces. Now,

$(j − 1) + (k − j) + 1 = k$,

so it takes Shawna $k$ moves to complete the tower, which is what we wanted to deduce. This completes the proof of the inductive step.

By Strong Induction, it will take Shawna $n − 1$ moves to complete a tower that contains $n$ blocks of lego, for every $n ≥ 1$.

This is pretty amazing. If we tried to go through the full argument for how many moves it takes her to build a tower with four blocks, it would go something like this. First, to build a tower with one block clearly takes $0$ moves; to build a tower with two blocks clearly takes $1$ move (stick the two blocks together). To build a tower with three blocks, we must use $1$ move to stick together a tower of two blocks (which took $1$ move to create) with a tower of one block (which took $0$ moves to create), meaning that we use $2$ moves altogether. Now, a tower of four blocks can be built in two ways: by using $1$ move to stick together two towers of two blocks, each of which took $1$ move to make, for a total of $3$ moves; or by using $1$ move to stick together a tower of one block (which took $0$ moves to make) with a tower of three blocks (which took $2$ moves to make), for a total of $3$ moves. So under either method, building a tower of four blocks takes $3$ moves. You can see that the argument will get more and more complicated as $n$ increases, but it will always continue to work.

We won’t need strong induction as such very much until later in the course, but the idea is useful background for the next kind of induction we’ll look at, which is very important when dealing with recurrence relations: induction with multiple base cases.

Induction with multiple base cases is very important for dealing with recursively defined sequences such as the Fibonacci sequence, where each term depends on more than one of the preceding terms.

Suppose you were asked to prove that the nth term of the Fibonacci sequence, $f_n$, is at least $2^{n−2}$. If we try to follow our basic inductive strategy, we’d begin by observing that this is true for $f_0$:

$f_0 = 1 ≥ 2 −2 = \dfrac{1}{4}$.

Then we’d make the inductive hypothesis that our inequality is true for some arbitrary $k ≥ 0$, so $f_k ≥ 2^{k−2}$. Now to deduce the inequality for $n = k + 1$, the natural approach is to use the recursive relation, which tells us that

$f_{k+1} = f_k + f_{k−1}$.

We can use our inductive hypothesis to make a substitution for $f_k$, but what about $f_{k−1}$? You might (reasonably) argue at this point that we should use strong induction, which will allow us to assume that the result is true for both $f_k$ and $f_{k−1}$, but actually, this doesn’t work! Why not? Well, the trouble is that everything we know about the Fibonacci sequence starts with $f_0$, but if $k = 1$ (which is the first time we try to use induction) then $f_{k−1} = f_{−1}$, which we haven’t even defined! It is very important to ensure that in the inductive step, we never make our assumption go back too far, i.e. to a value below $n_0$.

So, how can we deal with this problem? The solution is to add another base case, for $n = 1$. When $n = 1$, we have

$f_1 = 1 ≥ 2^{1−2} = \dfrac{1}{2}$.

Now if we try induction, at the first step we will be using the fact that the statement is true for $f_0$ and $f_1$ to prove it for $f_2$; then the fact that it’s true for $f_1$ and $f_2$ will allow us to deduce it for $f_3$, and so on. The final argument will look like the following.

Example $\PageIndex{3}$

Prove by induction that the $n^{\text{th}}$ term of the Fibonacci sequence, $f_n$, is at least $\left( \dfrac{3}{2} \right)^{n−1}$, for every $n ≥ 0$.

Solution

Since the recursive relation for the Fibonacci sequence requires the two immediately preceding terms, we will require two base cases.

Base cases: When $n = 0$, we have

$f_0 = 1 ≥ \left( \dfrac{3}{2} \right)^{−1} = \dfrac{2}{3}$,

so the inequality holds for $n = 0$. When $n = 1$, we have

$f_1 = 1 ≥ \left( \dfrac{3}{2} \right)^{1−1} = 1$,

so the inequality holds for $n = 1$. This completes the proof of the base cases.

Inductive step: We begin with the (strong) inductive hypothesis. Let $k$ be an arbitrary integer at least as big as our biggest base case, so $k ≥ 1$. Assume that for every integer $i$ with $0 ≤ i ≤ k$, we have $f_i ≥ \left( \dfrac{3}{2} \right)^{i−1}$.

Now we want to deduce that

$f_{k+1} ≥ \left( \dfrac{3}{2} \right)^{(k+1)−1} = \left( \dfrac{3}{2} \right)^k $.

Using the recursive relation, we know that $f_{k+1} = f_k +f_{k−1}$. Since $k ≥ 1$, we have $k −1 ≥ 0$, so both $k$ and $k − 1$ satisfy the bounds on $i$ (that $0 ≤ i ≤ k$), so that we can apply our inductive hypothesis to both $f_k$ and $f_{k−1}$. We therefore have

$f_{k+1} ≥ \left( \dfrac{3}{2} \right)^{k−1} + \left( \dfrac{3}{2} \right)^{k−2} = \left( \dfrac{3}{2} + 1 \right)\left( \dfrac{3}{2} \right)^{k−2} = \dfrac{5}{2} \left( \dfrac{3}{2} \right)^{k−2} = \dfrac{5}{3} \cdot \dfrac{3}{2} \left( \dfrac{3}{2} \right)^{k−2} > \left( \dfrac{3}{2} \right)^k $

since $\dfrac{5}{3} > \dfrac{3}{2}$. This is what we wanted to deduce. This completes the proof of the inductive step.

By the Principle of Mathematical Induction, $f_n ≥ \left( \dfrac{3}{2} \right)^{n−1}$ for every $n ≥ 0$.

Exercise $\PageIndex{1}$

Prove by induction that for every $n ≥ 0$, the nth term of the Fibonacci sequence is no greater than $2^n$.
The machine at the coffee shop isn’t working properly, and can only put increments of $$4$ or $$5$ on your gift card. Prove by induction that you can get any amount of dollars that is at least $$12$. [Hint: You should have four base cases.]
Define a recurrence relation by $a_0 = a_1 = a_2 = 1$, and $a_n = a_{n−1} + a_{n−2} + a_{n−3}$ for $n ≥ 3$. Prove by induction that $a_n ≤ 2^n$ for all $n ≥ 0$.