Prove using induction or strong induction.

Question

Let the sequence $G_0, G_1, G_2, . . .$ be defined recursively as follows: $G_0 = 0, G_1 = 1$, and $$G_n = (5 G_{n-1}) − (6 G_{n-2})$$ for every n belongs to N, n ≥ 2.

Prove using induction or strong induction that for all n belongs to N, $G_n = 3^n − 2^n$.

Answer 1

First, show that this is true for $n=0,1$:

$G_0=3^0-2^0$

$G_1=3^1-2^1$

Second, assume that this is true for all $k \leq n$:

$G_0=3^0-2^0$

$G_1=3^1-2^1$

$\dots$

$G_{n-1}=3^{n-1}-2^{n-1}$

$G_n=3^n-2^n$

Third, prove that this is true for $n+1$:

$G_{n+1}=$

$5\cdot\color\red{G_n}-6\cdot\color\green{G_{n-1}}=$

$5\cdot(\color\red{3^n-2^n})-6\cdot(\color\green{3^{n-1}-2^{n-1}})=$

$5\cdot3^n-5\cdot2^n-2\cdot3^n+3\cdot2^n=$

$3\cdot3^n-2\cdot2^n=$

$3^{n+1}-2^{n+1}$

---

Please note that the assumption is used only in the parts marked red and green.

Answer 2

Prove its true for G(2), and write G(k+1) in terms of G(k) and G(k-1), G(k) and G(k-1) both satisfy $ 3^n - 2^n $, substitute and solve.