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

1 Answer
yumean1119
Oct 4, 2017

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

Related questions
See all questions in Combinations and Permutations
Impact of this question
1600 views around the world
You can reuse this answer
Creative Commons License