Análise Combinatória - Funções geradoras

boa tarde, alguém poderia me ajudar nessa questão de um trabalho, foi retirada de uma lista de funções geradoras.

Encontre o numero de sequências com r termos formadas pelos dígitos 0, 1, 2 tais que o numero de 0's  é par.

R:  (3^r + 1)/2;

Defina:

a_n : número de sequências de n termos no qual o 0 aparece um número par de vezes.

b_n: número de sequências de n termos no qual o 0 aparece um número ímpar de vezes.

Perceba por exemplo a₁ = 2, o zero aparece 0 vezes (um número par) de duas formas distintas. 

De fato, a_n + b_n = número total de sequências. Logo:

a_n + b_n = 3ⁿ

Vamos calcular a_n. Temos os casos:

1) O primeiro termo da sequência de n termos é o 0:

Devemos ter nos n-1 termos restantes um número ímpar de zeros. Ou seja, b_n-1

2) O primeiro termo da sequência de n termos é o 1:

Devemos ter nos n-1 termos restantes um número par de vezes o número zero. Ou seja, a_n-1

3) O primeiro termo da sequência de n termos é o 2:

Devemos ter nos n-1 termos restantes um número par de vezes o número zero. Ou seja, a_n-1

Logo: a_n = b_n-1 + 2*a_n-1 , mas b_n-1 = 3^n-1 - a_n-1. Assim:

a_n = a_n-1 + 3^n-1

a_n-1 = a_n-2 + 3^n-2
.
.
.

a₂ = a₁ + 3

Somando membro a membro:

a_n = a₁ + (3+3²+... + 3^n-1)

a_n = a₁ + 3*(3^n-1 - 1)/2

Por fim: 

a_n = 2 + (3ⁿ - 3)/2 

a_n = (3ⁿ + 1)/2.

Tomando n=r, está feito.

Muito obrigado Vitor!