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.
Here is a relevant, intuitive interpretation of the Padovan sequence, whose recurrence relation is
$\displaystyle P(n)=P(n-\color{red}2)+P(n-\color{red}3),$
corresponding with the condition that there ought be no $\color{red}2$ consecutive zeros and no $\color{red}3$ consecutive ones in your problem,
namely: $P(n)$ is the number of compositions of $(n + 2)$ in which each term is either $\color{red}2$ or $\color{red}3$.
For example, $P(6) = 4$, and there are $4$ ways to write $(6+2)=8$ as an ordered sum of $2$s and $3$s:
$8=2 + 2 + 2 + 2$
$8=2 + 3 + 3$
$8=3 + 2 + 3$
$8=3 + 3 + 2$
Nota bene that the above needs starting values
$P(0)=P(1)=P(2)=1$, which is different from OEIS' definition with
$P(0)=1$ and $P(1)=P(2)=0$
When offset by eight, OEIS' $P(n)$ is again giving the number of strings of length $(n-8)$ from a binary alphabet $\{0, 1\}$ with no more than one $0$ and no more than two $1$'s consecutively.