Какова формула повторения для L_n? L_n - количество строк (a_1, a_2, ..., a_n) со словами из набора {0, 1, 2} без каких-либо соседних 0 и 2.

Ответ:

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

Объяснение:

Сначала мы должны найти # L_1 # а также # L_2 #.

# L_1 = 3 # так как есть только три строки: #(0) (1) (2)#.

# L_2 = 7 #, так как все строки без смежных 0 и 2 являются

#(0,0),(0,1),(1,0),(1,1),(1,2),(2,1),(2,2)#

Теперь мы собираемся найти повторение # L_n # # (П> = 3) #.

Если строка заканчивается #1#Мы можем поставить любое слово после этого.

Однако, если строки заканчиваются на #0# мы можем поставить только #0# или же #1#.

Аналогично, если строки заканчиваются на #2# мы можем поставить только #1# или же #2#.

Позволять #P_n, Q_n, R_n # быть числом строк без #0# а также #2# в соседних позициях, и это заканчивается #0,1,2#соответственно.

# L_n, P_n, Q_n # а также # R_n # следуйте повторениям ниже:

# L_n = P_n + Q_n + R_n # (я)

#P_ (п + 1) = P_n + Q_n # (II)

#Q_ (п + 1) = P_n + Q_n + R_n #(# = L_n #) (iii)

#R_ (п + 1) = Q_n + R_n # (IV)

Подведите итоги (ii), (iii) и (iv), которые вы можете увидеть для каждого #n> = 2 #:

#L_ (п + 1) = Р- (п + 1) + Q_ (п + 1) + R_ (п + 1) #

# 2 = (P_n + Q_n + R_n) + Q_n #

# = Цвет (синий) (2L_n) + цветной (красный) (L_ (п-1)) # (используя (i) и (iii))