Prove that the total binary sequences of length n with no consecutive 1s is Fib(n+1) .

Question

I have seen multiple posts on how to prove this, but I don't understand why we need only Fib(n-1) and Fib(n-2) from the Fib series to prove it. Why do we only need Fib(n), Fib(n-1) and Fib(n-2)? How are these three elements in the series sufficient to tell total sequences of valid binary strings? Why can't we have something like Fib(n) = Fib(n - 1) + Fib(n - 2) + C*Fib(n-3) +...

Answer 1

Define $a_n$ as the number of $n$-sequences that ends with $1$ and $b_n$ the number of $n$-sequences that ends with $0$. It is easy to see that $b_{n+1}=a_n+b_n$ and $a_{n+1}=b_n$. From the second one we conclude that $b_{n+1}=b_n+b_{n-1}$ and that defining $$c_n:=b_n+a_n=b_{n+1}$$ we conclude what we want.