Show that $a_n = 5a_{n-1} - 6a_{n-2}$ for all integers $n$ with $n \geq 2$

Question

Let $a_n = 2^n + 5 \cdot3^n$.

I'm having a hard time understanding the concept of iteration that needs to be applied to prove this.

I understand I can substitute the following:

$$a_n = 5(2^{n-1}+ 5 \cdot 3^{n-1})-6(2^{n-2}+ 5 \cdot 3^{n-2})$$

But I'm not clear on how to apply forward/backward substitution within the equation.

Answer 1

You are showing:

$$2^n+5(3^n)=5(2^{n-1}+5(3^{n-1}))-6(2^{n-2}+5(3^{n-2}))$$ Collate powers of $2$, you have: $$5(2^{n-1})-6(2^{n-2})$$ $$=5(2^{n-1})-3(2^{n-1})$$ $$=2(2^{n-1})=2^n$$ Now do the same for powers of $3$, so:

$$25(3^{n-1})-30(3^{n-2})=\ldots$$

Answer 2

$$a_n=5(2^{n-1}+5\times3^{n-1})-6(2^{n-2}+5\times3^{n-2})$$ $$a_n=5(2^{n-1}+5\times3^{n-1})-(2\times3)(2^{n-2}+5\times3^{n-2})$$ $$a_n=(5\times2^{n-1}+25\times3^{n-1})-(3\times2^{n-1}+10\times3^{n-1})$$ $$a_n=(5-3)\times2^{n-1}+(25-10)\times3^{n-1}$$ $$a_n=2\times2^{n-1}+15\times3^{n-1}$$ $$a_n=2\times2^{n-1}+3\times5\times3^{n-1}$$ $$a_n=2^{n}+5\times3^{n}$$

Answer 3

$$A=5(2^{n-1}+5\cdot 3^{n-1})-6(2^{n-1}\cdot2^{-1}+5\cdot 3^{n-1}\cdot 3^{-1})$$ $$=(5-6/2)2^{n-1}+(25-6\cdot5/3)3^{n-1}$$ $$=2\cdot 2^{n-1}+15\cdot 3^{n-1}$$ $$=2^{n}+5\cdot 3 \cdot 3^{n-1}$$ $$=2^{n}+5\cdot 3^{n}$$

Answer 4

Here is perhaps an over-explanation that should make it all clear. This is the way I would do this problem:

---

First, $a_0=1+5=6$, $a_1=2+15=17$, and $a_2=4+45=49$. Since $49=5\cdot 17-6\cdot 6$, the statement is true for $n=2$.

Now we want to show that the statement is true for all $n\ge 2$. The idea is to prove the implication which goes like $$\text{the statement holds for }n=k\implies \text{the statement holds for }n=k+1.$$

Then since the statement holds for $n=2$, it holds for $3$, and thus $4$, $5$, etc.

---

To that end, suppose that the statement holds for $n=k$. That is, suppose that $$a_k=5a_{k-1}-6a_{k-2}.$$ We know by definition that $a_{k+1}=2^{k+1}+5\cdot 3^k$. By assumption, we also know that $a_k=5a_{k-1}-6a_{k-2}$. We want to combine these to show that $a_{k+1}=5a_k-6a_{k-1}$. Well, by assumption, we can write $a_k=5a_{k-1}-6a_{k-2}$, so \begin{align} 5a_k-6a_{k-1}&=5(5a_{k-1}-6a_{k-2})-6a_{k-1}\\ &=25a_{k-1}-30a_{k-2}-6a_{k-1}\\ &=19a_{k-1}-30a_{k-2}\\ &=19(2^{k-1}+5\cdot 3^{k-1})-30(2^{k-2}+5\cdot 3^{k-2})\\ &=19(2^{k-1})-15(2^{k-1})+95(3^{k-1})-50(3^{k-1})\\ &=4(2^{k-1})+45(3^{k-1})\\ &=2^{k+1}+5\cdot 3^{k+1}\\ &=a_{k+1}. \end{align}

---

Aside: if you are confused about induction itself, its worth thinking through why it makes sense. The metaphor that made it immediately click for me was this: think of the proof as climbing an infinite ladder. The inductive step says "I can get from one rung to the next," and the base case says "I can get to the first rung."