012 Uma moeda é lançada n vezes. Seja P_{n} a probabilidade de que duas caras não apareçam consecutivamente.
(a) Calcule P_{1}, P_{2}, P_{3} e P_{4}.
(b) Prove que P_{n}=\frac{1}{2} P_{n-1}+\frac{1}{4} P_{n-2} para cada n>2.
(c) Prove que P_{n}=\frac{F_{n+2}}{2^{n}}, onde F_{n} é o n-ésimo termo da sequência de Fibonacci.

Passo 1

O enunciado trata do experimento de lançar uma moeda justa n vezes e considera a probabilidade P_{n} de que não ocorram duas caras consecutivas. Para resolver, vamos usar contagem de sequências binárias sem o padrão “cara-cara”, montar a relação de recorrência por análise de casos e reconhecer que essa recorrência é a dos números de Fibonacci normalizados por 2^{n}.

Passo 2

Para calcular diretamente P_{1},P_{2},P_{3},P_{4}, contamos quantas sequências de comprimentos 1,2,3,4 em \{\text{C},\text{K}\} (C = cara, K = coroa) não têm “CC”. O total de sequências de tamanho n é 2^{n}.
  • Para n=1: todas as 2 sequências são válidas, logo
P_{1}=\frac{2}{2^{1}}=1.
  • Para n=2: entre as 4 sequências só “CC” é proibida, então há 3 válidas,
P_{2}=\frac{3}{2^{2}}=\frac{3}{4}.
  • Para n=3: há 8 totais e as proibidas são “CC*” e “*CC”, ao todo 3, restando 5,
P_{3}=\frac{5}{2^{3}}=\frac{5}{8}.
  • Para n=4: sabe-se (ou conta-se) que há 8 sequências sem “CC” dentre 16,
P_{4}=\frac{8}{2^{4}}=\frac{1}{2}.

Passo 3

Queremos mostrar que, para n>2,
P_{n} = \frac12\,P_{n-1} + \frac14\,P_{n-2}.
Analisamos o primeiro lançamento:
  1. Se sai coroa (probabilidade \tfrac12), não restringe o segundo, e nos resta evitar “CC” nos n-1 últimos; isso contribui com \tfrac12\,P_{n-1}.
  2. Se sai cara (probabilidade \tfrac12), então para não ter “CC” o segundo deve ser coroa (probabilidade \tfrac12), restando evitar “CC” nos n-2 últimos; isso dá \tfrac12\cdot\tfrac12\,P_{n-2}=\tfrac14\,P_{n-2}.
    Somando os casos obtemos a relação requerida.

Passo 4

Para resolver a recorrência
P_{n} = \frac12\,P_{n-1} + \frac14\,P_{n-2},
note que se definirmos a_{n}=2^{n}P_{n}, a relação vira
a_{n}=a_{n-1}+a_{n-2},
com a_{1}=2, a_{2}=3. Essa é exatamente a recorrência dos números de Fibonacci deslocados, já que F_{3}=2 e F_{4}=3. Logo
a_{n}=F_{n+2} \quad\Longrightarrow\quad P_{n}=\frac{a_{n}}{2^{n}}=\frac{F_{n+2}}{2^{n}}.

Resposta

(a) P_{1}=1,\;P_{2}=\tfrac{3}{4},\;P_{3}=\tfrac{5}{8},\;P_{4}=\tfrac{1}{2}.
(b) Foi mostrado que
P_{n}=\frac12\,P_{n-1}+\frac14\,P_{n-2} \quad(n>2).
(c) Demonstrou-se que
P_{n}=\frac{F_{n+2}}{2^{n}},
onde F_{n} é o n-ésimo número de Fibonacci.

Exercícios relacionados