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?
We know that P(n+1)=
That should rather be $G_{n+1}\,$.not sure how to manipulate the formula in the inductive step
Substitute $G_n=3^n-2^n$ and $G_{n-1}= 3^{n-1}-2^{n-1}$ and work it out from there. $\endgroup$