Demonstre a relação de Stifel, isto é:
binomnp=binomn-1p-1+binomn-1p forall n in N, n >= 2 e p <= n

Solução

Consideremos um conjunto A com n elementos, e consideremos um deteminado elemento a in A. Vamos calcular o número de combinações dos elementos de A, tomados p a p, de dois modos:
1: modo: Diretamente pela fórmula, isto é, binomnp
2? modo: Calculamos o número de combinações que não possuam o elemento a.
Tal número é binomn-1p.
Em seguida, calculamos o número de combinações que possuem o elemento
a. Tal número é binomn-1p-1.
Ao todo, o número de combinações será:
binomn-1p+binomn-1p-1(2)
De (1) e (2) concluímos que:
binomnp=binomn-1p-1+binomn-1p

Passo 1

O enunciado pede para provar a relação de Stifel para coeficientes binomiais, ou seja, mostrar que, para todo ninN com n>=2 e todo p tal que 0<= p<= n,
binomnp ;=;binomn-1p-1+binomn-1p
O conteúdo envolvido é contagem de combinações e a ideia é usar uma argumentação combinatória (princípio da partição) para contar, de dois modos, o número de subconjuntos de tamanho p de um conjunto de n elementos.

Passo 2

Escolha um elemento fixo a em um conjunto A com lvert Arvert = n. Todo subconjunto de A que tem exatamente p elementos cabe em uma das duas categorias mutuamente exclusivas: ou contém a, ou não contém a.

Passo 3

Contagem dos subconjuntos de tamanho p que não contêm a!: basta escolher p elementos entre os n-1 restantes, o que fornece
binomn-1p
subconjuntos.

Passo 4

Contagem dos subconjuntos de tamanho p que contêm a!: como a já está incluído, restam p-1 vagas a preencher com elementos dos n-1 restantes, o que dá
binomn-1p-1
subconjuntos.

Passo 5

Pelo princípio da adição, o total de subconjuntos de A de tamanho p é a soma das duas contagens:
binomnp ;=; underbracebinomn-1psubstacknão contém a ;+; underbracebinomn-1p-1substackcontém a ãéé

Resposta

binomnp=binomn-1p-1+binomn-1p

Exercícios de Livros Relacionados