discrete mathematics - Recursive induction for a sequence.

Here's the question I'm trying to prove. I'm just not certain how I should approach the inductive / constructor step.

Let the sequence $G_0, G_1, G_2, . . .$ be defined recursively as follows:
$G_0 = 0$, $G_1 = 1$, and $G_n = 5G_{n−1} − 6G_{n−2}$, for every $n \in \Bbb{N}, n \ge 2$.
Prove that for all $n \in \Bbb{N}, G_n = 3^n − 2^n$.

I think I have everything right until the induction step.

Theorem: $P(n)$ hold for all $n \in \Bbb{N}, n \ge 2$, $G_n=3^n-2^2$

Proof: By structural induction on the definition that $n \in \Bbb{N}$, when $n \ge 2$, $G_n = 3^n - 2^n$.

Base case: $P(2)$ holds since $$5G_{n-1}-6G_{n-2} = 5$$, and$$3^n-2^n= 9 -4 = 5$$

Inductive step: Suppose that $n \ge 2$ We must show that $P(n+1)$ hold, namely, that $n+1$ is also $3^n-2^n$. So assume that $P(n)$ is true. We know that $P(n+1) = 5G_{(n+1) - 1} - 6G_{(n+1) -2}$.

And that's right where I'm stuck. I'm not sure how to manipulate the formula in the inductive step to show it's equivalent to $3^n - 2^n$. Other than doing the manipulations in the inductive step, should I be using traditional induction or structural induction for recursive data?

Answer

The idea of using induction is to manipulate the known equations to derive the inductive step. In this problem, by following your equations and assuming $G_n = 3^n-2^n$ holds for all $n\leq k$, then we can see that $$G_{k+1} = 5G_k - 6G_{k-1} = 5\cdot 3^k-5\cdot 2^k-6\cdot 3^{k-1}+6\cdot 2^{k-1}$$
Notice $5\cdot 3^k - 6\cdot 3^{k-1} = 3^{k+1}$ and $-5\cdot2^k+6\cdot 2^{k-1} = -2^{k+1}$; hence, we may conclude that $$G_{k+1} = 3^{k+1}-2^{k+1}$$
The rest follows naturally.