Що таке формула повторення для 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 # # (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 # (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)

Підсумовуйте (ii), (iii) та (iv), які ви можете побачити для кожного #n> = 2 #:

#L_ (n + 1) = P_ (n + 1) + Q_ (n + 1) + R_ (n + 1) #

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

# = колір (синій) (2L_n) + колір (червоний) (L_ (n-1)) # (за допомогою (i) і (iii))