ما هي صيغة تكرار ل 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 # (ن> = 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_ (ن + 1) = P_n + Q_n # (ب)

#Q_ (ن + 1) = P_n + Q_n + R_n #(# = # L_n) (ثالثا)

#R_ (ن + 1) = Q_n + R_n # (رابعا)

نلخص (ii) و (iii) و (iv) يمكنك رؤيته لكل شخص # N> = 2 #:

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

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

# = اللون (الأزرق) (2L_n) + اللون (الأحمر) (L_ (ن 1)) # (باستخدام (i) و (iii))