(b) Mostre que o número
de sequências binárias de comprimento
que não possuem dois números zero juntos é dado por
e
para
;
Passo 1
Então, bora entender o que o enunciado tá pedindo! A gente quer descobrir quantas sequências de bits (ou binárias) com comprimento
não têm dois zeros seguidos. Isso envolve conceitos de combinatória e sequências recorrentes. Pra resolver isso, vamos precisar usar a ideia de recorrência para montar uma relação que nos ajude a contar essas sequências de forma sistemática.
Passo 2
Vamos pensar em como construir uma sequência válida de comprimento
. A última posição dessa sequência pode ser um 1 ou um 0.
-
Se a última posição for 1: Então, as primeiras
posições podem ser qualquer sequência válida de comprimento . Ou seja, há maneiras de fazer isso. -
Se a última posição for 0: Para evitar ter dois zeros seguidos, a penúltima posição precisa ser 1. Então, as primeiras
posições podem ser qualquer sequência válida de comprimento . Assim, há maneiras de formar essas sequências.
Passo 3
Como as duas situações são exclusivas e cobrem todas as possibilidades, podemos somar as duas contagens para obter o total de sequências válidas de comprimento
:
Passo 4
Agora, precisamos definir os casos base para nossa recorrência:
-
Para
: Há exatamente 1 sequência possível (a sequência vazia). Então, . -
Para
: As possíveis sequências são “0” e “1”, totalizando 2. Portanto, .
Resposta
Portanto, o número de sequências binárias de comprimento
que não possuem dois zeros juntos é dado por:
Exercícios relacionados
Se
, determine o valor de
.
Mostre que calcular
e
usando o teorema binomial é moleza. Generalize esses casos e encontre uma fórmula para expressões do tipo
.
© Determine o coeficiente de
no desenvolvimento de
;
Use o teorema binomial (seja criativo) para calcular as seguintes somas (nos itens (
) e (
) as somas vão até o ponto em que seus termos começam a se anular):
(d) .
(d)