(ITA-63) Demonstrar a relação de Euler:
\binom{m+n}{p}=\binom{m}{0}\binom{n}{p}+\binom{m}{1}\binom{n}{p-1}+\binom{m}{2}\binom{n}{p-2}+\ldots+\binom{m}{p}\binom{n}{0}

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 m,n e um inteiro p com 0\le p\le m+n, vale
\binom{m+n}{p} = \binom{m}{0}\binom{n}{p} +\binom{m}{1}\binom{n}{p-1} +\cdots +\binom{m}{p}\binom{n}{0}.
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 A e B, com \lvert A\rvert = m e \lvert B\rvert = n. Queremos contar de quantas formas podemos escolher p elementos do conjunto A\cup B. Separamos por quantos elementos vêm de A:
  • Escolher exatamente k elementos de A: há \binom{m}{k} maneiras.
  • Escolher exatamente p-k elementos de B: há \binom{n}{p-k} maneiras.
    Pelo princípio multiplicativo, para cada k fixo há \binom{m}{k}\binom{n}{p-k} escolhas de total p elementos com k de A.

Passo 3

Como os casos “escolher k de A” para k=0,1,\dots,p são mutuamente exclusivos e cobrem todas as possibilidades de escolher p elementos em A\cup B, somamos as contribuições:
\binom{m+n}{p} = \sum_{k=0}^{p}\binom{m}{k}\binom{n}{p-k},
o que corresponde exatamente à identidade desejada.

Resposta

\binom{m+n}{p} = \binom{m}{0}\binom{n}{p} +\binom{m}{1}\binom{n}{p-1} +\cdots +\binom{m}{p}\binom{n}{0}.

Exercícios de Livros Relacionados