Mostre que, se n >= k >= r >= 0 : sumj=0^nbinomnjbinomjr=2^n-rbinomnr

Passo 1

Beleza, vamos entender o que a questão está pedindo. A gente precisa provar que, para números inteiros , e onde , a soma das combinações é igual a .
Aqui, estamos lidando com combinações e identidades combinatórias. Vamos usar propriedades de binômios e manipulações de somas envolvendo coeficientes binomiais para resolver isso.

Passo 2

Primeiro, vamos entender o que significa binomnjbinomjr = binomnrbinomn - rj - r . Esse termo representa o número de maneiras de escolher itens de um total de , e depois escolher itens desses . Podemos reescrever isso usando uma propriedade das combinações:
Isso porque primeiro escolhemos os itens e depois os restantes.

Passo 3

Agora, substituímos essa expressão na soma original:
sumj=0^nbinomnjbinomjr = binomnr sumj=0^n binomn - rj - r
Note que, mudando o índice da soma para sumj=0^n binomn - rj - r = sumj'= -r^n - r binomn - rj' , temos:
sumj'=0^n - r binomn - rj'
Como para ou , a soma simplifica para:

Passo 4

A soma das combinações de sumj'=0^n - r binomn - rj' = 2^n - r até de é uma identidade conhecida que vale . Ou seja:
Isso vem do fato de que a soma dos coeficientes binomiais para um dado é , já que representa todas as possíveis combinações.

Passo 5

Substituindo de volta na expressão original, temos:
sumj=0^nbinomnjbinomjr = binomnr cdot 2^n - r

Resposta

Portanto, mostramos que:
sumj=0^nbinomnjbinomjr = 2^n - rbinomnr

Exercícios relacionados