Hello Moni, ... I hope this can explain a little bit on why it is related to Fibonacci sequence, ...
We all know from problem-statement that we finally reduce the problem to finding the number of all binary-strings of length n that don't have consecutive ones.
Let f(n) = number of binary-strings of length n that don't have consecutive ones.
We can split f(n) by two smaller functions:
-> f0(n) -> finds the number of strings that start with '0'.
-> f1(n) -> finds the number of strings that start with '1'.
Let's consider f1(n) ... If the string starts with '1', clearly the next digit has to be '0'. So, the strings are fixed to "10????..."
Starting from s until s[n-1], the values are chosen so there is no consecutive ones. That means it is the same as calculating f(n-2) ...
f0(n) is even simpler. Since it starts with '0' ... the next digit can be either '0' or '1' ... So, the strings are only fixed to this pattern "0????..." and the rest should be chosen in such a way so that no consecutive ones are found. It's the same as calculating f(n-1).
Finally, we can see right away that f(n) = f(n-2) + f(n-1) ... which is Fibonacci sequence.
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).