1. Prove as seguintes identidades
\begin{aligned} \binom{n}{r}\binom{r}{k} & =\binom{n}{k}\binom{n-k}{r-k} \\\ \binom{m}{0}\binom{n}{k}+\binom{m}{1}\binom{n}{k-1}+\cdots+\binom{m}{k}\binom{n}{0} & =\binom{m+n}{k} \\\ \binom{n}{0}\binom{m}{0}+\binom{n}{1}\binom{m}{1}+\cdots+\binom{n}{n}\binom{m}{n} & =\binom{m+n}{n} \\\ \binom{2}{2}+\binom{4}{2}+\cdots+\binom{2 n}{2} & =\frac{n(n+1)(4 n-1)}{6} \text { para todo } n \geq 2 \\\ (1 \times 1!)+(2 \times 2!)+\cdots+(n \times n!) & =(n+1)!-1 \text { para todo } n>0 \end{aligned}

Passo 1

O enunciado pede para provar cinco identidades envolvendo coeficientes binomiais e somas telescópicas. O conteúdo principal é combinatória (interpretação de \binom{n}{k}), propriedades algébricas de fatoriais e soma de potências (para os casos de \sum j e \sum j^2). Vamos usar (i) definição de coeficiente binomial via fatoriais e interpretação combinatória de “escolhas em etapas”, (ii) fórmulas clássicas de soma de inteiros e quadrados, e (iii) telescópio em somas de fatoriais.

Passo 2

Prova de \binom{n}{r}\binom{r}{k} = \binom{n}{k}\binom{n-k}{r-k} por álgebra de fatoriais:
\binom{n}{r}\binom{r}{k} = \frac{n!}{r!\,(n-r)!}\,\frac{r!}{k!\,(r-k)!} = \frac{n!}{k!\,(r-k)!\,(n-r)!}.
Agora fatoramos (n-r)!=\frac{(n-k)!}{(r-k)!} de modo que
\frac{n!}{k!\,(r-k)!\,(n-r)!} = \frac{n!}{k!\,(n-k)!}\,\frac{(n-k)!}{(r-k)!\,(n-r)!} = \binom{n}{k}\binom{n-k}{r-k}.

Passo 3

Prova de
\sum_{i=0}^{k}\binom{m}{i}\binom{n}{k-i} = \binom{m+n}{k}
por interpretação combinatória: queremos escolher k elementos de um conjunto de tamanho m+n dividido em dois blocos de tamanhos m e n. Se escolhemos i do primeiro bloco ( \binom{m}{i} formas) e k-i do segundo ( \binom{n}{k-i} formas), somando para i=0,1,\dots,k cobrimos todas as possibilidades, totalizando \binom{m+n}{k}.

Passo 4

Prova de
\sum_{i=0}^{n}\binom{n}{i}\binom{m}{i} = \binom{m+n}{n}.
Isto é caso especial da identidade do passo anterior com k=n, pois \binom{n}{i}\binom{m}{n-i} e em seguida permutar i\leftrightarrow n-i. Ou extração de coeficiente em
(1+x)^n\,(1+x)^m=\sum_{i=0}^{n}\binom{n}{i}x^i\;\sum_{j=0}^{m}\binom{m}{j}x^j =\sum_{k=0}^{m+n}\Bigl(\sum_{i+j=k}\binom{n}{i}\binom{m}{j}\Bigr)x^k,
e para k=n obtemos exatamente o sumatório acima igual a \binom{m+n}{n}.

Passo 5

Prova de
\sum_{j=1}^{n}\binom{2j}{2} = \frac{n(n+1)(4n-1)}{6}.
Note que
\binom{2j}{2} = \frac{2j(2j-1)}{2} = j(2j-1) = 2j^2 - j.
Logo
\sum_{j=1}^{n}\binom{2j}{2} = 2\sum_{j=1}^n j^2 \;-\;\sum_{j=1}^n j.
Sabemos que \sum_{j=1}^n j = \tfrac{n(n+1)}{2} e \sum_{j=1}^n j^2 = \tfrac{n(n+1)(2n+1)}{6}.
Substituindo:
2\cdot\tfrac{n(n+1)(2n+1)}{6} \;-\;\tfrac{n(n+1)}{2} = \tfrac{n(n+1)}{3}(2n+1) - \tfrac{n(n+1)}{2} = \tfrac{n(n+1)}{6}\bigl[2(2n+1)-3\bigr] = \tfrac{n(n+1)(4n-1)}{6}.

Passo 6

Prova de
\sum_{k=1}^{n} k\,k! = (n+1)! - 1.
Observe que
k\,k! = (k+1-1)\,k! = (k+1)! - k!.
Então a soma telescopa:
\sum_{k=1}^{n}\bigl[(k+1)! - k!\bigr] = (2! - 1!) + (3! - 2!) + \cdots + ((n+1)! - n!) = (n+1)! - 1!.
Como 1!=1, resulta (n+1)! - 1.

Resposta

\binom{n}{r}\binom{r}{k} \;=\;\binom{n}{k}\binom{n-k}{r-k}
\sum_{i=0}^{k}\binom{m}{i}\binom{n}{k-i} \;=\;\binom{m+n}{k}
\sum_{i=0}^{n}\binom{n}{i}\binom{m}{i} \;=\;\binom{m+n}{n}
\sum_{j=1}^{n}\binom{2j}{2} \;=\;\frac{n(n+1)(4n-1)}{6}
\sum_{k=1}^{n}k\,k! \;=\;(n+1)! - 1

Exercícios relacionados