# Proof of explicit formula for recursive sequence by induction

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.
• Your proof looks good. To derive the formula, find the roots of the characteristic equation, which in this case is $x^2=5x-6$; cf. this Wikipedia resource about that Apr 26, 2020 at 18:37

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.