Processing math: 100%

An Example of Strong Induction

Hello everyone. So in this example we're going to talk about an induction problem, and this happened to be one example that I skipped from class to leave as an exercise, but I wanted to go over it in a video. And if you've seen it already, then at least you're going to get a little bit of extra practice with the argument.

Let $\{f_n\}$ be the Fibonacci sequence (that is, $f_1=1$, $f_2=1$ and $f_n=f_{n-1}+f_{n-2}$ for all $n\geq 3$). Show that $f_n < \displaystyle\left(\frac{7}{4}\right)^n$ for all $n\in\mathbb{N}$

So the first two terms are $1$ and every subsequent term is the sum of the previous two, that's what this says mathematically.

So we're trying to show that each Fibonacci number is bounded by $\displaystyle\frac{7}{4}$. The tip-off here to sort of use induction here is that we're trying to show some sentence is true for all natural numbers $n$, and the sequence that we have is defined recursively. So both of these things combined sort of suggest let's use Mathematical Induction.

Now the question is do I use Strong Mathematical Induction or just the Principle of Mathematical Induction? You can try to figure out before you write the proof, but I like to figure it out as I write the proof and if I'm wrong I just go back and modify everything to use the other one.

You can always use Strong Induction if you want but, it might save you time to use just the Principle of Mathematical Induction. They are equivalent of course, but that is a non-trivial exercise.

Proof Using Mathematical Induction

So if we're going to prove this by induction, we need three things: we need a base case, an induction hypothesis, and then the induction step.

Base Case

So let's start with the base case. So for $n=1$, we have that $f(1)=1 < \displaystyle\frac{7}{4}$. Okay so base case is easy.

Induction Hypothesis

Assume that $f(k) <\left(\displaystyle\frac{7}{4}\right)^k$ for some $k\in\mathbb{N}$.

So our base case is done and the induction hypothesis we're going to assume it's true for some $k$.

Induction Step

Now we're going to do the induction step. So for $k+1$, we have

$$f_{k+1}=f_k+f_{k-1}$$

But this is valid only when $k+1 \geq 3$. So this is only valid when $k\geq 2$, then we know we're going to need at least one more base case because I mean here we have that $k$ could be $1$ and then we would have

$$f_{2}=f_1+f_{0}$$

And $f_0$ doesn't really make sense. So we're going to need to do at least one more base case, so let's add that in now.

Additional Base Case

So for $n=2$, we have that $f(2)=1<\displaystyle\frac{49}{16}=\left(\frac{7}{4}\right)^2$.

Okay so now we have our two base cases.

Adjustment of Induction Hypothesis

So now in our induction hypothesis, well we already know that $1$ and $2$ are true, so we can actually additionally suppose here that $k\geq 2$.

Adjustment of Induction Step

So now this step here, $f_{k+1}=f_k+f_{k-1}$, well this is valid since $k+1 \geq 3$. But now, as you've noticed, now we're going to have to try to use just the fact that $f_k <\left(\displaystyle\frac{7}{4}\right)^k$, and that's not enough. We also need that $f_{k-1} < \left(\displaystyle\frac{7}{4}\right)^{k-1}$ if we're going to try to make any progress with this question.

So what do we do now? Well now we know that we need to use Strong Induction, so we're going to go back to the top and we're going to fix this up by using Strong Induction.

Proof Using Strong Induction

We proceed by Strong Induction. Our base cases don't change so we don't have to worry about that.

Induction Hypothesis

Now our induction hypothesis is wrong. Now we're going to assume that instead of $f_k < \left(\displaystyle\frac{7}{4}\right)^k$, we're going to assume that $f_i < \left(\displaystyle\frac{7}{4}\right)^i$ for all $1\leq i\leq k$ for some $k\in\mathbb{N}$ and $k\geq 2$.

We've already proven two base cases so there's no loss of generality in assuming that $k\geq 2$.

Induction Step

Now from here, what are we going to do? Well now we can use the induction hypothesis. What's our goal? We want to show $f_{k+1}<\left(\displaystyle\frac{7}{4}\right)^{k+1}$. $$\begin{align*} f_{k+1}&=f_k+f_{k-1}&&\text{Valid since}\,k+1\geq 3\\ &<\left(\frac{7}{4}\right)^k+\left(\frac{7}{4}\right)^{k-1}&&\text{Induction Hypothesis} \end{align*}$$

So now that we're at this step, right, usually the tricks in induction are either add $0$, multiply by $1$, or factor/expand. In this case, factoring seems like the most natural thing to do since something is in common.

