Demonstre:
.
Passo 1
O enunciado pede para demonstrar a igualdade
Ou seja, listar claramente: a soma à esquerda é
e o objetivo é provar que essa soma vale
para todo inteiro
.
Passo 2
Vamos entender o que é cada pedaço da soma (sem resolver ainda). O símbolo
significa “n escolhe k”, isto é, o número de subconjuntos de tamanho
que se pode formar a partir de um conjunto de
elementos. Formalmente,
onde
é o fatorial de
. Um exemplo para fixar a ideia: se
, então
,
,
.
Passo 3
Interpretação combinatória da soma à esquerda. Pense num conjunto fixo com
elementos (por exemplo,
). Considere pares ordenados
tais que:
-
é um subconjunto não-vazio de , -
é um elemento de (ou seja, um elemento “destacado” dentro de ).
Agora vamos contar quantos pares
existem, agrupando por tamanho do subconjunto
. Se
tem exatamente
elementos, então:
- o número de escolhas de
com tamanho é , - para cada tal
há exatamente opções para escolher o elemento destacado dentro de .
Logo, o número de pares
com
é
. Somando sobre todos os tamanhos possíveis
obtemos exatamente a soma do enunciado:
Passo 4
Contagem alternativa (mais direta) dos mesmos pares
. Em vez de agrupar por tamanho de
, vamos construir um par
em duas etapas:
- Escolher o elemento destacado
. Há escolhas possíveis para . - Depois de escolhido
, escolher arbitrariamente quais dos outros elementos entram ou não em . Cada um dos elementos restantes pode estar ou não em , independentemente, então há escolhas possíveis do conjunto dos outros elementos. (Aqui permitimos que nenhum dos outros elementos entre, porque já temos em , então nunca fica vazio.)
Portanto, contando dessa maneira:
Passo 5
Igualando as duas contagens do mesmo conjunto de pares
(Passo 3 e Passo 4) obtemos
Isso é exatamente a identidade que precisava ser demonstrada.
Passo 6
Um exemplo numérico rápido para ganhar confiança. Tome
. A soma do enunciado é
A fórmula do lado direito dá
. Confere!
Passo 7
(Prova alternativa — via fórmula do binômio e diferencial, caso goste de manipulações algébricas.) A identidade do binômio diz
Derivando ambos os lados em relação a
obtemos
Multiplicando por
:
Agora basta definir
para que o lado esquerdo vire
e o lado direito vire a soma desejada. Logo a identidade vale.
Passo 8
Resumo e incentivo: demonstrámos a identidade de duas maneiras — uma combinatória (contando pares
de dois jeitos) e outra algébrica (derivando o binômio). Ambas são válidas; a combinatória é muitas vezes mais intuitiva em provas rápidas de competição ou na prova da faculdade. Você conseguiu! Respira, reveja os passos devagar e pratique com
para fixar.