# 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# .

**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 (

Let

##### 1 Answer

#### Explanation:

First we have to find

Now we are going to find the recurrence of

If the string ends in

However, if the strings ends in

Similary, if the strings ends in

Let

Sum up (ii),(iii) and (iv) you can see for every