The problem that I'm working on is:
How many binary strings (strings with only 0 or 1) of length 10 are there such that there are no 3 consecutive ones and no 2 consecutive zeros?
Let $a_n$ be the number of binary strings of length $n$ that satisfy the second condition (no 3 consecutive ones and no 2 consecutive zeros) and start with a $0$. Let $b_n$ be the number of binary strings of length $n$ that satisfy the second condition and start with a $1$. Let $c_n$ be the total number valid binary strings of length $n$. Let $a$ be a string that starts with $0$ and let $b$ be a string that starts with $1$.
$a = (0\ldots)$
The second digit in $a_n$ must be a $1$ because there cannot be $2$ consecutive zeros.
$a = 01\ldots$
If there is another zero, then we have started a binary string of length $n - 2$ that starts with a zero.
$a = 01(0\ldots)$
The number of such strings is $a_{n-2}$. If we have another $1$ instead of a $0$, then the next digit after the $1$ must be a $0$ because there cannot be three consecutive ones.
$a = 011(0\ldots)$
The number of such strings is $a_{n-3}$. Because we have considered all cases when the binary string starts with $0$, we know that $a_n = a_{n-2} + a_{n-3}$.
Now, let's build a relationship for $b_n$. First, we note that $b = (1\ldots)$. If there is a zero after that, then a one must follow that zero because there cannot be $2$ consecutive zeros.
$b = 10(1\ldots)$
We have formed another binary string of length $n - 2$ that starts with 1. There are $b_{n-2}$ such strings. If we have a $1$ instead of a $0$, then the next digit must be a $0$ because there cannot be $3$ consecutive ones.
$b = 110\ldots$
The next digit must be a $1$ because there cannot be 2 consecutive zeros.
$b = 110(1\ldots)$
We formed another binary string of length $n - 3$ that starts with a $1$. There are $b_{n - 3}$ such strings. We have considered all cases that start with a $1$, so we know that $b_n = b_{n - 2} + b_{n - 3}$.
Notice that $a_n + b_n = c_n$. We add together $a_n = a_{n - 2} + a_{n - 3}$ and $b_n = b_{n - 2} + b_{n - 3}$ to get $(a_n + b_n) = (a_{n - 2} + b_{n - 2}) + (a_{n - 3} + b_{n - 3})$. This means that $c_n = c_{n - 2} + c_{n - 3}$.
That is such a simple recursive equation, but I don't have any intuitive understanding why the equation would be true.
