Advanced induction

Section 6.3 Advanced induction

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$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$th term.

Example 6.3.1.

Let's define a recursively-defined sequence by $a_1=2$ and for every integer $n \ge 2\text{,}$ we have

\begin{equation*} a_n=\sum_{i=1}^{n-1}a_i\text{.} \end{equation*}

Thus, $a_2=a_1=2\text{;}$

\begin{align*} a_3\amp= a_1+a_2=2+2=4;\\ a_4\amp= a_1+a_2+a_3=2+2+4=8\text{,} \end{align*}

and so on. Prove by induction that for every $n \ge 2\text{,}$ we have $a_n=2^{n-1}\text{.}$

Solution attempt

We begin with the base case: when $n=2\text{,}$ we have $a_2=2=2^{2-1}\text{,}$ so the equality is true for the base case. Now for the induction hypothesis, we let $k > 2$ be arbitrary, and suppose that the equality is true for $n=k-1\text{,}$ so $a_{k-1}=2^{(k-1)-1} = 2^{k-2}\text{.}$ Now when $n=k\text{,}$ we have

\begin{equation*} a_n=a_{k}=\sum_{i=1}^{k-1} a_i = a_1 + a_2 + \cdots + a_{k-1}\text{,} \end{equation*}

by the recursive relation for this sequence. We know what $a_1$ is, by our initial condition, and we know that $a_{k-1}=2^{k-1}\text{,}$ 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-2}\text{.}$

Actually, though, the way the concept of induction works, by the time we're trying to prove something about $a_n\text{,}$ 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-1\text{,}$ rather than just for $k-1\text{,}$ in order to deduce that $P(k)$ is true. More concretely, this is saying the following. Suppose that by knowing $P(0)$ we can deduce $P(1)\text{,}$ and then by knowing $P(0)$ and $P(1)$ we can deduce $P(2)\text{,}$ and so on, so that eventually by knowing that everything from $P(0)$ through $P(k-1)$ is true, we can deduce that $P(k)$ is true. Then $P(n)$ is true for every integer $n \ge 0\text{.}$ Of course, we don't have to start with $0\text{;}$ we can start with any integer $n_0\text{.}$ This is the strong form of mathematical induction:

Theorem 6.3.2 (Strong Induction).

Suppose we have a statement $P(n)$ about the integer $n\text{.}$ Assume that

the statement $P(n_0)$ is true for some particular integer $n_0\text{;}$ and
for every integer $k > n_0\text{,}$ if every $P(i)$ is true for $n_0 \le i \le k-1\text{,}$ then $P(k)$ must also be true.

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

Using this, we can complete the induction step in the example we started above. For $k > 2$, strong induction allows us to assume that $a_i=2^{i-1}$ for every integer $i$ with $2 \le i < k\text{.}$ Therefore

\begin{align*} a_k &= \sum_{i=1}^{k-1} a_i && \text{(definition of $a_k$)} \\ &=a_1 + \sum_{i=2}^{k-1} a_i && \text{(separating the $i = 1$ term from the rest of the sum)} \\ &=a_1 + \sum_{i=2}^{k-1} 2^{i-1} && \text{(induction hypothesis)} \\ &=2 + \sum_{i=2}^{k-1} 2^{i-1} && \text{($a_1 = 2$ by definition)} \\ &=2 + \sum_{j=1}^{k-2} 2^{k} && \text{(letting $j = i-1$)} \end{align*}

You may have learned in high school how to calculate the sum of a geometric series like this. Even if you didn't, we know from Exercise 6.2.6.3 that

\begin{equation*} \sum_{j=0}^m 2^j=2^{m+1}-1\text{.} \end{equation*}

Letting $m = k -2$, we conclude that

\begin{equation*} \sum_{j=0}^{k-2} 2^{k} = 2^{(k-2)+1} - 1 = 2^{k-1} + 1 \text{.} \end{equation*}

\begin{equation*} a_k = 2 + \sum_{j=1}^{k-2} 2^{k} = 2 - 2^0 + \sum_{j=0}^{k-2} 2^{k} =- 2 - 1 + (2^{k-1} + 1) = 2^{k-1} , \end{equation*}

as desired. 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\text{,}$ but we're not necessarily sure which ones.

Example 6.3.3.

