Qual é a fórmula de recorrência para L_n? L_n é o número de cadeias de caracteres (a_1, a_2, ..., a_n) com palavras do conjunto {0, 1, 2} sem quaisquer 0 e 2 adjacentes.

Responda:

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

Explicação:

Primeiro temos que encontrar # L_1 # e # L_2 #.

# L_1 = 3 # como existem apenas três cordas: #(0) (1) (2)#.

# L_2 = 7 #, como todas as seqüências sem adjacentes 0 e 2 são

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

Agora vamos encontrar a recorrência de # L_n # # (n> = 3) #.

Se a string terminar em #1#, podemos colocar qualquer palavra depois disso.

No entanto, se as seqüências de caracteres terminarem em #0# nós podemos colocar apenas #0# ou #1#.

Similarmente, se as cordas terminarem em #2# nós podemos colocar apenas #1# ou #2#.

Deixei #P_n, Q_n, R_n # para ser o número de seqüências de caracteres sem #0# e #2# em posições adjacentes e que termina em #0,1,2#, respectivamente.

# L_n, P_n, Q_n # e # R_n # siga as recorrências abaixo:

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

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

Resumindo (ii), (iii) e (iv) você pode ver para cada #n> = 2 #:

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

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

# = cor (azul) (2L_n) + cor (vermelho) (L_ (n-1)) # (usando (i) e (iii))