Enunciado

A identidade a seguir é conhecida como a identidade combinatória de Fermat.

Forneça um argumento combinatório (cálculos não são necessários) para estabelecer essa identidade.

Dica: Considere o conjunto de números 1 até n. Quantos subconjuntos de tamanho k possuem i como o seu membro de maior número?

Passo 1

Opa galeeeeera! Hoje vamos entender um pouco mais sobre contagem.

O enunciado pede para argumentarmos porque a seguinte igualdade é verdadeira:

n k = ∑ i = k n i - 1 k - 1 ,   n ≥ k

Se pensarmos que queremos pegar um conjunto dos números naturais de 1 até n , onde o numero i seja o maior número. Poderíamos fixar este número i e depois escolher os k - 1 números restantes dentre os i - 1 números (Pois estes escolhidos precisam ser menores do que i ) e isto poderia ser feito de i - 1 k - 1 formas.

E poderíamos escolher este i de diversas formas, i pode ser igual a 1 e contarmos todas as formas que 1 seja o maior numero desse conjunto... E podemos fazer esta mesma conta para todos os i até n , assim “varrendo” todas as possibilidades contadas no n k .

Resposta

Ei, a resposta está no passo a passo :)