Question

What is the recurrence formula for `L_n`? `L_n` is the number of strings (`a_1,a_2,...,a_n`) with words from set {`0, 1, 2`} without any adjacent `0` and `2`.

This problem is a part of the question originally asked by @smkwd.
https://socratic.org/questions/how-to-prove-that#484241

I divided it into smaller parts so as to avoid getting the answer too long.

--Divided problem--
Consider a string (`a_1,a_2,...,a_n`) with words from set {`0, 1, 2`}.

Let `L_n` be the number of all strings of length `n` with the words from set {`0, 1, 2`} in which the numbers `0` and `2` are not present in adjacent positions. For exmaple, (`1,2,1,0`) is a string that meets the condition, while (`1,2,0,1`) is not. Find the recurrence formula for `L_n`.

Answer 1

`L_1=3, L_2=7, L_(n+1)=2L_n+L_(n-1)" "(n>=2)`

Explanation:

First we have to find `L_1` and `L_2`.

`L_1=3` as there are only three string: `(0) (1) (2)`.

`L_2=7`, as all strings without adjacent 0 and 2 are
`(0,0),(0,1),(1,0),(1,1),(1,2),(2,1),(2,2)`

Now we are going to find the recurrence of `L_n` `(n>=3)` .
If the string ends in `1`, we can put any word after that.
However, if the strings ends in `0` we can put only `0` or `1`.
Similary, if the strings ends in `2` we can put only `1` or `2`.

Let `P_n, Q_n, R_n` to be the number of strings without `0` and `2` in adjacent positions and that ends in `0,1,2`, respectively.

`L_n,P_n, Q_n` and `R_n` follow the recurrences below:

`L_n=P_n+Q_n+R_n` (i)
`P_(n+1)=P_n+Q_n` (ii)
`Q_(n+1)=P_n+Q_n+R_n`(`=L_n`) (iii)
`R_(n+1)=Q_n+R_n` (iv)

Sum up (ii),(iii) and (iv) you can see for every `n>=2`:
`L_(n+1)=P_(n+1)+Q_(n+1)+R_(n+1)`
`=2(P_n+Q_n+R_n)+Q_n`
`=color(blue)(2L_n)+color(red)(L_(n-1))` (using (i) and (iii))