Hvad er gentagelsesformlen for L_n? L_n er antallet af strenge (a_1, a_2, ..., a_n) med ord fra sæt {0, 1, 2} uden nogen tilstødende 0 og 2.

Svar:

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

Forklaring:

Først skal vi finde # L_1 # og # L_2 #.

# L_1 = 3 # da der kun er tre snor: #(0) (1) (2)#.

# L_2 = 7 #, da alle strenge uden tilstødende 0 og 2 er

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

Nu skal vi finde tilbagevenden af # L_n # # (N> = 3) #.

Hvis strengen slutter i #1#, vi kan lægge noget ord efter det.

Men hvis strengene slutter i #0# vi kan kun sætte #0# eller #1#.

Tilsvarende, hvis strengene slutter #2# vi kan kun sætte #1# eller #2#.

Lade #P_n, Q_n, R_n # at være antallet af strings uden #0# og #2# i tilstødende stillinger og det ender i #0,1,2#, henholdsvis.

# L_n, P_n, Q_n # og # R_n # følg nedenstående gentagelser:

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

Opsummere (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 #

# = Farve (blå) (2L_n) + farve (rød) (L_ (n-1)) # (ved anvendelse af (i) og (iii))