# 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} , \ldots , {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}$.

Oct 4, 2017

${L}_{1} = 3 , {L}_{2} = 7 , {L}_{n + 1} = 2 {L}_{n} + {L}_{n - 1} \text{ } \left(n \ge 2\right)$

#### Explanation:

First we have to find ${L}_{1}$ and ${L}_{2}$.

${L}_{1} = 3$ as there are only three string: $\left(0\right) \left(1\right) \left(2\right)$.

${L}_{2} = 7$, as all strings without adjacent 0 and 2 are
$\left(0 , 0\right) , \left(0 , 1\right) , \left(1 , 0\right) , \left(1 , 1\right) , \left(1 , 2\right) , \left(2 , 1\right) , \left(2 , 2\right)$

Now we are going to find the recurrence of ${L}_{n}$ $\left(n \ge 3\right)$ .
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 \ge 2$:
${L}_{n + 1} = {P}_{n + 1} + {Q}_{n + 1} + {R}_{n + 1}$
$= 2 \left({P}_{n} + {Q}_{n} + {R}_{n}\right) + {Q}_{n}$
$= \textcolor{b l u e}{2 {L}_{n}} + \textcolor{red}{{L}_{n - 1}}$ (using (i) and (iii))