Aký je vzorec opakovania pre L_n? L_n je počet reťazcov (a_1, a_2, ..., a_n) so slovami zo sady {0, 1, 2} bez priľahlých 0 a 2.

odpoveď:

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

vysvetlenie:

Najprv musíme nájsť # # L_1 a # # L_2.

# L_1 = 3 # pretože existujú iba tri reťazce: #(0) (1) (2)#.

# L_2 = 7 #, pretože všetky reťazce bez susedných 0 a 2 sú

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

Teraz nájdeme opakovanie # # L_n # (N> = 3) #.

Ak reťazec končí #1#, môžeme za to dať nejaké slovo.

Ak však reťazce končia #0# môžeme dať len #0# alebo #1#.

Podobne, ak reťazec končí #2# môžeme dať len #1# alebo #2#.

nechať #P_n, Q_n, R_n # je počet reťazcov bez #0# a #2# v susedných polohách a končí v #0,1,2#, resp.

# L_n, P_n, Q_n # a # # R_n sledovať opakovanie nižšie:

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

Súčet (ii), (iii) a (iv) môžete vidieť za každý # N> = 2 #:

#L_ (n + 1) = P_ (n + 1) + -Q (n + 1) R_ (n + 1) #

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

# = Farba (modrá) (2L_n) + farba (červená) (L_ (n-1)) # (s použitím bodov i) a iii)) t