I've seen many posts regarding this topic but have not seen a structured and full inductive proof of this. While I fully understand the recurrence relation and the set theory behind the relation, how would you concisely lay this down into a formal inductive proof? My trouble is for $F_{(n+1)+2}$=$F_{n+3}=F_{n+1}+F_{n+2}$ I'm not sure how to express the two previous terms. By the base case and our assumption we know both are true… but what's the most concise way to express them?
Here's my attempt.
Prove that the number of $n$-digit binary numbers that have no consecutive $1$'s is the Fibonacci number $F_{n+2}$.
$Proof.$ We will prove this using mathematical induction.
Base Case. When $n=1$ we consider a $1$-digit binary string and we see that we can form exactly $2$ strings that meet the restriction of no consecutive $1$'s. These strings are contained in our set $A=\{(0),(1)\}$. Now notice $F_{n+2}=F_{3}=2$ and $\left\vert{A}\right\vert=2$.
When $n=2$ we consider a $2$-digit binary string and we see that we can form exactly $3$ strings that meet our restriction of no consecutive $1$'s. These strings are contained in our set $B=\{(00),(01),(10)\}$. Notice again that $F_{n+2}=F_{4}=3$ and $\left\vert{B}\right\vert=3$.
When $n=3$ we consider a $3$-digit binary string and we see that we can form exactly $5$ strings that meet our restriction of no consecutive $1$'s. These strings are contained in our set $C=\{(000),(100),(001),(010),(101)\}$. Notice here that $F_{n+2}=F_5=5$ and $\left\vert{C}\right\vert=5$.
Finally, we see that the sum of the cardinalities of the two previous terms give us the cardinality of the next term in our sequence. Thus $\left\vert{C}\right\vert=\left\vert{B}\right\vert+\left\vert{A}\right\vert.$
Inductive Step. Now consider $n\ge3$ and suppose that our proposition holds for any number $k$ such that $0\le k\le n$. Then observe that
$F_{(n+1)+2}=F_{n+3}=F_{n+2}+F_{n+1}=\left\vert F_{n+2} \right\vert+\left\vert F_{n+1}\right\vert=\left\vert F_{n+3}\right\vert$.
Best Answer
Your base case is overkill: for your base case you need only two consecutive values, not three. If you start with $n=1$, you need to check $n=1$ and $n=2$. However, you can do better. The only string of length $0$ is the empty string, which does not have consecutive $1$s, so there is $1=F_{0+2}$ such string. That is, the result holds for $n=0$, so your base case can be $n=0$ and $n=1$.
Your induction step, however, doesn’t prove anything, I’m afraid. Let $a_n$ be the number of binary strings of length $n$ that do not contain consecutive $1$s. The theorem is that $a_n=F_{n+2}$ for each $n\ge 0$. Your induction step should therefore be to show that the induction hypothesis that $a_n=F_{n+2}$ and $a_{n-1}=F_{(n-1)+2}=F_{n+1}$ implies that $a_{n+1}=F_{(n+1)+2}=F_{n+3}$. You’ve said nothing about the numbers $a_n$, which are the objects of actual interest; you’ve merely said that $F_{n+3}=F_{n+2}+F_{n+1}$, which we already knew. The actual argument for the induction step requires that you have already proved that the numbers $a_n$ satisfy the recurrence $a_{n+1}=a_n+a_{n-1}$. Once you have that, it goes as follows:
$$\begin{align*} a_{n+1}&=a_n+a_{n-1}\\ &=F_{n+2}+F_{(n-1)+2}\\ &=F_{n+2}+F_{n+1}\\ &=F_{n+3}\\ &=F_{(n+1)+2}\;, \end{align*}$$
as desired. Here the first step is the known recurrence for the $a_n$, the second uses the induction hypothesis, the third is algebra, the fourth uses the Fibonacci recurrence, and the last is again algebra.
This argument shows why the base case requires only the first two values: the induction argument requires that we know the truth of the theorem for the previous two terms, since the recurrence is second-order. The induction argument itself tells us that the theorem is true for $n=3$ if it’s true for $n=2$ and $n=1$, so there’s no need to add $n=3$ to the base case.