สูตรการเกิดซ้ำสำหรับ L_n คืออะไร L_n คือจำนวนสตริง (a_1, a_2, ... , a_n) พร้อมคำจากชุด {0, 1, 2} โดยไม่มี 0 และ 2 ที่อยู่ติดกัน

ตอบ:

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

คำอธิบาย:

ก่อนอื่นเราต้องค้นหา # L_1 # และ # L_2 #.

# L_1 = 3 # เนื่องจากมีเพียงสามสาย: #(0) (1) (2)#.

# L_2 = 7 #เนื่องจากสตริงทั้งหมดที่ไม่มี 0 และ 2 อยู่ติดกัน

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

ตอนนี้เรากำลังจะพบการกลับเป็นซ้ำของ # L_n # # (n> = 3) #.

หากสตริงสิ้นสุดลง #1#เราสามารถใส่คำใด ๆ หลังจากนั้น

อย่างไรก็ตามหากสตริงสิ้นสุดลง #0# เราสามารถใส่ได้เท่านั้น #0# หรือ #1#.

คล้ายคลึงกันถ้าสตริงสิ้นสุดลง #2# เราสามารถใส่ได้เท่านั้น #1# หรือ #2#.

ปล่อย #P_n, Q_n, R_n # เป็นจำนวนสตริงที่ไม่มี #0# และ #2# ในตำแหน่งที่อยู่ติดกันและสิ้นสุดใน #0,1,2#ตามลำดับ

# L_n, P_n, Q_n # และ # R_n # ทำตามการเกิดซ้ำด้านล่าง:

# L_n = P_n + + Q_n R_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)

สรุป (ii), (iii) และ (iv) ที่คุณสามารถเห็นได้ทุก ๆ #N> = 2 #:

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

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

# = สี (สีฟ้า) (2L_n) + สี (สีแดง) (L_ (n-1)) # (ใช้ (i) และ (iii))