Prove by induction of recursive sequence

Question

My classmates and I were working on this question on our discrete mathematics homework, but we can't figure it out. We are asked to consider the following recurrence:

\begin{equation*} G_0 = 0; G_1 = 1; \\ G_n = 7G_{n-1} - 12G_{n-2} \end{equation*}

for $n \geq 2$.

We have to prove that $G_n = 4^n - 3^n$.

Now, I know that this has to be done by some sort of strong induction. The way I'm approaching it right now is that I have two base cases, $n = 2$ and $n = 3$. After proving that those base cases work, I assume that the hypothesis holds true for some $n$ and $n+1$. Then I try to prove that it holds true for $n+2$, but I'm running into some trouble doing that. If I could get some guidance for this problem that would be really helpful.

Thanks!

Answer 1

Suppose that this is true for every $k\leq n+1$, For $n+2$ you have $G_{n+2}=7G_{n+1}-12G_n=7(4^{n+1}-3^{n+1})-12(4^n-3^n)$. So

$$G_{n+2}=7\cdot 4^{n+1}-3\cdot 4^{n+1}-7\cdot 3^{n+1}+4\cdot 3^{n+1}=4^{n+2}-3^{n+2}.$$

Answer 2

First note that your base cases are $n=0$ and $n=1$. The formula $G_n=4^n-3^n$ holds for all $n\ge0$. It is only the recurrence $G_n=7G_{n-1}-12G_{n-2}$ that is defined for all $n\ge2$ (since $G_0$ and $G_1$ were defined explicitly).

Once you have checked these two cases hold, then assume that the result holds for all $n\le k$ for some integer $k\ge 0$. Then when $n=k+1$ we have:

$$ \begin{split} G_{k+1}=7G_{k}-12G_{k-1} &= 7\cdot (4^{k}-3^{k})-12\cdot (4^{k-1}-3^{k-1}) \\ &= 7\cdot 4^k-12\cdot 4^{k-1}+12\cdot 3^{k-1}-7\cdot 3^{k} \\ &= 4^{k-1}\cdot (28-12)+3^{k-1}\cdot (12-21) \\ &= 4^{k-1}\cdot 16+3^{k-1}\cdot (-9) \\ &= 4^{k+1}-3^{k+1} \end{split} $$

which is what we required. So the result holds for all $n\ge 0$ by induction.