Quina és la fórmula de repetició de L_n? L_n és el nombre de cadenes (a_1, a_2, ..., a_n) amb paraules del conjunt {0, 1, 2} sense cap 0 o 2 adjacent.

Resposta:

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

Explicació:

Primer hem de trobar # L_1 # i # L_2 #.

# L_1 = 3 # ja que només hi ha tres cadenes: #(0) (1) (2)#.

# L_2 = 7 #, ja que totes les cadenes sense 0 i 2 adjacents són

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

Ara trobarem la recurrència de # L_n # # (n> = 3) #.

Si la cadena acaba #1#, podem posar qualsevol paraula després d’aquest.

Tanmateix, si les cadenes acaben #0# només podem posar #0# o bé #1#.

Simularment, si les cordes acaben #2# només podem posar #1# o bé #2#.

Deixar #P_n, Q_n, R_n # ser el nombre de cadenes sense #0# i #2# en posicions adjacents i això acaba en #0,1,2#, respectivament.

# L_n, P_n, Q_n # i # R_n # seguiu les recurrències següents:

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

Suma (ii), (iii) i (iv) es pot veure per a cadascun #n> = 2 #:

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

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

# = color (blau) (2L_n) + color (vermell) (L_ (n-1)) # (utilitzant (i) i (iii))