Question

Quantas sequencias binárias(isto é, sequencias consistindo de 0's e 1') possuem três 0's consecutivos em alguma parte da sequencia ? (resolver usando relação de recorrencia)

Answer 1

Olá, Bruno.

Vamos representar abaixo todas as possibilidades de construção de sequências binárias com três zeros consecutivos formadas por $n$ algarismos.
As construções a seguir foram elaboradas de tal forma que, a cada nova construção, não haja a repetição de sequências já geradas em construções anteriores:

Construção 1: 0 0 0 _ _ ... _ _ _ _ _
Construção 2: 1 0 0 0 _ ... _ _ _ _ _
Construção 3: _ 1 0 0 0 ... _ _ _ _ _
$\vdots$
Construção n - 3: _ _ _ _ _ ... 1 0 0 0 _
Construção n - 2: _ _ _ _ _ ... _ 1 0 0 0

Como se pode observar acima, a regra para que cada nova construção, a partir da segunda, não repita sequências já geradas, é que o trecho de 3 zeros consecutivos, após ser movido uma posição para a direita da posição anterior, seja precedido de um algarismo "1".
Observe que a posição do "1", a cada nova construção, corresponde, na construção anterior, à posição do primeiro zero do trecho "000". Isto garante que não ocorra, a cada nova construção, a repetição de sequências já geradas em construções anteriores.

Na primeira construção, temos $2^{n-3}$ possibilidades de sequências binárias.
Da construção 2 até a construção n - 2, temos $2^{n-4}$ possibilidades de sequências para cada construção.

Somando tudo, ficamos com um total de sequências binárias de tamanho $n$ com três zeros consecutivos igual a:

$2^{n-3}+\underbrace{2^{n-4}+...+2^{n-4}}_{(n-3)~\text{vezes}}=\boxed{2^{n-3}+(n-3)\cdot2^{n-4}}$