Mi az L_n ismétlődési képlete? Az L_n a {0, 1, 2} készletből származó szavak (a_1, a_2, ..., a_n) száma szomszédos 0 és 2 nélkül.

Válasz:

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

Magyarázat:

Először meg kell találnunk # # L_1 és # # L_2.

# L_1 = 3 # mivel csak három karakterlánc van: #(0) (1) (2)#.

# L_2 = 7 #, mivel minden szomszédos 0 és 2 sztring nélkül

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

Most meg fogjuk találni az ismétlődést # # L_n # (N> = 3) #.

Ha a karakterlánc véget ér #1#, ezt követően bármely szót elhelyezhetünk.

Ha azonban a karakterláncok véget érnek #0# csak elhelyezhetjük #0# vagy #1#.

Egyszerű, ha a karakterláncok véget érnek #2# csak elhelyezhetjük #1# vagy #2#.

enged #P_n, Q_n, R_n # a sztringek száma #0# és #2# a szomszédos pozíciókban, és vége #0,1,2#, illetve.

# L_n, P_n, Q_n # és # # R_n kövesse az alábbi visszatéréseket:

# L_n = P_n + Q_n + R_n # (én)

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

Összefoglalva (ii), (iii) és (iv) mindenki számára látható #n> = 2 #:

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

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

# = Színe (kék) (2L_n) + színes (piros) (L_ (n-1)) # (az i. és iii.