Is my proof, by strong induction, of for all $n\in\mathbb{N}$, $G_n=3^n-2^n$ correct?

Question

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\mathbb{N}, n\ge2$.

Prove that for all $n\in\mathbb{N}$, $G_n=3^n-2^n$.

---

Proof. By strong induction. Let the induction hypothesis, $P(n)$, be $G_n=3^n-2^n$

Base Case: For $(n=0)$, $P(0)$ is true because $3^0-2^0 =0$

For $(n=1)$, $P(1)$ is true because $3^1-2^1=1$

Inductive Step: Assume that $P(n-1)$ and $P(n-2)$, where $n\ge2$, are true for purposes of induction.

So, we assume that $G_{n-1}=3^{n-1}-2^{n-1}$ and $G_{n-2}=3^{n-2}-2^{n-2}$, and we must show that $G_{ n }=3^{ n }-2^{ n }$.

Since we assumed $P(n-1)$ and $P(n-2)$, we can rewrite $G_n=5G_{n-1}-6G_{n-2}$ as $G_n=5(3^{n-1}-2^{n-1})-{ 6 }(3^{n-2}-2^{n-2})$

So, we get:

$\Rightarrow G_n=5\cdot 3^{ n-1 }-5\cdot 2^{ n-1 }-(\frac { 6 }{ 3 } \cdot 3^{ n-1 }-\frac { 6 }{ 2 } \cdot 2^{ n-1 })$

$\Rightarrow G_n=5\cdot 3^{ n-1 }-5\cdot 2^{ n-1 }-2\cdot 3^{ n-1 }+3\cdot 2^{ n-1 }$

$\Rightarrow G_n=5\cdot 3^{ n-1 }-2\cdot 3^{ n-1 }-5\cdot 2^{ n-1 }+3\cdot 2^{ n-1}$

$\Rightarrow G_n=3\cdot 3^{ n-1 }-2\cdot 2^{ n-1 }$

$\Rightarrow G_n=\frac { 1 }{ 3 } \cdot 3\cdot 3^n-\frac { 1 }{ 2 } \cdot 2\cdot 2^n$

$\Rightarrow G_n=3^n-2^n$

---

The only real issue I have at this point is that I don't know how to properly conclude this proof with a final statement. A hint/guidance in that regard would be much appreciated.

In addition, please feel free to offer advice and/or constructive criticism about my proof.

Answer 1

You have the right idea, but there are some minor points that need correction.

The strong induction principle in your notes is stated as follows:

Principle of Strong Induction $\ $ Let $\,P(n)\,$ be a predicate. If

• $\ P(0)$ is true, and

• for all $\,n\in \Bbb N,\ P(0), P(1),\ldots, P(n)\,$ together imply $\,P(n\!+\!1)\,$ then $\,P(n)\,$ is true for all $\,n\in\Bbb N$

Your $\,P(n)\,$ is $\, G_n = 3^n - 2^n.\,$ You have verified that $\,P(0)\,$ is true.

Your induction hypothesis is that $\,P(k)\,$ is true for all $k \le n.\,$ You have essentially shown that $\,P(n\!-\!1),P(n)\,\Rightarrow\,P(n\!+\!1)\,$ but that only works for $\,n\ge 1$ (else $\,P(n-1)\,$ is undefined). Thus you need to separately verify $\,P(1)\,$ (to be pedantic, this is part of the inductive step, not the base case, according to the above formulation of strong induction, though that is a somewhat arbitrary distinction)

It is illuminating to observe that the recurrence in the induction is a special case of

$$ a^{n+1}-b^{n+1} =\, (a+b)(a^n-b^n) -ab (a^{n-1} - b^{n-1})$$

which can be verified directly or derived from the fact that $\,a,b\,$ are roots of

$$(x\!-\!a)(x\!-\!b) = x^2\! - (a\!+\!b) x + ab\,\Rightarrow\, x^{n+1}\! = (a\!+\!b)\,x^n - ab\, x^{n-1}$$

The proof will be simpler (and more insightful) if you work with this general case, i.e. prove that $\,f_n = a^n - b^n\,$ satisfies $\,f_{n+1} = (a+b) f_{n} - ab f_{n-1},\ f_0 = 1,\ f_1 = a-b\,$ for all $\,n\ge 0.\,$ Then your problem is just the special case $\,a,b = 3,2,\,$ and the inductive step is much clearer.

Answer 2

Yes, your proof is perfectly fine. Good job! You can write something like "The assertion follows.". But honestly it isn't necessary since it is in this case pretty simple for readers to see where the proof is complete (after the inductive step).