A identidade \sum_{i=k}^{n}\binom{i}{k}=\binom{n+1}{k+1} é conhecida como Identidade do Taco de Hóquei (ou Hockey-stick Identity).
a) Explique o significado combinatório dessa identidade, interpretando-a a partir do Triângulo de Pascal.
b) Demonstre a identidade utilizando as propriedades dos coeficientes binomiais.
c) Aplique a identidade para calcular o valor de \sum_{i=3}^{7}\binom{i}{3}.

Passo 1

O enunciado apresenta a identidade
\sum_{i=k}^{n}\binom{i}{k}=\binom{n+1}{k+1}
e pede três coisas:
  1. (a) Explicar o significado combinatório dessa identidade interpretando-a a partir do Triângulo de Pascal.
  2. (b) Demonstrar a identidade utilizando propriedades dos coeficientes binomiais.
  3. (c) Aplicar a identidade para calcular o valor de \sum_{i=3}^{7}\binom{i}{3}.
Informações relevantes dadas (que vamos usar):
  • A soma é sobre i de i=k até i=n.
  • Os símbolos \binom{i}{k} são coeficientes binomiais (assumimos n e k inteiros com 0\le k\le n).
  • A identidade relaciona uma soma de coeficientes binomiais (uma “coluna” inclinada do Triângulo de Pascal) a um único coeficiente binomial.

Passo 2

Primeiro, vamos lembrar e entender o que significa \binom{n}{k} — isso é essencial para a explicação e para a prova.
Definição e interpretação combinatória:
\binom{n}{k}=\frac{n!}{k!(n-k)!},
onde n! é o fatorial de n. Mas a interpretação combinatória é mais útil: \binom{n}{k} é o número de maneiras de escolher um subconjunto com k elementos a partir de um conjunto de n elementos, sem considerar ordem. Ou seja, se tenho um conjunto com n elementos, \binom{n}{k} conta quantas escolhas de k elementos eu posso fazer.
Triângulo de Pascal (ideia visual):
  • O Triângulo de Pascal organiza os coeficientes binomiais em linhas: a linha n contém \binom{n}{0},\binom{n}{1},\dots,\binom{n}{n}.
  • A relação de Pascal diz que, para n\ge1 e 1\le k\le n,
\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}.
Isso significa que cada entrada (exceto as bordas) é a soma das duas acima dela.
Vou usar essas ideias (escolha de subconjuntos e a relação de Pascal) nas próximas etapas.

Passo 3

Interpretação combinatória (resposta da parte (a)) — versão detalhada e intuição com o Triângulo de Pascal:
Queremos entender por que somando \binom{i}{k} para i=k,k+1,\dots,n obtemos \binom{n+1}{k+1}.
Interpretação por contagem: conte todas as maneiras de escolher um subconjunto com k+1 elementos de um conjunto com n+1 elementos. Seja o conjunto \{1,2,\dots,n+1\}. Toda escolha de k+1 elementos tem um maior elemento — chame-o de m. Se o maior elemento escolhido for m, então os outros k elementos devem ser escolhidos entre os inteiros 1,2,\dots,m-1. Para que exista uma escolha com maior elemento m, precisamos ter m-1\ge k, isto é, m\ge k+1.
Agora indexe m como i+1 com i variando de k até n (porque m pode ir de k+1 até n+1). Se o maior elemento é i+1, então escolhemos os outros k elementos dentre os i primeiros, o que pode ser feito de \binom{i}{k} maneiras. Logo, somando sobre todas as possibilidades de i obtém-se o total de subconjuntos de tamanho k+1 de \{1,\dots,n+1\}:
\sum_{i=k}^{n}\binom{i}{k}=\binom{n+1}{k+1}.
Geométrica/visual no Triângulo de Pascal: essa soma corresponde a pegar uma “barra inclinada” do triângulo (os termos \binom{k}{k},\binom{k+1}{k},\dots,\binom{n}{k}) — formando o formato do “taco de hóquei” — e o resultado é a entrada logo abaixo e à direita do último termo somado, isto é, \binom{n+1}{k+1}. Isso é exatamente a interpretação combinatória que liga a contagem por maior elemento à posição no Triângulo de Pascal.

