(ITA-63) Demonstrar a relação de Euler:
Passo 1
O enunciado pede para demonstrar a identidade de Vandermonde (também chamada de relação de Euler) para coeficientes binomiais, que diz que, dado dois inteiros não negativos
e um inteiro
com
, vale
O conteúdo necessário é o princípio multiplicativo na contagem e a ideia de particionar escolhas em casos mutuamente exclusivos.
Passo 2
Considere dois conjuntos disjuntos
e
, com
e
. Queremos contar de quantas formas podemos escolher
elementos do conjunto
. Separamos por quantos elementos vêm de
:
- Escolher exatamente
elementos de : há maneiras. - Escolher exatamente
elementos de : há maneiras.
Pelo princípio multiplicativo, para cadafixo há escolhas de total elementos com de .
Passo 3
Como os casos “escolher
de
” para
são mutuamente exclusivos e cobrem todas as possibilidades de escolher
elementos em
, somamos as contribuições:
o que corresponde exatamente à identidade desejada.