Let $a_n$ denote " the number of ternary strings of length n that do not contain three consecutive 1s"
Ternary string contains only 0, 1, 2 and has length n. The way I approached it was to make a tree of length n:
Besides from my obvious lack of artistic skills, I find it very hard to believe that the recurrence relation is $ a_n = 26(a_{n-3}) $ . If anybody could tell me what I did wrong and help me out, that would be greatly appreciated.
Note: I realized that there are some possible duplicates on the site, which I have went through and either 1) do not apply to three consecutive (insert digit here)s or 2) I don't fully understand.
Best Answer
Let $T_n$ be the number of such strings, call them "good", of length $n$. The goal is to get a recursion for $T_n$. To do it, we'll distinguish between the various ways a "good" string might end. Specifically (reading from left to right):
Let $a_n$ denote the number of good strings that end in $01$
Let $b_n$ denote the number of good strings that end in $011$
Let $c_n$ denote the number of good strings that end in $21$
Let $d_n$ denote the number of good strings that end in $211$
Let $e_n$ denote the number of good strings that end in $0$
Let $f_n$ denote the number of good strings that end in $2$.
Clearly $$T_n=a_n+b_n+c_n+d_n+e_n+f_n$$
It is easy to read off that: $$T_1=3\;\;\;\;T_2=9\;\;\;\;T_3=26$$
Recursively, we pass from strings of length $n-1$ to those of length $n$ by appending one of the three digits. Visibly,
$$a_n=e_{n-1}\;\;\;\;b_n=a_{n-1}\;\;\;\;c_n=f_{n-1}\;\;\;\;d_n=c_{n-1}\;\;\;\;e_n=T_{n-1}=f_n$$
It follows at once that $$a_n=T_{n-2}=c_n\;\;\;b_n=T_{n-3}=d_n$$
Whence
$$T_n=2(T_{n-2}+T_{n-3}+T_{n-1})$$
And we are done.