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.
Best Answer
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.