Prove, usando um argumento combinatório, a Fórmula de Euler

Passo 1

O enunciado pede que provemos, por contagem combinatória, a identidade
sumk=0^p binommk,binomhp-k ;=;binomm+hp
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 p elementos de um conjunto de tamanho m+h.

Passo 2

Interprete o lado direito binomm+hp como o número de maneiras de escolher um subconjunto de tamanho p a partir de um conjunto total com m+h elementos.

Passo 3

Agora, imagine que esse conjunto de m+h elementos esteja dividido em dois blocos: um bloco A com m elementos e um bloco B com h elementos. Toda escolha de p elementos do conjunto total pode ser descrita pelo número k de elementos que vêm de A e, consequentemente, p-k elementos que vêm de B.

Passo 4

Se fixarmos exatamente k elementos escolhidos de A, temos binommk maneiras de escolhê-los. Para completar os p elementos, escolhemos os p-k restantes de B, o que pode ser feito de binomhp-k maneiras. Como k pode variar de 0 até p, o total de formas de escolher p elementos, separando por cada k, é
sumk=0^p binommk,binomhp-k

Passo 5

Concluímos que as duas contagens — direta, escolhendo p de m+h elementos, e via partição em dois blocos somando sobre k escolhas em A — devem ser iguais. Assim,
sumk=0^p binommk,binomhp-k ;=;binomm+hp

Resposta

A identidade está provada.

Exercícios de Livros Relacionados