Proof of explicit formula for recursive sequence by induction

Question

I am new to proof-writing and have just started working on Math for Computer Science on MIT OCW. I encountered the following problem on one of the assignments and would like feedback on my proof.

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\geq2.$ Prove that for all $n \in \mathbb{N}, G_{n}=3^{n}-2^{n}$.

Proof by Induction:

Base Case: We first check that the hypothesis is true for $n=0$ and $n=1$.

$$3^{0}-2^{0}=1-1=0=G_{0} \\ 3^{1}-2^{1}=3-2=1=G_{1}$$ Inductive Step: Assume that $G_{n}=3^{n}-2^{n}$ for all $n \in \mathbb{N}$, for purposes of induction. $$\begin{align*} \displaystyle G_{n+1}&=5G_{n}-6G_{n-1} \\ &=5(3^{n}-2^{n})-6(3^{n-1}-2^{n-1}) \\ &=5\cdot3^{n}-5\cdot2^n-2\cdot 3 \,\cdot3^{n-1}+3\,\cdot2 \, \cdot2^{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} \tag*{$\blacksquare$} \end{align*} $$ So I have a few specific questions regarding my proof.

1. Did I do the base case right and is it connected to the inductive step? I was confused by how the recursive definition applies for $n\geq2$ and the explicit formula applies for all $n$ so I wasn't really sure what my base case should be.
2. In a formal proof, do you have to state the hypothesis in predicate logic? Also, how would you do that here?
3. How did they derive the explicit formula for this problem? Or more generally, how do you derive the explicit formula for a recursively-defined sequence? I understand that this probably requires a long answer, so even resources on the topic would be appreciated.
4. Any other feedback on my proof would be greatly appreciated.

Answer 1

Your base case is correct. There is a fundamental error at the beginning of your induction step, however: when you assume that $G_n=3^n-2^n$ for all $n\in\Bbb N$, you are assuming precisely the result that you’re supposed to be proving, which makes your argument circular. What you should be assuming as your induction hypothesis is that $G_k=3^k-2^k$ for all $k\le n$; then you’ll use that hypothesis to show that $G_{n+1}=3^{n+1}-2^{n+1}$, using exactly the calculation that you in fact made. In that calculation you used the induction hypothesis when you replaced $G_n$ by $3^n-2^n$ and $G_{n-1}$ by $3^{n-1}-2^{n-1}$. (In fact you didn’t need the whole induction hypothesis that the result is true up through $n$: you needed only the last two cases, $n-1$ and $n$.) It wouldn’t be a bad idea to conclude the argument by saying something like The result now follows by induction.

In ordinary mathematical practice a proof is not written in formal logical formalism: it is a piece of prose, written in paragraphs of sentences. Yes, some of those sentences are mostly mathematical notation, but the whole thing should be a connected narrative.

Finding closed forms for sequences defined by recurrences is a big subject. This Wikipedia article and its references are a starting point; the book Concrete Mathematics by Graham, Knuth, and Patashnik has a great deal of useful information, though it deals with many other topics as well. The book generatingfunctionology by Herbert S. Wilf is heavier going but has a great deal of information on the use of generating functions to solve recurrences and is freely available here.