Quantas mensagens diferentes podem ser transmitidas em n microssegundos, usando três sinais diferentes, se um sinal requer 1 microssegundo para a transmissão e os outros dois sinais, 2 microssegundos cada um para a transmissão, e um sinal na mensagem é seguido imediatamente pelo próximo sinal?

Passo 1

O enunciado pede o número de mensagens formadas por três sinais (digamos A,B,C), em que A leva 1\mus e B,C levam 2\mus cada, de modo que a soma das durações seja n microssegundos. O conteúdo usado será contagem de sequências com restrição de soma de “pesos” e recorrência.

Passo 2

Definimos a_n como o número de mensagens cuja duração total é exatamente n μs. Note que:
a_0 = 1
(contém a mensagem vazia)
e
a_1 = 1
(só cabe o sinal A).

Passo 3

Para n\ge2, uma mensagem de duração n termina ou com um sinal de 1\mus A, ou com um sinal de 2\mus B ou C. Se terminar em A sobra n-1 μs, dando a_{n-1} possibilidades; se terminar em B ou C sobra n-2 μs, dando 2\,a_{n-2}. Logo
a_n = a_{n-1} + 2\,a_{n-2}.

Passo 4

Resolvendo a recorrência via equação característica:
\lambda^2 - \lambda - 2 = 0 \quad\Rightarrow\quad \lambda = 2 \text{ ou } \lambda = -1.
Assim a solução geral é
a_n = C\cdot 2^n + D\cdot(-1)^n.

Passo 5

Usando a_0=1 e a_1=1 em
a_0 = C + D = 1, \qquad a_1 = 2C - D = 1,
temos C=\tfrac23 e D=\tfrac13. Portanto
a_n = \frac{2}{3}\,2^n + \frac{1}{3}(-1)^n = \frac{2^{n+1} + (-1)^n}{3}.

Resposta

a_n = \frac{2^{n+1} + (-1)^n}{3}.

Exercícios de Livros Relacionados