(b) Mostre que o número f(n) de sequências binárias de comprimento n que não possuem dois números zero juntos é dado por f(0)=1, f(1)=2 e f(n)=f(n-1)+ f(n-2) para n >= 2;

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 f(n) = f(n-1) + f(n-2) :

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 f(0) = 1, f(1) = 2, e f(n) = f(n-1) + f(n-2) para n >= 2 que não possuem dois zeros juntos é dado por:

Exercícios relacionados