Setting up a recurrence relation of ternary strings of length n that does not have three consecutive 1s

Question

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.

Answer 1

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.

Answer 2

Generating Function

Let's build the generating function of the number of $n$ length bit strings that don't have $3$ ones in a row. We can do this by starting with $1+x+x^2$ representing $0$, $1$, or $2$ ones. Then we will have $0$ or more molecules consisting of $2$ atoms: an atom consisting of $1$ or more zeros and twos, and an atom consisting of $1$ or $2$ ones. There are $2^k$ atoms of zeros and twos that have length $k$. Thus, the generating function for $1$ or more would be $$ \sum_{k=1}^\infty(2x)^k=\frac{2x}{1-2x} $$ The generating function for the atom of $1$ or $2$ ones is $x+x^2$. Then there is a final atom of $0$ or more zeros and twos, giving a generating function of $$ \sum_{k=0}^\infty(2x)^k=\frac1{1-2x} $$ We can get any valid pattern in a unique way by summing $$ \begin{align} &\overbrace{\left(1+x+x^2\right)\vphantom{\left(\frac11\right)^k}}^{\text{initial ones}}\sum_{k=0}^\infty \overbrace{\left(\frac{2x}{1-2x}\left(x+x^2\right)\right)^k}^{\substack{\text{arbitrary number of}\\\text{zeros and twos followed by ones}}}\overbrace{\frac1{1-2x}\vphantom{\left(\frac11\right)^k}}^{\substack{\text{final}\\\text{zeros and twos}}}\\ &=\left(1+x+x^2\right)\frac1{1-\left(\frac{2x}{1-2x}\right)\left(x+x^2\right)}\frac1{1-2x}\\ &=\bbox[5px,border:2px solid #C0A000]{\frac{1+x+x^2}{1-2x-2x^2-2x^3}}\\[6pt] &=1+3x+9x^2+26x^3+76x^4+222x^5+\dots \end{align} $$ Thus, we get $a_0=1$, $a_1=3$, and $a_2=9$. For $n\gt2$ we can use the recursion indicated by the denominator: $$ \bbox[5px,border:2px solid #C0A000]{a_n=2a_{n-1}+2a_{n-2}+2a_{n-3}} $$ Representing A String By Atoms

The string "$\color{#C00000}{0220}11\color{#C00000}{2}1\color{#C00000}{2220}1$" is counted in the $k=3$ term: $$ \begin{align} &\small\overbrace{\left(1\color{#C0C0C0}{+x+x^2}\right)}^{\text{$0$ ones}}\overbrace{\overbrace{\left(\color{#C0C0C0}{2x+4x^2+8x^3+}16x^4\color{#C0C0C0}{+\dots}\right)}^{\text{$4$ zeros or twos}}\overbrace{\left(\color{#C0C0C0}{x+}x^2\right)}^{\text{$2$ ones}}}^{k=1} \overbrace{\overbrace{\left(2x\color{#C0C0C0}{+4x^2+8x^3+16x^4}\color{#C0C0C0}{+\dots}\right)}^{\text{$1$ zero or two}}\overbrace{\left(x\color{#C0C0C0}{+x^2}\right)}^{\text{$1$ one}}}^{k=2}\\ &\small\overbrace{\overbrace{\left(\color{#C0C0C0}{2x+4x^2+8x^3+}16x^4\color{#C0C0C0}{+\dots}\right)}^{\text{$4$ zeros or twos}}\overbrace{\left(x\color{#C0C0C0}{+x^2}\right)}^{\text{$1$ one}}}^{k=3}\overbrace{\left(1\color{#C0C0C0}{+2x+4x^2+8x^3+16x^4+\dots}\right)}^{\text{$0$ zeros or twos}}=512x^{13} \end{align} $$ Getting The Recursion From The Denominator

Suppose that $$ \sum_{k=0}^\infty a_kx^k=\frac{1+x+x^2}{1-2x-2x^2-2x^3} $$ Multiplying both sides by $1-2x-2x^2-2x^3$, gives $$ \left(1-2x-2x^2-2x^3\right)\sum_{k=0}^\infty a_kx^k=1+x+x^2 $$ Equating the coefficient of $x^n$ on both sides, for $n\gt2$, we get $$ a_n-2a_{n-1}-2a_{n-2}-2a_{n-3}=0 $$ which gives the recursion $$ a_n=2a_{n-1}+2a_{n-2}+2a_{n-3} $$