Here is a question that states Bn is the number of bit strings with length n>=1 that don't contain any maximal run of ones of odd length, they're all even. I know how to do the first question but not sure how to go about the second question. Any help should lead me in the right direction, thanks!
To come up with a recursive scheme, one has to analyze what is changing from $n$ to $n+1$.
After writing down the first three rounds with bit strings of length $1$, $2$ and $3$ and observing what changes to the strings occur if one adds a $0$ or a $1$ it turns out that one can divide the words into three categories and assign counters:
The following table shows what happens to the result if one adds a $0$ or a $1$ to words from these sets:
$$ \begin{array}{rcll} F \cdot 0 & \to & F & \mbox{stays fine} \\ F \cdot 1 & \to & R & \mbox{gets flawed, but recoverable} \\ R \cdot 0 & \to & L & \mbox{gets lost forever} \\ R \cdot 1 & \to & F & \mbox{recovered!} \\ L \cdot 0 & \to & L & \mbox{stays lost} \\ L \cdot 1 & \to & L & \mbox{stays lost} \end{array} $$
This gives the following updates of the counts: \begin{align} B_{n+1} &= B_n + R_n \\ R_{n+1} &= B_n \\ L_{n+1} &= 2 L_n + R_n \end{align}
Combining the second with the first we get a recurrence relation for $B_n$: $$ B_{n+1} = B_n + B_{n-1} $$ This is a well known recurrence relation, with explicit solutions for $B_n$.
So we can calculate $R_n = B_{n-1}$ and $L_n = 2^n - (B_n + R_n) = 2^n - B_{n+1}$.
From the paper examples we note that $B_1 = R_1 = 1$, $L_1 = 0$ and $B_2 = 2$, $R_2 = L_2 = 1$ and $B_3 = L_3 = 3$, $R_3 = 2$.