1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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$ – dxiv Jun 6 '17 at 3:30
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.