Prove que sumk=0^n binomnk=2^n.

Passo 1

Beleza, o enunciado pede pra provar que
sumk=0^n binomnk = 2^n
Isso cai em combinatória básica e, mais precisamente, na definição de coeficiente binomial e no “conto de subconjuntos”. A gente vai precisar entender o que é e como contar de duas maneiras o número total de subconjuntos de um conjunto de tamanho .

Passo 2

Primeiro, lembra o que é o coeficiente binomial binomnk = n!k!,(n-k)!, :
e esse carinha conta de quantas formas diferentes você escolhe elementos num conjunto de . Então, é só a soma de todas essas escolhas, pra .

Passo 3

Agora a ideia-chave: imagine um conjunto com elementos (pode ser , por exemplo).
  • O número de subconjuntos de tamanho exatamente é .
  • Se você quer contar todos os subconjuntos (dos que têm 0 elementos até os que têm elementos), basta somar para até . Isso dá exatamente o lado esquerdo .
Por outro lado, dá pra contar direto: para cada um dos elementos, você decide “está” ou “não está” no subconjunto. São 2 escolhas independentes por elemento, logo (com fatores) igual a . Então o total de subconjuntos é .

Resposta

sumk=0^n binomnk = 2^n

Exercícios relacionados