A identidade
é 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
.
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
Passo 1
O enunciado apresenta a identidade
e pede três coisas:
- (a) Explicar o significado combinatório dessa identidade interpretando-a a partir do Triângulo de Pascal.
- (b) Demonstrar a identidade utilizando propriedades dos coeficientes binomiais.
- (c) Aplicar a identidade para calcular o valor de
.
Informações relevantes dadas (que vamos usar):
- A soma é sobre
de até . - Os símbolos
são coeficientes binomiais (assumimos e inteiros com ). - 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
— isso é essencial para a explicação e para a prova.
Definição e interpretação combinatória:
onde
é o fatorial de
. Mas a interpretação combinatória é mais útil:
é o número de maneiras de escolher um subconjunto com
elementos a partir de um conjunto de
elementos, sem considerar ordem. Ou seja, se tenho um conjunto com
elementos,
conta quantas escolhas de
elementos eu posso fazer.
Triângulo de Pascal (ideia visual):
- O Triângulo de Pascal organiza os coeficientes binomiais em linhas: a linha
contém . - A relação de Pascal diz que, para
e ,
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
para
obtemos
.
Interpretação por contagem: conte todas as maneiras de escolher um subconjunto com
elementos de um conjunto com
elementos. Seja o conjunto
. Toda escolha de
elementos tem um maior elemento — chame-o de
. Se o maior elemento escolhido for
, então os outros
elementos devem ser escolhidos entre os inteiros
. Para que exista uma escolha com maior elemento
, precisamos ter
, isto é,
.
Agora indexe
como
com
variando de
até
(porque
pode ir de
até
). Se o maior elemento é
, então escolhemos os outros
elementos dentre os
primeiros, o que pode ser feito de
maneiras. Logo, somando sobre todas as possibilidades de
obtém-se o total de subconjuntos de tamanho
de
:
Geométrica/visual no Triângulo de Pascal: essa soma corresponde a pegar uma “barra inclinada” do triângulo (os termos
) — formando o formato do “taco de hóquei” — e o resultado é a entrada logo abaixo e à direita do último termo somado, isto é,
. 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
temos
Reescrevendo, obtemos
Agora some essa igualdade para
variando de
até
:
O lado direito é uma soma telescópica: escrevendo alguns termos fica claro que os termos intermediários se cancelam:
Todos os termos internos
se cancelam em pares, sobrando apenas
Finalmente, observe que
(não é possível escolher
elementos de um conjunto com apenas
elementos), logo
que é exatamente a identidade desejada.
Passo 5
Aplicação numérica (parte (c)): calcular
.
Usamos a identidade com
e
:
Agora calculamos
pela fórmula:
Simplificando passo a passo (modo que você pode fazer na prova sem calculadora):
-
. -
. -
.
Alternativamente, somando os termos individuais (para conferir):
,
,
,
,
. Soma:
. Ambos os caminhos dão o mesmo resultado.
Resposta
(a) A soma
conta as maneiras de escolher
elementos de
classificando por qual é o maior elemento; para maior igual a
há
escolhas, logo a soma é
.\n
(b) Usando a identidade de Pascal e somando de
a
obtemos uma soma telescópica que resulta em
.\n
(c)
(b) Usando a identidade de Pascal
(c)