Passo 4

Demonstração algébrica usando propriedades dos coeficientes binomiais (parte (b)) — prova por telescópica com a relação de Pascal:
Usamos a relação de Pascal em forma rearranjada. Para i\ge k temos
\binom{i+1}{k+1}=\binom{i}{k+1}+\binom{i}{k}.
Reescrevendo, obtemos
\binom{i}{k}=\binom{i+1}{k+1}-\binom{i}{k+1}.
Agora some essa igualdade para i variando de i=k até i=n:
\sum_{i=k}^{n}\binom{i}{k}=\sum_{i=k}^{n}\bigl(\binom{i+1}{k+1}-\binom{i}{k+1}\bigr).
O lado direito é uma soma telescópica: escrevendo alguns termos fica claro que os termos intermediários se cancelam:
\begin{aligned} \sum_{i=k}^{n}\bigl(\binom{i+1}{k+1}-\binom{i}{k+1}\bigr) &= \bigl(\binom{k+1}{k+1}-\binom{k}{k+1}\bigr) + \bigl(\binom{k+2}{k+1}-\binom{k+1}{k+1}\bigr) \\\ &\quad + \cdots + \bigl(\binom{n+1}{k+1}-\binom{n}{k+1}\bigr). \end{aligned}
Todos os termos internos \binom{k+1}{k+1},\binom{k+2}{k+1},\dots,\binom{n}{k+1} se cancelam em pares, sobrando apenas
\sum_{i=k}^{n}\binom{i}{k}=\binom{n+1}{k+1}-\binom{k}{k+1}.
Finalmente, observe que \binom{k}{k+1}=0 (não é possível escolher k+1 elementos de um conjunto com apenas k elementos), logo
\sum_{i=k}^{n}\binom{i}{k}=\binom{n+1}{k+1},
que é exatamente a identidade desejada.

Passo 5

Aplicação numérica (parte (c)): calcular \sum_{i=3}^{7}\binom{i}{3}.
Usamos a identidade com k=3 e n=7:
\sum_{i=3}^{7}\binom{i}{3}=\binom{7+1}{3+1}=\binom{8}{4}.
Agora calculamos \binom{8}{4} pela fórmula:
\binom{8}{4}=\frac{8\cdot7\cdot6\cdot5}{4\cdot3\cdot2\cdot1}.
Simplificando passo a passo (modo que você pode fazer na prova sem calculadora):
  • 4\cdot3\cdot2\cdot1=24.
  • 8\cdot7\cdot6\cdot5 = 8\cdot7\cdot30 = 56\cdot30 = 1680.
  • \dfrac{1680}{24}=\dfrac{1680}{8\cdot3}=\dfrac{210}{3}=70.
Alternativamente, somando os termos individuais (para conferir): \binom{3}{3}=1, \binom{4}{3}=4, \binom{5}{3}=10, \binom{6}{3}=20, \binom{7}{3}=35. Soma: 1+4+10+20+35=70. Ambos os caminhos dão o mesmo resultado.

Resposta

(a) A soma \sum_{i=k}^{n}\binom{i}{k} conta as maneiras de escolher k+1 elementos de \{1,\dots,n+1\} classificando por qual é o maior elemento; para maior igual a i+1 \binom{i}{k} escolhas, logo a soma é \binom{n+1}{k+1}.\n
(b) Usando a identidade de Pascal \binom{i+1}{k+1}=\binom{i}{k+1}+\binom{i}{k} e somando de i=k a n obtemos uma soma telescópica que resulta em \binom{n+1}{k+1}.\n
(c) \sum_{i=3}^{7}\binom{i}{3}=\binom{8}{4}=70

Exercícios relacionados