Let $a_n$ the number of words in $L_n$ that end in $ba$ for $a,b \in \Sigma, a\neq b$ and $b_n$ similarly the number of words in $L_n$ that end in $baa$. Obviously, $|L_n| = a_n + b_n$.
The following recursions hold (with $s = |\Sigma|$):
$\begin{align*}\qquad a_1 &= s \\ \qquad a_n &= (a_{n-1} + b_{n-1})\cdot(s-1) \qquad \text{ for } n > 1\end{align*}$
and
$\begin{align*}\qquad b_1 &= 0 \\ \qquad b_2 &= s \\ \qquad b_n &= (a_{n-2} + b_{n-2})\cdot(s-1) \qquad \text{ for } n > 2\end{align*}$
If you have trouble seeing that, imagine taking valid strings of length $n-1$ and $n-2$ and appending symbols up to length $n$ while maintaining validity. Now, with $c_n = a_n + b_n$ we get
$\begin{align*}\qquad c_1 &= s \\ c_2 &= s^2 \\ c_n &= (c_{n-2} + c_{n-1}) \cdot (s-1) \qquad \text{ for } n>2\end{align*}$
With the ansatz $C(z) = \sum_{n>0}c_nz^n$ you get that
$\displaystyle\qquad C(z) = \frac{sz(z + 1)}{(1-s)z^2 + (1-s)z + 1}$
Now $|L_n| = c_n = [z^n]C(z)$; unfortunately, the latter expression seems to be hard to find and/or ugly.
Fortunately, recursions of this kind can always be computed by using memoisation in time $\mathcal{O}(n)$ and space $\mathcal{O}(1)$:
calc(n : int, s : int ) { c = new int[] {s, s*s} if ( n <= 0 ) return 0 else if ( n == 1 ) return c[0] else { for ( i=3; i<=n; i++ ) { ci = (c[0] + c[1]) * (s-1) c[0] = c[1]; c[1] = ci } return c[1] } }
Note that this scheme also works if you can not find a nice recursion for $c_n$; just compute $a_n$ and $b_n$ simultaneously.
If you expect many calls to calc
with different parameters, it might be worthwhile to store all values ever computed. Depending on your queries, this might result in amortised constant evaluation time for the price of as much memory as your largest query.