$$\begin{align*} f_{k+1}&=f_k+f_{k-1}&&\text{Valid since}\,k+1\geq 3\\ &<\left(\frac{7}{4}\right)^k+\left(\frac{7}{4}\right)^{k-1}&&\text{Induction Hypothesis}\\ &=\left(\frac{7}{4}\right)^{k-1}\left(\frac{7}{4}+1\right)\\ &=\left(\frac{7}{4}\right)^{k-1}\left(\frac{11}{4}\right) \end{align*}$$

Now we want to show that $f_{k+1}<\left(\displaystyle\frac{7}{4}\right)^{k+1}$. Here we only have $\left(\displaystyle\frac{7}{4}\right)^{k-1}$, so the other $2$ better come from this $\displaystyle\frac{11}{4}$.

Now if this is going to work, then we need that $\displaystyle\frac{11}{4}<\frac{7^2}{4^2}=\frac{49}{16}$

How do we check this? Well we do the following:

$$\begin{align*} \frac{11}{4}<\frac{49}{16}&\Leftrightarrow\frac{11\cdot 16}{4}< 49\\ &\Leftrightarrow 44 < 49 \end{align*}$$

So these were all “if and only if’s” so you can go in either direction of this proof, and so we actually have the thing that we want to be true, since the final line is true. Now you don't need to show this, but let's now just write down the result that we want:

$$\begin{align*} f_{k+1}&=f_k+f_{k-1}&&\text{Valid since}\,k+1\geq 3\\ &<\left(\frac{7}{4}\right)^k+\left(\frac{7}{4}\right)^{k-1}&&\text{Induction Hypothesis}\\ &=\left(\frac{7}{4}\right)^{k-1}\left(\frac{7}{4}+1\right)\\ &=\left(\frac{7}{4}\right)^{k-1}\left(\frac{11}{4}\right)\\ &<\left(\frac{7}{4}\right)^{k-1}\frac{49}{16}\\ &=\left(\frac{7}{4}\right)^{k-1}\frac{7^2}{4^2}\\ &=\left(\frac{7}{4}\right)^{k+1} \end{align*}$$

Thus, $f_{k+1}<\left(\displaystyle\frac{7}{4}\right)^{k+1}$ and hence, the statement $f_n < \left(\displaystyle\frac{7}{4}\right)^n$ is true for all $n\in\mathbb{N}$ by Strong Induction. $\quad\blacksquare$

Summary

Okay so let's back up and just sort of summarize what we did. So our statement that we were trying to show here. The statement we were trying to show is that $f_n < \left(\displaystyle\frac{7}{4}\right)^n$. We're going to proceed by Strong Induction, which we saw by trying to do the proof.

We need two base cases, again this was an artifact of the proof. You could also kind of justify it by the fact that we had to go back two previous terms, so you might want to use two base cases.

Base cases are very easy to show, just plug in $1$ into both sides of the inequality and show that it's correct. Really you should start from the left-hand side show that it's less than the right-hand side. Or vice versa, but in this case I want to go in this direction.

So for $n=2$, we have $f(2)=1<\displaystyle\frac{49}{16}=\left(\frac{7}{4}\right)^2$. So now our induction hypothesis that we're going to assume the claim is true for all $1\leq i \leq k$ for some $k\in\mathbb{N}$, and we're going to make sure that $k\geq 2$, since we have two base cases that's not a concern for us.

The induction step we now want to show that $f_{k+1}<(\displaystyle\frac{7}{4})^{k+1}$. So for $k+1$, we're just going to plug it in. We're going to use the recursive definition which is valid since $k+1\geq 3$. Then we use the induction hypothesis, or induction hypotheses, to show that $f_k$ and $f_{k-1}$ is less than $\displaystyle\left(\frac{7}{4}\right)^k$ or $\displaystyle\left(\frac{7}{4}\right)^{k-1}$ respectively.

Factor, simplify, $\displaystyle\frac{11}{4} < \frac{49}{16}$, we saw that in the aside we did. $\displaystyle\frac{49}{16}=\frac{7^2}{4^2}$, and the reason why we picked $\displaystyle\frac{49}{16}$ was so that we can get the extra two values of $\displaystyle\frac{7}{4}$ that we needed.

Thus the induction step is true and hence the statement is true for all natural numbers $n$ by Strong Induction. And that's what we wanted to show.

So hopefully this gives you a little bit of idea of when to Strong or Weak Induction, how many base cases to use, and how to go through the proof of such an example.

I apologize this video is very long, but induction examples do take a little bit of time to explain and get used to in the beginning. After a little bit of time hopefully this kind of example will just be very routine for you, but it will take a little bit of practice and effort to get to that point. So thank you very much for listening and good luck.