Wat is de herhalingsformule voor L_n? L_n is het aantal strings (a_1, a_2, ..., a_n) met woorden uit set {0, 1, 2} zonder aangrenzende 0 en 2.

Antwoord:

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

Uitleg:

Eerst moeten we vinden # L_1 # en # L_2 #.

# L_1 = 3 # want er zijn maar drie snaren: #(0) (1) (2)#.

# L_2 = 7 #, zoals alle tekenreeksen zonder aangrenzende 0 en 2 zijn

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

Nu gaan we de herhaling vinden van # L_n # # (N> 3) #.

Als de reeks eindigt #1#, we kunnen daarna nog een woord plaatsen.

Als de tekenreeks echter eindigt #0# we kunnen alleen zetten #0# of #1#.

Similary, als de snaren eindigen #2# we kunnen alleen zetten #1# of #2#.

Laat #P_n, Q_n, R_n # om het aantal snaren zonder te zijn #0# en #2# in aangrenzende posities en dat eindigt in #0,1,2#, respectievelijk.

# L_n, P_n, Q_n # en # R_n # volg de recidieven hieronder:

# L_n = p_n + Q_n + R_n # (ik)

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

Samenvattend (ii), (iii) en (iv) kunt u voor elke zien #n> = 2 #:

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

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

# = Kleur (blauw) (2L_n) + kleur (rood) (L_ (n-1)) # (met behulp van (i) en (iii))