Jaka jest formuła powtarzania dla L_n? L_n to liczba łańcuchów (a_1, a_2, ..., a_n) ze słowami z zestawu {0, 1, 2} bez żadnych sąsiadujących 0 i 2.

Odpowiedź:

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

Wyjaśnienie:

Najpierw musimy znaleźć # L_1 # i # L_2 #.

# L_1 = 3 # ponieważ są tylko trzy ciągi: #(0) (1) (2)#.

# L_2 = 7 #, ponieważ wszystkie łańcuchy bez sąsiadujących 0 i 2 są

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

Teraz znajdziemy powtórzenie # L_n # # (n> = 3) #.

Jeśli ciąg kończy się #1#, możemy potem umieścić dowolne słowo.

Jeśli jednak struny kończą się #0# możemy tylko położyć #0# lub #1#.

Podobnie, jeśli łańcuchy się kończą #2# możemy tylko położyć #1# lub #2#.

Pozwolić #P_n, Q_n, R_n # być liczbą ciągów bez #0# i #2# na sąsiednich pozycjach, a to kończy się #0,1,2#, odpowiednio.

# L_n, P_n, Q_n # i # R_n # postępuj zgodnie ze wskazówkami poniżej:

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

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

Podsumuj (ii), (iii) i (iv) możesz zobaczyć dla każdego #n> = 2 #:

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

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

# = kolor (niebieski) (2L_n) + kolor (czerwony) (L_ (n-1)) # (za pomocą (i) i (iii))