Kakšna je formula ponovitve za L_n? L_n je število nizov (a_1, a_2, ..., a_n) z besedami iz niza {0, 1, 2} brez sosednjih 0 in 2.

Odgovor:

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

Pojasnilo:

Najprej moramo najti # L_1 # in # L_2 #.

# L_1 = 3 # ker so samo trije nizi: #(0) (1) (2)#.

# L_2 = 7 #, saj so vsi nizi brez sosednjih 0 in 2

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

Zdaj bomo našli ponovitev # L_n # # (n> = 3) #.

Če se niz konča #1#, po tem lahko izrazimo katerokoli besedo.

Če pa se strune končajo #0# lahko damo samo #0# ali #1#.

Enostavno, če se strune končajo #2# lahko damo samo #1# ali #2#.

Let #P_n, Q_n, R_n # biti število nizov brez #0# in #2# v sosednjih položajih in se konča #0,1,2#v tem zaporedju.

# L_n, P_n, Q_n # in # R_n # sledite spodnjim ponovitvam:

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

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

Povzetek (ii), (iii) in (iv) lahko vidite za vsako #n> = 2 #:

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

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

# = barva (modra) (2L_n) + barva (rdeča) (L_ (n-1)) # (z uporabo (i) in (iii))