Wie lautet die Wiederholungsformel für L_n? L_n ist die Anzahl der Zeichenfolgen (a_1, a_2, ..., a_n) mit Wörtern aus der Gruppe {0, 1, 2} ohne angrenzende 0 und 2.

Antworten:

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

Erläuterung:

Zuerst müssen wir finden # L_1 # und # L_2 #.

# L_1 = 3 # da gibt es nur drei string: #(0) (1) (2)#.

# L_2 = 7 #, da alle Zeichenfolgen ohne benachbarte 0 und 2 sind

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

Jetzt werden wir die Wiederholung von finden # L_n # # (n> = 3) #.

Wenn die Zeichenfolge endet #1#, wir können danach noch ein Wort setzen.

Wenn die Zeichenfolgen jedoch auf #0# wir können nur setzen #0# oder #1#.

Ähnlich, wenn die Saiten auf enden #2# wir können nur setzen #1# oder #2#.

Lassen #P_n, Q_n, R_n # die Anzahl der Strings ohne sein #0# und #2# in benachbarten Positionen und das endet in #0,1,2#, beziehungsweise.

# L_n, P_n, Q_n # und # R_n # Folgen Sie den Wiederholungen unten:

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

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

Fassen Sie (ii), (iii) und (iv) zusammen, die Sie für jeden sehen können #n> = 2 #:

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

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

# = Farbe (blau) (2L_n) + Farbe (rot) (L_ (n-1)) # (unter Verwendung von (i) und (iii))