Ano ang formula ng pag-ulit para sa L_n? Ang L_n ay ang bilang ng mga string (a_1, a_2, ..., a_n) na may mga salita mula sa set {0, 1, 2} nang walang anumang katabi 0 at 2.

Sagot:

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

Paliwanag:

Una kailangan nating hanapin # L_1 # at # L_2 #.

# L_1 = 3 # dahil mayroon lamang tatlong string: #(0) (1) (2)#.

# L_2 = 7 #, dahil ang lahat ng mga string na walang katabi 0 at 2 ay

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

Ngayon ay makikita natin ang pag-ulit ng # L_n # # (n> = 3) #.

Kung ang string ay nagtatapos #1#, maaari naming ilagay ang anumang salita pagkatapos na.

Gayunpaman, kung natapos ang mga string #0# maaari lamang naming ilagay #0# o #1#.

Katulad, kung ang mga string ay nagtatapos #2# maaari lamang naming ilagay #1# o #2#.

Hayaan #P_n, Q_n, R_n # upang maging bilang ng mga string na walang #0# at #2# sa katabi posisyon at na nagtatapos sa #0,1,2#, ayon sa pagkakabanggit.

# L_n, P_n, Q_n # at # R_n # sundin ang mga pag-ulit sa ibaba:

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

Sum up (ii), (iii) at (iv) maaari mong makita para sa bawat #n> = 2 #:

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

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

# = kulay (asul) (2L_n) + kulay (pula) (L_ (n-1)) # (gamit ang (i) at (iii))