sequences above 0,1,2 start&end with 0 with no 2 same successive digits find the number of sequences of length n above {0,1,2} that start and end with 0 and without 2 successive digits that are equal (00,11,22).
Find and solve a recursice equation.
I would be thankful for a clue or an approach to this.
 A: 
We define a recurrence relation as follows. Let
  
  
*
  
*$a_k$ denote the number of valid strings with $k$-th symbol $0$.
  
*$b_k$ denote the number of valid strings with $k$-th symbol $1$.
  
*$c_k$ denote the number of valid strings with $k$-th symbol $2$.

Since valid strings start with $0$ we have
\begin{align*}
a_1=1\qquad b_1=0\qquad c_1=0\tag{1}
\end{align*}
Valid strings do not have equal consecutive characters. The recurrence relation for $2\leq k\leq n-1$ is
\begin{align*}
a_k&=b_{k-1}+c_{k-1}\\
b_k&=a_{k-1}+c_{k-1}\tag{2}\\
c_k&=a_{k-1}+b_{k-1}
\end{align*}
and since the $n$-th character of a valid string is $0$, we have for $n\geq 2$:
\begin{align*}
a_n=b_{n-1}+c_{n-1}\tag{3}
\end{align*}

We are looking for $a_n, n\geq 0$.
Due to the symmetry of $b_n$ and $c_n$ in the recurrence relations (1) - (3) we observe $b_n=c_n, n\geq 1$ and we obtain a simplified recurrence relation
\begin{align*}
a_1&=1, b_1=0\\
a_k&=2b_{k-1}\qquad\qquad 2\leq k\leq n-1\tag{4}\\
b_k&=a_{k-1}+b_{k-1}\\
a_n&=2b_{n-1}\tag{5}
\end{align*}
We obtain from (4) a recurrence relation for $b_k, k\geq 1$.
  \begin{align*}
b_1&=0, b_2=1\\
b_k&=b_{k-1}+2b_{k-2}\qquad\qquad k\geq 3\tag{6}
\end{align*}
Setting $B(x)=\sum_{k=0}^\infty b_kx^k$ we obtain from (6)
  \begin{align*}
\sum_{k=3}^\infty b_kx^k&=\sum_{k=3}^\infty b_{k-1}x^k+2\sum_{k=3}b_{k-2}x^k\\
&=x\sum_{k=2}^\infty b_{k}x^k+2x^2\sum_{k=1}b_{k}x^k\\
B(x)-x^3&=xB(x)+2x^2B(x)\\
\color{blue}{B(x)}&\color{blue}{=\frac{x^3}{1-x-2x^2}}
\end{align*}
Since $a_n=2b_{n-1}$ according to (5), we finally obtain for $n\geq 2$
  \begin{align*}
a_n&=2[x^{n-1}]B(x)\\
&=2[x^n]xB(x)\\
&=[x^n]\frac{2x^3}{1-x-2x^2}\\
&=[x^n]\left(2 x^3 + 2 x^4 + 6 x^5 + \color{blue}{10} x^6 + 22 x^7 + 42 x^8 + \cdots\right)
\end{align*}

The last line was calculated with some help of Wolfram Alpha.

The coefficient $\color{blue}{10}$ of $x^6$ for example tells us we have $10$ valid strings
  \begin{align*}
&010120,010210,012010,012020,012120,\\
&020120,020210,021010,021020,021210
\end{align*}

A: It's the number of closed walks on the graph $K_3$.  So if we define
$$
A=
\begin{bmatrix}
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 0 \\
\end{bmatrix}
$$
then it's the number in cell $(1,1)$ of $A^n$.
Computing this gives
$$
0, 2, 2, 6, 10, 22, 42, 86, 170, 342, 682, \ldots
$$
when $n \geq 1$, which is OEIS's A078008.
There's a linear recurrence given there
$$
a(n) = 3a(n-2) + 2a(n-3)
$$
which follows directly from the identity
$$
A^4 = 3A^2+2A.
$$
And if we use the usual methods for solving linear recurrences, we'd get the closed form solution at OEIS:
$$
a(n) = \frac{1}{3}(2^n + 2(-1)^n).
$$
