Ternary strings with 3 or more consecutive 2's I'm trying to figure out how to find the number of ternary strings of length $n$ that have 3 or more consecutive 2's.
So far I've been able to establish that there is $n(2^{n-1})$ with a single 2.
And I think (but am not certain) that this can be extrapolated to the number of strings with a single group of 2's of length $x$ by:
$$\bigl(n-(x-1)\bigr)(2^{n-x})$$
What I'm getting caught on is the 'or more part', any help would be greatly appreciated.
 A: Denote by $c_n$ the number of ternary words containing no $222$. Then $c_1=3$, $c_2=9$, $c_3=26$, and we have the recursion
$$c_n=2c_{n-1}+2c_{n-2}+2c_{n-3}\qquad(n\geq4)\ .\tag{1}$$
Proof. An admissible word $w$ can begin with $Z$, $2Z$, or $22Z$ with $Z\in\{0,1\}$, followed by an admissible word $w'$.
Unfortunately the characteristic equation of $(1)$ has no rational roots, hence it remains to list the first few values:
$$(c_n)_{n\geq1}=(3, 9, 26, 76, 222, 648, 1892, 5524, 16128, 47088, 137480, 401392,\ldots)\ .$$
The values $a_n=3^n-c_n$ required by the OP then are
$$(a_n)_{n\geq1}=(0, 0, 1, 5, 21, 81, 295, 1037, 3555, 11961, 39667, 130049,\ldots)\ .$$
A: 
We consider the alphabet $V=\{0,1,2\}$ and we are looking for the number $c_n$  of strings of length $n$ having runs of $2$ less than three. The wanted  number is  $$a_n=3^n-c_n$$
We derive a generating function $C(z)=\sum_{n=0}^\infty c_nz^n$ from which the number $a_n$ can be obtained easily since
  \begin{align*}
a_n=[z^n]\left(\frac{1}{1-3z}-C(z)\right)\tag{1}
\end{align*}
  with $[z^n]$ denoting the coefficient of $z^n$ of a series.

Strings with no consecutive equal characters at all are called Smirnov or Carlitz words. See example III.24 Smirnov words from Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick for more information. 
A generating function for the number of Smirnov words over a ternary alphabet $V$ is given by
\begin{align*}
\left(1-\frac{3z}{1+z}\right)^{-1}\tag{2}
\end{align*}
Replacing occurrences of $0$ in a Smirnov word by one or more zeros generates words having runs of $0$ with length $\geq 1$.
\begin{align*}
z\longrightarrow z+z^2+z^3+\cdots=\frac{z}{1-z}
\end{align*}
The  same can be done with the digit $1$.
Replacing occurrences of $2$ in a Smirnov word by one or two $2$'s generates words with runs of $2$ of length less than three.
\begin{align*}
z\longrightarrow z+z^2=z(1+z)
\end{align*}
The resulting generating function is according to (2)
\begin{align*}
\color{blue}{C(z)}=\left(1- 2\cdot\frac{\frac{z}{1-z}}{1+\frac{z}{1-z}}-\frac{z(1+z)}{1+z(1+z)}\right)^{-1}
&\color{blue}{=\frac{1+z+z^3}{1-2z-2z^2-2z^3}}\tag{3}
\end{align*}

We obtain for $n\geq 3$ the number of wanted words of length $n$ according to (1) and (3) as
  \begin{align*}
\color{blue}{a_n}&=3^n-c_n\\
&=[z^n]\left(\frac{1}{1-3z}-\frac{1+z+z^3}{1-2z-2z^2-2z^3}\right)\\
&=[z^n]\left(\color{blue}{1}z^3+\color{blue}{5}z^4+\color{blue}{21}z^5+\color{blue}{81}z^6+\color{blue}{295}z^7+\color{blue}{1\,037}z^8+\color{blue}{3\,555}z^9+\cdots\right)
\end{align*}
whereby the last line was obtained with some help of Wolfram Alpha.

A: Following another approach, 
consider a binary word, where the one stands for the ternary $2$ and the zero stands for $0,1$.
Take a binary word of length $n$,  having $s$ ones  and $n-s$ zeros in total, with no more than $r$ consecutive ones.
Now the number of such binary words is given by
$$
\eqalign{
  & M_b (s,r,n) = N_b (s,r,n - s + 1)\quad \left| {\;0 \le {\rm integers  }s,n,r} \right.\quad  =   \cr 
  &  = \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,\min \left( {{s \over {r + 1}}\,,\,n - s + 1} \right)} \right)} {\left( { - 1} \right)^k \left( \matrix{
  n - s + 1 \cr 
  k \cr}  \right)\left( \matrix{
  n - k\left( {r + 1} \right) \cr 
  s - k\left( {r + 1} \right) \cr}  \right)}  \cr} 
$$
as explained in this related post.
Coming back to the ternary words, we just have to multiply $N_b$ by the number of ways
to pad the $n-s$ zeros with $0$ or $1$. So in general we have
$$
\eqalign{
  & M_t (s,r,n) = 2^{\,n - s} M_b (s,r,n) =   \cr 
  &  = 2^{\,n - s} \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,\min \left( {{s \over {r + 1}}\,,\,n - s + 1} \right)} \right)} {\left( { - 1} \right)^k \left( \matrix{
  n - s + 1 \cr 
  k \cr}  \right)\left( \matrix{
  n - k\left( {r + 1} \right) \cr 
  s - k\left( {r + 1} \right) \cr}  \right)}  \cr} 
$$
which summed over $s$ gives
$T(r,n)=$ the number of ternary strings of length $n$ having max $r$ consecutive two's
$$ \bbox[lightyellow] {  
T(r,n) = \sum\limits_{\left( {0\, \le } \right)\,\,s\,\,\left( { \le \,n} \right)} {2^{\,n - s} \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,\min \left( {{s \over {r + 1}}\,,\,n - s + 1} \right)} \right)} {\left( { - 1} \right)^k \left( \matrix{
  n - s + 1 \cr 
  k \cr}  \right)\left( \matrix{
  n - k\left( {r + 1} \right) \cr 
  s - k\left( {r + 1} \right) \cr}  \right)} } 
}$$
Note that it can be easily extended to quaternary, quinary, ... words.
For your particular case then, the number is given by $3^n-T(2,n)$, which checks with the formulas already given in the precedent answers.
