Mostre que (a soma da linha de ordem
do triângulo de Pascal é):
Passo 1
O enunciado pede para provar a seguinte igualdade para todo inteiro
:
Informações relevantes dadas (explicitamente ou implicitamente):
- Os termos
são os coeficientes binomiais, para . - A soma vai por todos os
possíveis de até .
O objetivo é justificar, com uma explicação passo a passo e didática, por que essa soma vale.
Passo 2
Primeiro, vou explicar o que significa
— isso é essencial para entender a soma.
- Definição em palavras:
é o número de maneiras de escolher exatamente elementos distintos de um conjunto com elementos (sem considerar ordem). - Fórmula em termos de fatorial:
onde
(lê-se “
fatorial”) significa
(e por convenção
).
Explicando as variáveis: é o total de elementos disponíveis;
é quantos escolhemos; o denominador divide por
porque a ordem entre os
escolhidos não importa, e por
porque os não escolhidos também têm permutações que não distinguimos.
Explicando as variáveis:
Passo 3
Agora a ideia combinatória simples (contagem em dois jeitos), que é a prova mais direta e intuitiva:
- Considere um conjunto
com exatamente elementos distintos (por exemplo, ). - Queremos contar todas as possíveis subconjuntos de
(incluindo o subconjunto vazio e o próprio ).
Contagem 1 (direta, usando princípio multiplicativo):
- Para cada elemento de
existem duas possibilidades ao formar um subconjunto: ou o elemento está no subconjunto, ou não está. - Essas escolhas são independentes para os
elementos, então o número total de subconjuntos é
Aqui expliquei: cada elemento dá fator 2 (entrar/ não entrar), e pelos princípios básicos de contagem multiplicam-se as possibilidades.
Passo 4
Contagem 2 (classificando por tamanho):
- Outra maneira de contar todos os subconjuntos é agrupá‑los pelo número de elementos que têm.
- O número de subconjuntos que têm exatamente
elementos é (pela definição). - Portanto, somando sobre todos os possíveis tamanhos
, o número total de subconjuntos é
Passo 5
Comparando as duas contagens:
- O total de subconjuntos contado de forma direta deu
(Passo 3). - O total contado por tamanho deu
(Passo 4).
Como estamos contando a mesma coleção (todos os subconjuntos de), os dois resultados devem ser iguais. Logo
o que é exatamente a identidade pedida.
Passo 6
Para fixar a intuição, um exemplo pequeno:
.
- Os coeficientes são
, , , . - Somando:
. - E
. Funciona direitinho — a ideia geral é a mesma para todo .
Passo 7
Complemento (outra visão rápida usando o Teorema Binomial):
- O Teorema Binomial diz que, para quaisquer
,
- Tomando
e obtemos
o que fornece a mesma identidade de forma algébrica. (Intuição do porquê do Teorema Binomial: ao expandir
escolhe‑se em cada fator
se pega
ou
; escolher
em
dos
fatores pode ser feito de
maneiras.)