I've been struggling with this question for a bit, however here is the detail of the question- " a postman delivers mail to 19 terraced houses in a single row. He notices that no two adjacent houses ever get mail on the same day and that there are never more than two adjacent houses that do not receive mail on any day. What is maximum number of days that he can deliver mail before he repeats a mail delivery? "
I stared off using 5 houses and drew out houses he could/couldn't deliver too and got a maximum number of 6 days. (Not sure if this is right) I've been trying to identify a pattern to be able to solve it for 19 houses but have no clue!
Thanks!
I think the problem consists of counting the number of binary sequences containing no $000$ and no $11$ of length $19$, we call such a sequence a good sequence. This can be done using a recursion.
Let $f_n$ be the number of good sequences of length $n$ ending in $1$ and $g_n$ be the number of good sequence of length $n$ ending in $0$.
Then we have: $f_1=1,f_2=1,g_1=1,g_2=2$
We also have the following recursions for $n\geq 3$
$f_n=g_{n-1}$, This is beacause if a sequence ends in $1$, it ends in $01$.
We also have $g_n=f_{n-1}+f_{n-2}$. Because there are $f_{n-1}$ good sequences of length $n$ ending in $10$ and $g_{n-2}$ good sequences of length $n$ ending in $100$.
From here:
$$\begin{array} n && 1 && 2 && 3 && 4 && 5 && 6 && 7 && 8 && 9 && 10 && 11 && 12 && 13 && 14 && 15 && 16 && 17 && 18 && 19 \\ f_n && 1 && 1 && 2 && 2 && 3 && 4 && 5 && 7 && 9 && 12 && 16 && 21 && 28 && 37 && 49 && 65 && 86 && 114 && 151 && \\ g_n && 1 && 2 && 2 && 3 && 4 && 5 && 7 && 9 && 12 && 16 && 21 && 28 && 37 && 49 && 65 && 86 && 114 && 151 && 200 && \\ \end{array}$$
So the answer is $151+200=351$.