The problem is: Find the number of binary strings (strings composed of just $1$s and $0$s) of length $n$ such that the substrings "$111$" and "$101$" are not contained within them.
In this question, $n$ can be up to $10^{18}$, and the code must finish in two seconds (C++, around $4 \cdot 10^8$ computations).
I found a way to use recurrences that can do up to around $n = 10^7$, but clearly this was not enough.
Let's look at this as "How many binary strings do not contain two $1$s with exactly one space separating them".
The amount of new strings added with each additional $n+1$ is proportional to the $(0/1)$ ratio of the number $n-1$ (considering all valid strings of length $n$) and is in turn the proportion of $(0/1)$ at $n+1$ itself effecting the strings added at $n+3$.
In other words$$ n+1 = (n) (1+ {0_{n-1}\over n}) $$ where $0_{n-1}$ just means the number of strings of length $n$ with an $0$ at the $n-1$ spot.
For $n=3,4$ we double only the strings that have a $0$ in the first or second spot respectively so we multiply by $3 \over 2$ . For $n=5,6$ we double ${2 \over 3}$ of our strings so we multiply by $5 \over 3$.
i.e. for $n=11$ we have $${2 \over 1} \cdot {2 \over 1}\cdot {3 \over 2} \cdot {3\over 2} \cdot {5 \over 3} \cdot {5 \over 3} \cdot {8 \over5 } \cdot {8\over 5} \cdot {13 \over 8} \cdot {13 \over 8} \cdot {21 \over 13}= 273$$
The Fibonacci sequence. Since everything cancels out except the final two terms the solution is simply the product of the final two numerators.
$\implies $ When $n$ is even the solution is the square of the ${n \over2}+2$ term of the Fibonacci sequence $$(F_{{n \over 2}+2})^2$$
$\implies$When $n$ is odd the solution is the product $$F_{{n+1\over 2}+2} \cdot F_{{n-1\over 2}+2} $$
EDIT
What if we simplify the question and just ask how many binary strings of length $n$ do not contain the substring $11$?
Now to calculate $n+1$ we use the (0/1) ratio of $n$ itself. $$n+1 = (n)(1+{0_n\over n})$$ which gives us $${2 \over 1} \cdot {3 \over 2} \cdot {5 \over 3} \cdot {8 \over5 } \cdot {13 \over 8} \cdot {21 \over 13}...$$ so our final solution will just be $$F_{{n}+2}$$ Which seems a nice way of getting the fibonacci sequence while avoiding the moral dilemmas of experimenting on rabbits.
Please feel free to edit this...