Apakah rumusan berulang untuk L_n? L_n ialah bilangan rentetan (a_1, a_2, ..., a_n) dengan kata-kata dari set {0, 1, 2} tanpa mana-mana bersebelahan 0 dan 2.

Jawapan:

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

Penjelasan:

Pertama kita perlu mencari # L_1 # dan # L_2 #.

# L_1 = 3 # kerana terdapat hanya tiga rentetan: #(0) (1) (2)#.

# L_2 = 7 #, kerana semua rentetan tanpa bersebelahan 0 dan 2 adalah

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

Sekarang kita akan mencari pengulangan semula # L_n # # (n> = 3) #.

Jika rentetan berakhir #1#, kita boleh meletakkan perkataan selepas itu.

Walau bagaimanapun, jika rentetan berakhir #0# kita boleh meletakkan sahaja #0# atau #1#.

Similari, jika rentetan berakhir #2# kita boleh meletakkan sahaja #1# atau #2#.

Biarkan #P_n, Q_n, R_n # untuk menjadi bilangan tali tanpa #0# dan #2# dalam kedudukan bersebelahan dan yang berakhir #0,1,2#, masing-masing.

# L_n, P_n, Q_n # dan # R_n # ikuti pengulangan di bawah:

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

Jumlah (ii), (iii) dan (iv) anda boleh lihat bagi setiap #n> = 2 #:

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

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

# = warna (biru) (2L_n) + warna (merah) (L_ (n-1)) # (menggunakan (i) dan (iii))