Let $A_n$ denote set of strings over characters $\left\{0,1,2\right\}$ of length $n$ which do not contain substring $22$. Moreover let $B_n$ denote set of strings which both do not contain substrings $21$, $22$ and do not end with $2$.
- Find out how many of $2$ characters at most could strings from $A_n$ and $B_n$ contain. Then combinatoricaly devise nonrecurrent formulae for cardinalities $a_n = \lvert A_n \rvert$ and $b_n = \lvert B_n \rvert$.
- Devise recurrent formulae for $a_n$ and $b_n$. For these two linear equations with constant coefficients figure out initial conditions and solve them.
I see that most dense $A_n$ strings follow $2␣2␣2…$ pattern, so there will be $\left \lceil{\frac{n}{2}}\right \rceil$ $2$’s in string of length $n$. $B_n$ strings looks like $202020…$, so there will be $\left \lfloor{\frac{n}{2}}\right \rfloor$ $2$’s in string of length $n$.
But how do I make formulae out of this observation?
As you know $$A_0 = \left\{ε\right\}$$ $$A_1 = \{0, 1, 2\}$$ initially then we can define the recurrence relation for A like this:
$$A_n = \{x.y\ |\ x\in A_{n-1}, y \in \{0,1\}\} \cup \{x.y.\{2\} | x \in A_{n-2}, y\in\{0,1\}\}$$ where .(dot) is concatenation operator
lets think why;
a string in $A_n$ must end with a $0$, $1$ or $2$ so we can add $0$ and $1$ directly without violating the rule for $A_n$ but we can add $2$ only after adding one of $\{0,1\}$
so
$$a_n = 2a_{n-1} + 2a_{n-2}$$ and if you solve that relation:
$$x^2 = 2x + 2$$ $$x = 1\mp\sqrt{3}$$
so you get: $$a_n = c_1*(1+\sqrt{3})^n + c_2*(1-\sqrt3)^n$$ and we know that $a_0=1, a_1=3$ you can solve this equation to get values for $c_1$ and $c_2$
you can solve the $B$ part of the problem by the same logic if you run into any trouble ask again :)