Prove, usando um argumento combinatório, a Fórmula de Euler
em seguida, use ela para mostrar a Fórmula de Lagrange
Passo 1
O enunciado pede duas coisas. Primeiro, provar por contagem que, para inteiros não negativos
com
, vale
Isso é conhecido como Fórmula de Euler (ou identidade de Vandermonde). Em seguida, usando esse resultado, mostrar que, tomando
e
, obtemos
que é a Fórmula de Lagrange. Para isso vamos precisar da interpretação combinatória de
como “número de maneiras de escolher
elementos de um conjunto de
elementos”.
Passo 2
Considere um conjunto
com
elementos e outro conjunto
disjunto de
com
elementos. Juntos eles formam um conjunto
de tamanho
. Se quisermos escolher exatamente
elementos de
, podemos proceder assim:
- Escolhemos
elementos de : há maneiras. - Escolhemos os
elementos restantes de : há maneiras.
Comopode variar de até , somamos todas as possibilidades e obtemos
Por outro lado, contar diretamente quantas formas há de escolher
de
elementos é
. Como ambas as contagens descrevem o mesmo processo, concluímos
Passo 3
Agora basta aplicar a fórmula de Euler com
,
e
. Temos
Mas
, logo o somatório vira
que é exatamente a Fórmula de Lagrange.