Prove, usando um argumento combinatório, a Fórmula de Euler
Passo 1
O enunciado pede que provemos, por contagem combinatória, a identidade
O conteúdo aqui é interpretação de coeficientes binomiais como número de formas de escolher subconjuntos, e a ideia é contar de duas maneiras o número de escolhas de
elementos de um conjunto de tamanho
.
Passo 2
Interprete o lado direito
como o número de maneiras de escolher um subconjunto de tamanho
a partir de um conjunto total com
elementos.
Passo 3
Agora, imagine que esse conjunto de
elementos esteja dividido em dois blocos: um bloco
com
elementos e um bloco
com
elementos. Toda escolha de
elementos do conjunto total pode ser descrita pelo número
de elementos que vêm de
e, consequentemente,
elementos que vêm de
.
Passo 4
Se fixarmos exatamente
elementos escolhidos de
, temos
maneiras de escolhê-los. Para completar os
elementos, escolhemos os
restantes de
, o que pode ser feito de
maneiras. Como
pode variar de
até
, o total de formas de escolher
elementos, separando por cada
, é
Passo 5
Concluímos que as duas contagens — direta, escolhendo
de
elementos, e via partição em dois blocos somando sobre
escolhas em
— devem ser iguais. Assim,
Resposta
A identidade está provada.