Let $f(n)$ be the number of binary strings with length as $n$ that they do not contain a sub-string as “$010$” nor “$101$”. Prove that for $n\ge 3$: $f(n)=f(n-1)+f(n-2)$ 🔑
Proof: For $n=1$, we have $2$ possible binary strings, as $0$, and $1$. We have $f(1)=2$ as none of the $2$ possible binary strings containing $010$ or $101$.
For $n=2$, we have $4$ possible binary strings, as $00$, $01$, $10$, and $11$. We have $f(2)=4$ as none of the $4$ possible binary strings containing $010$ or $101$.
When $n=3$, there are $8$ possible binary strings, as $000$, $001$, $010$, $011$, $100$, $101$, $110$, and $111$. Excluding $010$ and $101$, we have $f(3)=6$.
Therefore, $f(n)=f(n-1)+f(n-2)$ when $n=3$.
For a binary string of length $n$ that does not contain a sub-string as $010$ nor $101$, the string can end up with a suffix as $00$, $01$, $10$, or $11$. Let $a(n)$, $b(n)$, $c(n)$, and $d(n)$ be the number of strings with length as $n$ that end up with a suffix as $00$, $01$, $10$, and $11$ respectively. Therefore $$f(n)=a(n)+b(n)+c(n)+d(n)$$ Additionally, we have the following relationships:
$$ \begin{array}{rcl} a(n)&=&a(n-1)+c(n-1)\\ b(n)&=&a(n-1)\\ c(n)&=&d(n-1)\\ d(n)&=&b(n-1)+d(n-1)\\ \end{array} $$Therefore
$$ \begin{array}{rcl} f(n)&=&a(n)+b(n)+c(n)+d(n)\\ \ &=&(a(n-1)+c(n-1))+a(n-1)+d(n-1)+(b(n-1)+d(n-1))\\ \ &=&(a(n-1)+b(n-1)+c(n-1)+d(n-1))+(a(n-1)+d(n-1))\\ \ &=&f(n-1)+((a(n-2)+c(n-2))+(b(n-2)+d(n-2)))\\ \ &=&f(n-1)+(a(n-2)+b(n-2)+c(n-2)+d(n-2))\\ \ &=&f(n-1)+f(n-2)\\ \end{array} $$Combining with the case when $n=3$, it is proved that $\boxed{f(n)=f(n-1)+f(n-2)}$.