Q:

Number of strings of size $k$ that do not have 'ab'

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"

A:

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})\ .$$

