Quantas cadeias de bits com comprimento não excedente a n, em que n é 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 n 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 n, as opções são
0,1,2,\dots,n.
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 k\in\{0,1,2,\dots,n\} há exatamente uma cadeia formada só por 1s, a saber:
  • para k=0: a cadeia vazia,
  • para k=1: “1”,
  • para k=2: “11”,
  • …,
  • para k=n: sequência de n vezes “1”.
Logo, para cada k há exatamente 1 opção.

Passo 4

Somando as opções para todos os comprimentos de 0 até n, obtemos
\sum_{k=0}^{n}1 = n+1.

Resposta

n+1

Exercícios de Livros Relacionados