Quantas cadeias de bits com comprimento não excedente a
, em que
é um número inteiro positivo, compostas apenas de 1s são possíveis?
Passo 1
O enunciado pede para contar todas as cadeias de bits (strings de 0s e 1s) cujo comprimento é no máximo
e que são formadas apenas pelo dígito 1. Essa é uma aplicação direta do princípio fundamental da contagem: para cada comprimento permitido, contamos quantas cadeias satisfazem a condição.
Passo 2
Quais são os comprimentos possíveis? Como o comprimento não pode exceder
, as opções são
Aqui consideramos também a cadeia de comprimento zero (string vazia), pois normalmente ela faz parte do universo de cadeias de bits.
Passo 3
Para cada comprimento
há exatamente uma cadeia formada só por 1s, a saber:
- para
: a cadeia vazia, - para
: “1”, - para
: “11”, - …,
- para
: sequência de vezes “1”.
Logo, para cada
há exatamente 1 opção.
Passo 4
Somando as opções para todos os comprimentos de 0 até
, obtemos