Recursive induction for a sequence.

Question

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 1

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.