Ensino Médio ⇒ (Rufino) Recorrência em combinatória

[Deleted User 23699]

Seja f(n) o número de palavras com n letras, sem zeros vizinhos, formadas a partir do alfabeto {0,1,2}. Encontre uma recorrência para f(n).

Resposta

---

f(n)=2f(n-1)+2f(n-2)

[A13235378]

Olá:

Seja:

X(n) = o número de palavras que começam com 1 (atendendo às condições da questão)
Y(n) = o número de palavras que começam com 2 (atendendo às condições)
Z(n) = o número de palavras que começam com 0 (atendendo às condições)

Logo:

f(n) = X(n) + Y(n) + Z(n)

X(n) = 1 ______ (começando com 1 ou 2)

As n-1 letras restantes podem ser escritas de f(n-1) maneiras , pois podem começar com 1,2 ou 0

X(n) = f(n-1)

Analogamente ,

Y(n) = f(n-1)

Para Z(n) ,quando começar com 0 , os n-1 letras restantes não podem começar com 0, ou seja podem começar com 1 ou 2

Logo,

Z(n) = X(n-1) + Y (n-1)

Lembrando que X(n) = Y(n) = f(n-1)

Abaixando o indice , X(n-1) = Y(n-1) = f(n-2)

Z(n) = 2f(n-2)


Portanto,

f(n) = 2f(n-1) + 2f(n-2)