Ποια είναι η φόρμουλα επανάληψης για το L_n; L_n είναι ο αριθμός των συμβολοσειρών (a_1, a_2, ..., a_n) με λέξεις από το σετ {0, 1, 2} χωρίς οιονδήποτε παρακείμενο 0 και 2.

Απάντηση:

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

Εξήγηση:

Πρώτα πρέπει να βρούμε # 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 # (Εγώ)

# Ρ (n + 1) = Ρ_η + Q_η # (ϋ)

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

# R_ (η + 1) = Q_n + R_n # (ίν)

Συγκεντρώστε (ii), (iii) και (iv) μπορείτε να δείτε για κάθε # n> = 2 #:

(N + 1) = Ρ_ (η + 1) + Q_ (η + 1) + R_

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

# = χρώμα (μπλε) (2L_n) + χρώμα (κόκκινο) (L_ (n-1)) # (χρησιμοποιώντας (i) και (iii))