Mostre a identidade
Passo 1
O enunciado pede para provar a igualdade
supondo que
e
são inteiros com
.
As informações relevantes são: a soma começa em e vai até
; o objetivo é mostrar que essa soma é igual a
.
As informações relevantes são: a soma começa em
Passo 2
Primeiro, lembrar o que é
. Definição e interpretação combinatória:
- Definição algébrica:
sempre que . Aqui significa o fatorial de (produto ). - Interpretação combinatória (útil para provas):
é o número de formas de escolher elementos distintos de um conjunto com elementos (ou seja, o número de subconjuntos de tamanho ).
Exemplo rápido para fixar:
. Isso corresponde aos 6 pares distintos que se pode formar a partir de 4 elementos.
Passo 3
Prova combinatória (intuitiva e direta — a clássica “identidade do bastão de hóquei”):
Considere um conjunto
com
elementos, por exemplo
. O número total de subconjuntos de
com exatamente
elementos é, pela definição,
.
Agora contamos esses mesmos subconjuntos de outra maneira: pelo valor do maior elemento do subconjunto. Seja
o maior elemento de um subconjunto de tamanho
. Como o subconjunto tem
elementos e
é o maior, os outros
elementos devem ser escolhidos entre os
elementos menores que
. Portanto, para um dado
o número de subconjuntos de tamanho
cujo maior elemento é
é
.
Quais valores pode assumir
? Para que seja possível formar um subconjunto de
elementos, o menor
possível é
(quando os elementos são
) e o maior
possível é
. Assim
varia por
.
Somando a contribuição de cada
obtemos o total de subconjuntos de tamanho
:
Fazendo a mudança de índice
(então
vai de
a
) essa soma fica
Pelo argumento de contagem, essa soma conta exatamente todos os subconjuntos de
com
elementos, logo
Reescrevendo a soma na forma do enunciado obtemos a identidade desejada:
Passo 4
Prova alternativa por indução (para quem gosta de ver a versão algébrica):
Base (
): a soma tem só um termo
e a direita é
. Verdade.
Passo indutivo: suponha que para certo
valha
Então, somando o próximo termo
,
Usa-se a identidade de Pascal (que pode ser entendida combinatoriamente: ao escolher
elementos de
considere se um elemento fixo está ou não no subconjunto), a saber
Portanto
que é exatamente a forma da identidade para
substituído por
. Assim a propriedade vale para todo
por indução.
Passo 5
Resumo final: a soma dos binomiais
de
até
conta, via dois métodos, o número de subconjuntos de tamanho
de um conjunto com
elementos; por isso a soma é
. A identidade está demonstrada.