Mostre a identidade
\binom{k}{k}+\binom{k+1}{k}+\ldots+\binom{n}{k}=\binom{n+1}{k+1} .

Passo 1

O enunciado pede para provar a igualdade
\binom{k}{k}+\binom{k+1}{k}+\ldots+\binom{n}{k}=\binom{n+1}{k+1},
supondo que k e n são inteiros com 0\le k\le n.
As informações relevantes são: a soma começa em \binom{k}{k} e vai até \binom{n}{k}; o objetivo é mostrar que essa soma é igual a \binom{n+1}{k+1}.

Passo 2

Primeiro, lembrar o que é \binom{a}{b}. Definição e interpretação combinatória:
  • Definição algébrica: \displaystyle \binom{a}{b}=\frac{a!}{b!(a-b)!} sempre que 0\le b\le a. Aqui a! significa o fatorial de a (produto a(a-1)\cdots1).
  • Interpretação combinatória (útil para provas): \displaystyle \binom{a}{b} é o número de formas de escolher b elementos distintos de um conjunto com a elementos (ou seja, o número de subconjuntos de tamanho b).
Exemplo rápido para fixar: \displaystyle \binom{4}{2}=\frac{4!}{2!2!}=\frac{24}{4}=6. Isso corresponde aos 6 pares distintos que se pode formar a partir de 4 elementos.

Passo 3

Prova combinatória (intuitiva e direta — a clássica “identidade do bastão de hóquei”):
Considere um conjunto S com n+1 elementos, por exemplo S=\{1,2,\dots,n+1\}. O número total de subconjuntos de S com exatamente k+1 elementos é, pela definição, \displaystyle \binom{n+1}{k+1}.
Agora contamos esses mesmos subconjuntos de outra maneira: pelo valor do maior elemento do subconjunto. Seja m o maior elemento de um subconjunto de tamanho k+1. Como o subconjunto tem k+1 elementos e m é o maior, os outros k elementos devem ser escolhidos entre os m-1 elementos menores que m. Portanto, para um dado m o número de subconjuntos de tamanho k+1 cujo maior elemento é m é \displaystyle \binom{m-1}{k}.
Quais valores pode assumir m? Para que seja possível formar um subconjunto de k+1 elementos, o menor m possível é k+1 (quando os elementos são 1,2,\ldots,k+1) e o maior m possível é n+1. Assim m varia por m=k+1,k+2,\dots,n+1.
Somando a contribuição de cada m obtemos o total de subconjuntos de tamanho k+1:
\binom{k}{k}+\binom{k+1}{k}+\binom{k+2}{k}+\cdots+\binom{n}{k} =\sum_{m=k+1}^{n+1}\binom{m-1}{k}.
Fazendo a mudança de índice j=m-1 (então j vai de k a n) essa soma fica
\sum_{j=k}^{n}\binom{j}{k}.
Pelo argumento de contagem, essa soma conta exatamente todos os subconjuntos de S com k+1 elementos, logo
\sum_{j=k}^{n}\binom{j}{k}=\binom{n+1}{k+1}.
Reescrevendo a soma na forma do enunciado obtemos a identidade desejada:
\binom{k}{k}+\binom{k+1}{k}+\ldots+\binom{n}{k}=\binom{n+1}{k+1}.

Passo 4

Prova alternativa por indução (para quem gosta de ver a versão algébrica):
Base ( n=k): a soma tem só um termo \binom{k}{k}=1 e a direita é \binom{k+1}{k+1}=1. Verdade.
Passo indutivo: suponha que para certo n\ge k valha
\sum_{j=k}^{n}\binom{j}{k}=\binom{n+1}{k+1}.
Então, somando o próximo termo \binom{n+1}{k},
\sum_{j=k}^{n+1}\binom{j}{k} =\binom{n+1}{k+1}+\binom{n+1}{k}.
Usa-se a identidade de Pascal (que pode ser entendida combinatoriamente: ao escolher k elementos de n+1 considere se um elemento fixo está ou não no subconjunto), a saber
\binom{n+1}{k+1}+\binom{n+1}{k}=\binom{n+2}{k+1}.
Portanto
\sum_{j=k}^{n+1}\binom{j}{k}=\binom{n+2}{k+1},
que é exatamente a forma da identidade para n substituído por n+1. Assim a propriedade vale para todo n\ge k por indução.

Passo 5

Resumo final: a soma dos binomiais \displaystyle \binom{j}{k} de j=k até j=n conta, via dois métodos, o número de subconjuntos de tamanho k+1 de um conjunto com n+1 elementos; por isso a soma é \displaystyle \binom{n+1}{k+1}. A identidade está demonstrada.

Resposta

\binom{k}{k}+\binom{k+1}{k}+\ldots+\binom{n}{k}=\binom{n+1}{k+1}.

Exercícios relacionados