It is clear that:

-valid sequence of length K ending with 1 might be composed

adding 1 to any valid sequence of length K-1

-valid sequence of length K ending with 2 might be composed

adding 2 to any valid sequence of length K-1

-valid sequence of length K ending with 0 might be composed

adding 0 to valid sequences of length K-1 ending with 0 or 2

So simple Python program

```
def valid123(n):
a = [[0]*3 for _ in range(n)]
a[0][0] = 1
a[0][1] = 1
a[0][2] = 1
summ = 3
for i in range(1, n):
a[i][0] = summ - a[i-1][1]
a[i][1] = summ
a[i][2] = summ
summ = sum(a[i])
return summ
for i in range(1,10):
print(i, valid123(i))
```

gives

```
1 3
2 8
3 21
4 55
5 144
6 377
7 987
8 2584
9 6765
```

Corresponding OEIS sequence has simple recurrent representation `a(n) = 3*a(n-1) - a(n-2)`

– subset of Fibonacci, and some closed formula does exist:

```
a(n) = (ap^n - am^n)/(ap-am), with ap := (3+sqrt(5))/2, am := (3-sqrt(5))/2
```

CLICK HERE to find out more related problems solutions.