Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

6.3: More Advanced Induction

( \newcommand{\kernel}{\mathrm{null}\,}\)

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 nth 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 nth term.

Example 6.3.1

Let’s define a recursively-defined sequence by a1=2 and for every integer n2, we have

an=n1i=1ai.

Thus, a2=a1=2;

a3=a1+a2=2+2=4;a4=a1+a2+a3=2+2+4=8,

and so on. Prove by induction that for every n2, we have an=2n1.

Solution

We begin with the base case: when n=2, we have a2=2=221, so the equality is true for the base case. Now for the inductive hypothesis, we let k2 be arbitrary, and suppose that the equality is true for n=k, so ak=2k1. Now when n=k+1, we have

an=ak+1=ki=1ai,

by the recursive relation for this sequence. We know what a1 is, by our initial condition; we know that ak=2k1, 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) ak1.

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 n0 and n1(inclusive). So there is nothing wrong with assuming that P(i) is true for every value between n0 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 n0. Of course, we don’t have to start with 0; we can start with any integer n0. This is the strong form of mathematical induction:

Theorem 6.3.1: Strong Induction

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

  1. The statement P(n0) is true for some particular integer n0; and
  2. For any integer kn0, if every P(i) is true for n0ik, then P(k+1) must also be true,

then P(n) is true for every integer nn0.

Using this, we can complete the example we started above. We have a1=2 (by the initial condition), and the strong induction hypothesis allows us to assume that ai=2i1 for every integer i with 2ik. So using the recursive relation

ak+1=ki=1ai

we see that

ak+1=2+ki=22i1

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

kj=02j=2k+11

and we can re-write what we have as

ak+1=1+(1+k1j=12j)=1+k1j=02j=1+(2(k1)+11)=2k

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 n0 and k, but we’re not necessarily sure which ones.

Example 6.3.2

Shawna is building a tower with lego. Prove that if she has n pieces of lego (where n1), 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 n1 moves to complete the tower

Solution

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

Induction step: we begin with the induction hypothesis, that when 1ik, it takes Shawna i1 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+1j pieces. Both j and k+1j 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 j1 move to build the tower that contains j pieces, and kj moves to build the tower that contains kj+1 pieces. Together with her final move, then, it must take Shawna

(j1)+(kj)+1

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

(j1)+(kj)+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 n1 moves to complete a tower that contains n blocks of lego, for every n1.

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, fn, is at least 2n2. If we try to follow our basic inductive strategy, we’d begin by observing that this is true for f0:

f0=122=14.

Then we’d make the inductive hypothesis that our inequality is true for some arbitrary k0, so fk2k2. Now to deduce the inequality for n=k+1, the natural approach is to use the recursive relation, which tells us that

fk+1=fk+fk1.

We can use our inductive hypothesis to make a substitution for fk, but what about fk1? 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 fk and fk1, but actually, this doesn’t work! Why not? Well, the trouble is that everything we know about the Fibonacci sequence starts with f0, but if k=1 (which is the first time we try to use induction) then fk1=f1, 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 n0.

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

f1=1212=12.

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

Example 6.3.3

Prove by induction that the nth term of the Fibonacci sequence, fn, is at least (32)n1, for every n0.

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

f0=1(32)1=23,

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

f1=1(32)11=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 k1. Assume that for every integer i with 0ik, we have fi(32)i1.

Now we want to deduce that

fk+1(32)(k+1)1=(32)k.

Using the recursive relation, we know that fk+1=fk+fk1. Since k1, we have k10, so both k and k1 satisfy the bounds on i (that 0ik), so that we can apply our inductive hypothesis to both fk and fk1. We therefore have

fk+1(32)k1+(32)k2=(32+1)(32)k2=52(32)k2=5332(32)k2>(32)k

since 53>32. This is what we wanted to deduce. This completes the proof of the inductive step.

By the Principle of Mathematical Induction, fn(32)n1 for every n0.

Exercise 6.3.1

  1. Prove by induction that for every n0, the nth term of the Fibonacci sequence is no greater than 2n.
  2. 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.]
  3. Define a recurrence relation by a0=a1=a2=1, and an=an1+an2+an3 for n3. Prove by induction that an2n for all n0.

This page titled 6.3: More Advanced Induction is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Joy Morris.

  • Was this article helpful?

Support Center

How can we help?