Consider $\Sigma = \{a,b,c\}$ and the language $L$, the set of all strings that do not contain 'ab'
Find strings, of size $k$ is in $L$ ($L_k$)
Consider $A_k$ (strings of size $k$ that end in $a$) and $N_k$ (strings of size $k$ that don't end in $a$)
The recurrence is quite simple,
$$ A_k = A_{k-1} + N_{k-1} $$ $$ N_k = 2N_{k-1} + A_{k-1} $$
I was able to come up with the recurrence, but for extra credit I was asked to prove that this is the "Fibonacci in disguise"
Substituting the second recurrence into the first, $$(N_{k+1}-2N_k)=(N_k-2N_{k-1})+N_{k-1}$$ and so $$N_{k+1}=3N_k-N_{k-1}\ .$$ This is the recurrence relation for "every second Fibonacci", and by checking some initial conditions you can show that $$N_k=F_{2k+1}\ .$$ In a similar way you can prove that $$A_k=F_{2k}\ ,$$ and the the total is $$T_k=A_k+N_k=F_{2k+2}\ .$$ In all of this I am assuming that the Fibonacci numbers start with $F_0=0$ and $F_1=1$.
BTW, you can get a recurrence for $T_k$ directly by using inclusion/exclusion to count the number of strings of length $k$ which DO contain $ab$. Exercise. See if you can explain why $$3^k-T_k=3^{k-2}+3(3^{k-1}-T_{k-1})-(3^{k-2}-T_{k-2})\ .$$