How many binary arrays that have no $3$ consecutive $1$'s are there? Let $N$ be a positive integer. The function $f(N)$ indicates that how many of the binary arrays of length $N$ don't consist of $3$ consecutive $1$'s.
For example, if we'd have a look at $f(3)$: There are $8$ possible distinct arrays consisting of $0$'s and $1$'s. There is only "$111$" which is inappropriate for the rule. Therefore, the result is $7$.
Question: What is the formula of $f(N)$?
I tried something and found something work for $N <= 12$ before.
Let's look at $f(5)$. Let's say this array consists of 5 $x$'s which can be 0 or 1 for ease. We have $32$ possible arrays. Function wants us to find the ones which don't have consecutive $1$'s but again, for ease, I want to count them.
First possible array starts with $111xx$, there are $2 \times 2=4$ possibilities.
Second one starts with $x111x$ but if we say like that, if first $x$ is equal to $1$ we will be counting it once more because we already did it at the first array. So first $x$ has to be 0. So we are looking for $0111x$. So there are $2$ possibilities.
And the last array is $x0111$ for the same reason which are only $2$ arrays.
So the result is $32-8 = 24$.
But if you keep going like that you will see that won't work for larger $N$'s.
 A: 
 This sequence is known as the Tribonacci numbers and it has several other recursive definitions and combinatorial interpretations.

It looks like the function $f(N)$ is suitable to be defined recursively. Thus, while reading the problem, I was thinking to myself: Given $f(1), f(2), ..., f(N),$ how can I calculate $f(N+1)$?
For convenience, let's call an array that is enumerated by $f$ "a good array." Notice that all good arrays of length $N+1$ contain a good array of length $N$: the first $N$ digits. Therefore, it is a promising strategy to focus on the following question: How can we obtain all good arrays of length $N+1$ from the set of good arrays of length $N$?
If a good array of length $N$ ends with $11,$ there is only one way to obtain a good array of length $N+1$: appending $0$ to the end. Otherwise, appending $1$ will do it as well. How many good arrays of length $N$ that end with $11$ are there? Obviously, if $N=2$, the answer is $1.$ Otherwise, since the prefix $011$ is appended to a good array of length $N-3$, the answer is $f(N-3)$ (assuming $f(0) = 1$). Therefore, we have constructed our recursive formula: $$\begin{align} f(N+1) &= 2(f(N) - f(N-3)) + f(N-3) \\ &= 2f(N) - f(N-3).\end{align}$$
Given $f(0) = 1, f(1) = 2, f(2) = 4,$ and $f(3) = 7,$ you can compute all values of this function now.
