For any number of length n ending in 1, a 1 or 2 can be appended to form a number of length n+1.

For any number of length n ending in 2, a 1, 2, or 3 can be appended to form a number of length n+1.

For any number of length n ending in 3, a 2 or 3 can be appended to form a number of length n+1.

Let g(n) be the quantity of numbers ending in 1.  g(n) will also be the quantity of numbers ending in 3.

Let h(n) be the quantity if numbers ending in 2.

Then let f(n) be the total quantity of numbers, then f(n)=2g(n)+h(n)

g(n) and h(n) can be defined recursively as

g(n+1) = g(n)+h(n) and h(n+1)=2*g(n)+h(n)

Rearranging I can make

h(n) = g(n)-g(n-1) and g(n) = (h(n)-h(n-1))/2

I can substitute these into each other and simplify to get

g(n+1)=2g(n)+g(n-1) and h(n+1)=2h(n)+h(n-1)

These are identical recursions, and f(n) is a linear combination of g(n) and h(n), therefore f(n) also has this recursion f(n+1) = 2f(n)+f(n-1).

Now all we need is initial conditions f(1)=3 from {1,2,3} and f(2)=7 from {11,12,21,22,23,32,33}.  Then f(n) continues as 3,7,17,41,99,239.  Then the quantities if 4-, 5-, and 6-digit numbers are 41, 99, and 239 respectively.

With such a simple recursion it is easy to go much further, for example, f(10)=8119 valid 10-digit numbers, or even f(20)=54608393 valid 20-digit numbers.