Prove, usando um argumento combinatório, a Fórmula de Euler
C_{m}^{0} C_{h}^{p}+C_{m}^{1} C_{h}^{p-1}+C_{m}^{2} C_{h}^{p-2}+\ldots+C_{m}^{p} C_{h}^{0}=C_{m+h}^{p} em seguida, use ela para mostrar a Fórmula de Lagrange
\left(C_{n}^{0}\right)^{2}+\left(C_{n}^{1}\right)^{2}+\left(C_{n}^{2}\right)^{2}+\ldots+\left(C_{n}^{n}\right)^{2}=C_{2 n}^{n}

Passo 1

O enunciado pede duas coisas. Primeiro, provar por contagem que, para inteiros não negativos m,h,p com 0\le p\le m+h, vale
\sum_{k=0}^{p} \binom{m}{k}\,\binom{h}{p-k} \;=\;\binom{m+h}{p}.
Isso é conhecido como Fórmula de Euler (ou identidade de Vandermonde). Em seguida, usando esse resultado, mostrar que, tomando m=h=n e p=n, obtemos
\sum_{k=0}^{n} \bigl(\binom{n}{k}\bigr)^{2} \;=\;\binom{2n}{n},
que é a Fórmula de Lagrange. Para isso vamos precisar da interpretação combinatória de \binom{x}{y} como “número de maneiras de escolher y elementos de um conjunto de x elementos”.

Passo 2

Considere um conjunto A com m elementos e outro conjunto B disjunto de A com h elementos. Juntos eles formam um conjunto A\cup B de tamanho m+h. Se quisermos escolher exatamente p elementos de A\cup B, podemos proceder assim:
  • Escolhemos k elementos de A: há \binom{m}{k} maneiras.
  • Escolhemos os p-k elementos restantes de B: há \binom{h}{p-k} maneiras.
    Como k pode variar de 0 até p, somamos todas as possibilidades e obtemos
\sum_{k=0}^{p} \binom{m}{k}\,\binom{h}{p-k}.
Por outro lado, contar diretamente quantas formas há de escolher p de (m+h) elementos é \binom{m+h}{p}. Como ambas as contagens descrevem o mesmo processo, concluímos
\sum_{k=0}^{p} \binom{m}{k}\,\binom{h}{p-k} \;=\;\binom{m+h}{p}.

Passo 3

Agora basta aplicar a fórmula de Euler com m=n, h=n e p=n. Temos
\sum_{k=0}^{n} \binom{n}{k}\,\binom{n}{n-k} \;=\;\binom{2n}{n}.
Mas \binom{n}{n-k}=\binom{n}{k}, logo o somatório vira
\sum_{k=0}^{n} \bigl(\binom{n}{k}\bigr)^{2} \;=\;\binom{2n}{n},
que é exatamente a Fórmula de Lagrange.

Resposta

\sum_{k=0}^{p} \binom{m}{k}\,\binom{h}{p-k} \;=\;\binom{m+h}{p},
\sum_{k=0}^{n} \bigl(\binom{n}{k}\bigr)^{2} \;=\;\binom{2n}{n}.

Exercícios relacionados