Hva er gjentakelsesformelen for L_n? L_n er antall strenger (a_1, a_2, ..., a_n) med ord fra settet {0, 1, 2} uten tilgrensende 0 og 2.

Svar:

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

Forklaring:

Først må vi finne # L_1 # og # L_2 #.

# L_1 = 3 # da det bare er tre snorer: #(0) (1) (2)#.

# L_2 = 7 #, som alle strenger uten tilstøtende 0 og 2 er

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

Nå skal vi finne gjentakelsen av # L_N # # (N> = 3) #.

Hvis strengen slutter i #1#, vi kan legge noe ord etter det.

Men hvis strengene ender i #0# vi kan bare sette #0# eller #1#.

Tilsvarende, hvis strengene ender i #2# vi kan bare sette #1# eller #2#.

La #P_n, Q_n, R_n # å være antall strenger uten #0# og #2# i tilstøtende stillinger og som slutter i #0,1,2#, henholdsvis.

# L_n, P_n, Q_n # og # R n # følg gjentakelsene nedenfor:

# L_N = P_n + Q_n + R n # (Jeg)

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

Oppsummer (ii), (iii) og (iv) du kan se for hver #N> = 2 #:

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

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

# = Farge (blå) (2L_n) + farger (rød) (L_ (n-1)) # (ved bruk av (i) og (iii))