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.
- 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.
- In a formal proof, do you have to state the hypothesis in predicate logic? Also, how would you do that here?
- 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.
- Any other feedback on my proof would be greatly appreciated.