Processing math: 100%

Fall 2000 Exam Question 3

Hello everyone. In this video, we're going to talk about the 2000 exam, and we're going to start with question $3$.

Question: Let $a_1=2$, $a_2=3$ and $a_n=3a_{n-1}-2a_{n-2}$ for $n\geq 3$. Show that $a_n=2^{n-1}+1$ for $n\geq 1$.

Solution

So when you see a question like this, it feels pretty natural to use some sort of induction. Because I'm going back twice, I think I'm going to use Strong Induction to prove this, and especially since I have the condition for $n\geq 3$, I definitely want at least two base cases to account for this fact. You'll see where all this comes into play when you write the proof, but for now, let's just actually go through it.

Base Cases

For $n=1$ and $n=2$,

$$a_1=2=2^{1-1}+1\\\\ a_2=3=2+1=2^{2-1}+1$$

So the claim definitely holds for the first two values.

Induction Hypothesis

Now for the induction hypothesis, so because I'm using Strong Induction, I'm going to assume that $a_i=2^{i-1}+1$ for all $i\in\{1,2,...,k\}$ for some $k\in\mathbb{N}$, $k\geq 2$.

Now why do I add this extra restriction $k\geq 2$? That's going to come through in the induction conclusion, okay, and the main reason for this is that I need to be able to use the recurrence relation at some point, which we'll see in a minute, and to use the recurrence relation, I need that $n\geq 3$.

So if I have $k\geq 2$, then $k+1\geq 3$, and I can use the recurrence, okay? That's why I need $k\geq 2$.

Induction Conclusion

So in the induction conclusion, now we're going to prove that $a_{k+1}=2^k+1$. Since $k+1\geq 3$, I can use the recursive definition to see that:

$$\begin{align*} a_{k+1}&=3a_k-2a_{k-1}\\ &=3(2^{k-1}+1)-2(2^{k-2}+1)&&\text{IH}\\ &=3\cdot 2^{k-1}+3-2^{k-1}-2\\ &=2\cdot 2^{k-1}+1\\ &=2^k+1 \end{align*}$$

So the IH step is why I needed to go back in time twice so that I could use the $a_k$ definition and the $a_{k-1}$. I need both of those to make this question work, so that's why I needed to have Strong Induction here.

Thus, the statement is true for $n=k+1$ and the claim is proven by POSI.

And that's it, okay? So just a quick recap. Okay, so again, Strong Induction, not weak induction because I need to go back twice. So you might not see this until you actually write down the induction conclusion step, but that's okay. If you notice a little late, just go back and correct it.

After using that and simplifying, that part's easy. So once you know to use Strong Induction, that's okay, and I need two base cases so that I can ensure that $k\geq 2$. So if I prove the first two base cases, then I can assume that $k\geq 2$ because I know that when $k=1$ and $k=2$, I already have the claim, okay? And that's it. So hopefully that gives you a little bit of an idea how to do an induction question, and good luck on the final.