מהי הנוסחה הישנה עבור 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 #:

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