Công thức tái phát cho L_n là gì? L_n là số chuỗi (a_1, a_2, ..., a_n) với các từ từ tập {0, 1, 2} mà không có bất kỳ 0 và 2 liền kề nào.

Câu trả lời:

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

Giải trình:

Đầu tiên chúng ta phải tìm # L_1 # và # L_2 #.

# L_1 = 3 # vì chỉ có ba chuỗi: #(0) (1) (2)#.

# L_2 = 7 #, vì tất cả các chuỗi không có 0 và 2 liền kề là

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

Bây giờ chúng ta sẽ tìm thấy sự tái phát của # L_n # # (n> = 3) #.

Nếu chuỗi kết thúc bằng #1#, chúng ta có thể đặt bất kỳ từ nào sau đó.

Tuy nhiên, nếu chuỗi kết thúc bằng #0# chúng ta chỉ có thể đặt #0# hoặc là #1#.

Similary, nếu chuỗi kết thúc bằng #2# chúng ta chỉ có thể đặt #1# hoặc là #2#.

Để cho #P_n, Q_n, R_n # là số chuỗi không có #0# và #2# ở vị trí liền kề và kết thúc bằng #0,1,2#, tương ứng.

# L_n, P_n, Q_n # và # R_n # theo dõi các đợt tái phát dưới đây:

# L_n = P_n + Q_n + R_n # (tôi)

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

Tổng hợp (ii), (iii) và (iv) bạn có thể thấy cho mọi #n> = 2 #:

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

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

# = màu (xanh dương) (2L_n) + màu (đỏ) (L_ (n-1)) # (sử dụng (i) và (iii))