L_n için yinelenme formülü nedir? L_n, {0, 1, 2} kümesinden sözcüklerle komşu 0 ve 2'ye sahip olmayan dizelerin sayısıdır (a_1, a_2, ..., a_n).

Cevap:

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

Açıklama:

İlk önce bulmalıyız # L-1 # ve # L_2 #.

# L-1 = 3 # Sadece üç dize olduğu için: #(0) (1) (2)#.

# L_2 = 7 #, 0 ve 2 bitişik olmayan tüm dizeler

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

Şimdi nüksünü bulacağız. # L_n # # (N> = 3) #.

Dize biterse #1#Bundan sonra herhangi bir kelime söyleyebiliriz.

Ancak, dizeler biterse #0# sadece koyabiliriz #0# veya #1#.

Benzer şekilde, dizeler biterse #2# sadece koyabiliriz #1# veya #2#.

let #P_n, Q_n, R_n # olmayan dize sayısı olmak #0# ve #2# bitişik konumlarda ve bu da biter #0,1,2#, sırasıyla.

# L_n, P_n, Q_n # ve # R_n # aşağıdaki yinelemeleri takip edin:

# L_n = p_n + Q_n + R_n # (ben)

#P_ (n + 1) = P_N + Q_n # (İi)

#Q_ (n + 1) = P_N + Q_n + R_n #(# = L_n #) (iii)

#R_ (n + 1) = Q_n + R_n # (İv)

Özetle (ii), (iii) ve (iv) her biri için görebilirsiniz #n> = 2 #:

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

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

# = Rengi (mavi) (2L_n) + renkli (kırmızı) (L_ (n-1)) # ((i) ve (iii) kullanarak)