Number of strings of $\{0,1,2\}$ : the longest substrings of $1$ is odd-length. Consider $A^* = \{0,1,2\}^*$. We want to know how many string of length $n$ in this alphabet following such property : all longest substrings of 1-s has odd length(let it be $a_n$).
I know that it can be founded by regular-sequence, but I don't understand how to generate it. 
Essential edits: 


*

*We don't consider zero numbers of $1s$.

*Longest means maximal, i.e. $111011$, $1110111$ are valid, $11101111$
invalid.


So I've tried to consider some extra cases :
$a_1 = 1,a_2 = 4(10,12,01,21),a_3 = 15,a_4 = 48$. The OEIS gives me that it should be $a_n = n Pell(n)$. Maybe it's possible to show it somehow? 
 A: This is a partial solution. It provides a recurrence relation which allows manual calculation for small values of $n$, and makes it easier to get solutions for larger $n$ from Mathematica etc. 
Let $g(n,k)$ denote the number of strings length $n$ with $k$ as the longest run of 1s. We have the following equations:
$g(n,0)=2^n$
$g(n,n)=1$
$g(n,n-1)=4\text{ for }n\ge2$
$g(n,k)=0\text{ for }n<k$
$g(n,k)=2\sum_{h=1}^kg(n-\,h,k)+2\sum_{h=0}^kg(n-\,k-\,1,k-\,h)$
The terms in the first sum of the last equation correspond to adding a non-1 followed by $h-1$ 1s. So $h=0$ gives strings ending with a non-1, whilst higher $h$ give strings ending with a run of 1s of length $<k$. The terms in the second sum correspond to strings ending with a run of $k$ 1s.
So we get: 
$n=1: 2,1$
$n=2: 4,4,1$
$n=3: 8,14,4,1$
$n=4: 16,44,16,4,1$
$n=5: 32,132,58,16,4,1$
$n=6: 64,384,200,60,16,4,1$
$n=7: 128,1096,668,214,60,16,4,1$
As a check we see that the totals for each $n$ are just $3^n$. The sum of the odd maximum lengths gives: $$1,4,15,48,149,448,1327$$. These are the numbers sought in the question. Note that the sequence is not OEIS93967,
