I know there is recurence solution, but thats not what I am interested in, I want pure combinatorial solution, similar to this post. What I tried and started with but never realy finished was:
I know all count of all ternary strings is $3^n$ where n is length of string, so my plan is to subtract $T_n$ from $S_n$ where $T_n$ is number of all ternary strings with "00" substring, I am only able to count part of $T_n$ as it is very problematic since many of those cases overlap. Maybe I am supposed to use inclusion/exclusion principle but I dont know how to use it exactly, I am only aware that something like that exist and maybe could be useful here, but even there you have to count those overlappign cases.
Anyone could give me a hit how to solve it without any recursion ?