Shawna is building a tower with Lego. Prove that if she has $n$ pieces of Lego (where $n \ge 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.

Proof

Base case: $n=1\text{.}$ Shawna's “tower” is already complete without making any moves. So the number of moves needed is 0. Since $n = 1\text{,}$ we also have $n - 1 = 0 \text{,}$ so the number of moves needed is equal to $n - 1\text{.}$ This completes the proof of the base case.

Induction step: Assume that when $1 \le i < k\text{,}$ 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$ pieces of Lego, it takes her $k-1$ 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-j$ pieces. Both $j$ and $k-j$ must lie between $1$ and $k-1$ (if either of the smaller towers had $k$ pieces then the tower would already be complete), so the induction hypothesis applies to each of them. Thus, it has taken Shawna $j-1$ moves to build the tower that contains $j$ pieces, and $k-j - 1$ moves to build the tower that contains $k-j$ pieces. Together with her final move, then the number of moves to complete the entire tower of $k$ pieces is $(j-1)+(k-j-1) + 1 = k - 1 \text{,}$ as desired. This completes the proof of the induction step.

By Strong Induction, it will take Shawna $n-1$ moves to complete a tower that contains $n$ blocks of Lego, for every $n \ge 1\text{.}$

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 $n^{\text{th}}$ term of the Fibonacci sequence, $f_n\text{,}$ is at least $(3/2)^{n-1}\text{.}$ If we try to follow our basic inductive strategy, we'd begin by observing that this is true for $n = 0\text{:}$

\begin{equation*} f_0=1 \ge 2/3 = (3/2)^{-1} = (3/2)^{0-1}\text{.} \end{equation*}

Then we consider some $k > 0 \text{,}$ and assume (the induction hypothesis) that $f_{k-1} \ge (3/2)^{k-1}\text{.}$ Now to establish the desired inequality for $n=k\text{,}$ the natural approach is to use the recursive relation, which tells us that

\begin{equation*} f_{k}=f_{k-1}+f_{k-2}\text{.} \end{equation*}

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

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

\begin{equation*} f_1=1 \ge 1 = (3/2)^{0} = (3/2)^{1-1}\text{.} \end{equation*}

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\text{;}$ then the fact that it's true for $f_1$ and $f_2$ will allow us to deduce it for $f_3\text{,}$ and so on. The final argument will look like the following.

Example 6.3.4.

Prove by induction that the $n$th term of the Fibonacci sequence, $f_n\text{,}$ is at least $(3/2)^{n-1}\text{,}$ for every $n \ge 0\text{.}$

Solution

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

Proof by induction. Base cases: For $n=0\text{,}$ we have

\begin{equation*} f_n = f_0=1 \ge 2/3 = (3/2)^{-1}= (3/2)^{0-1} = (3/2)^{n-1}\text{,} \end{equation*}

so the inequality holds for $n=0\text{.}$ When $n=1\text{,}$ we have

\begin{equation*} f_n = f_1=1 = (3/2)^{0} = (3/2)^{1-1} = (3/2)^{n-1}\text{,} \end{equation*}

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

Induction step: Let $k$ be an arbitrary integer that is larger than our biggest base case, so $k > 1\text{.}$ Assume that for every integer $i$ with $0 \le i < k\text{,}$ we have $f_i \ge (3/2)^{i-1}\text{.}$

Now we want to deduce that

\begin{equation*} f_{k} \ge (3/2)^{k-1}\text{.} \end{equation*}

Using the recursive relation, we know that $f_{k}=f_{k-1}+f_{k-2}\text{.}$ Since $k > 1\text{,}$ we have $k > k-1 > k-2 \ge 0\text{,}$ so both $k-1$ and $k-2$ satisfy the bounds on $i$ (that $0 \le i < k$), so we can apply our induction hypothesis to both $f_{k-1}$ and $f_{k-2}\text{.}$ We therefore have

\begin{gather*} f_{k} = f_{k-1} + f_{k-2} \ge \left( \frac{3}{2} \right)^{\! k-2}+\left( \frac{3}{2} \right)^{\! k-3} = \left( \frac{3}{2} + 1 \right) \left( \frac{3}{2} \right)^{\! k-3} > \left(\frac{3}{2}\right)^{\! 2} \left( \frac{3}{2} \right)^{\! k-3} = \left( \frac{3}{2} \right)^{\! k-1}\text{,} \end{gather*}

since

\begin{equation*} \frac{3}{2} + 1 = 2.5 > 2.25 =\left(\frac{3}{2}\right)^{\! 2} \text{.} \end{equation*}

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

By the Principle of Mathematical Induction, $f_n \ge (3/2)^{n-1}$ for every $n \ge 0\text{.}$

Exercises 6.3.5.

Prove by induction that for every $n \ge 0\text{,}$ the $n$th term of the Fibonacci sequence is no greater than $2^n\text{.}$
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\text{,}$ and $a_n=a_{n-1}+a_{n-2}+a_{n-3}$ for $n \ge 3\text{.}$ Prove by induction that $a_n \le 2^n$ for all $n \ge 0\text{.}$