¿Cuál es la fórmula de recurrencia para L_n? L_n es el número de cadenas (a_1, a_2, ..., a_n) con palabras del conjunto {0, 1, 2} sin ningún 0 y 2 adyacentes.

Responder:

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

Explicación:

Primero tenemos que encontrar # L_1 # y # L_2 #.

# L_1 = 3 # Como solo hay tres cuerdas: #(0) (1) (2)#.

# L_2 = 7 #, como todas las cadenas sin 0 y 2 adyacentes son

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

Ahora vamos a encontrar la recurrencia de # L_n # # (n> = 3) #.

Si la cadena termina en #1#, podemos poner cualquier palabra después de eso.

Sin embargo, si las cuerdas terminan en #0# solo podemos poner #0# o #1#.

Similarmente, si las cuerdas terminan en #2# solo podemos poner #1# o #2#.

Dejar #P_n, Q_n, R_n # ser el numero de cuerdas sin #0# y #2# en posiciones adyacentes y que termina en #0,1,2#, respectivamente.

# L_n, P_n, Q_n # y # R_n # siga las recurrencias a continuación:

# L_n = P_n + Q_n + R_n # (yo)

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

Resuma (ii), (iii) y (iv) que puede ver por cada #n> = 2 #:

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

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

# = color (azul) (2L_n) + color (rojo) (L_ (n-1)) # (usando (i) y (iii))