Use indução matemática para mostrar que um conjunto com
elementos tem
subconjuntos com exactamente dois elementos, para todo o
.
Passo 1
O enunciado pede para provar por indução matemática que um conjunto com
elementos tem exatamente
subconjuntos com dois elementos. O conteúdo principal aqui é o princípio de indução e a contagem de combinações simples de
elementos tomados 2 a 2.
Passo 2
Para o caso base
, um conjunto com 2 elementos, digamos
, só tem um único subconjunto de tamanho 2, que é
. Por outro lado, a fórmula dá
Logo, o caso base está correto.
Passo 3
Suponha como hipótese de indução que todo conjunto com
elementos possui
subconjuntos de tamanho 2.
Passo 4
Para o passo de indução, considere um conjunto
com
elementos. Escolha um elemento
e divida os subconjuntos de tamanho 2 em dois tipos:
- Os que não contêm
: são precisamente os subconjuntos de tamanho 2 de , que tem elementos. Pela hipótese de indução, há
subconjuntos desse tipo.
- Os que contêm
: cada subconjunto é com em um dos outros elementos, gerando exatamente subconjuntos.
Somando os dois casos, o total é
Observe que
, ou seja, confere a fórmula para
.
Passo 5
Pela base e pelo passo de indução, concluímos que para todo
um conjunto com
elementos tem exatamente
subconjuntos de tamanho 2.
Resposta
Para todo
, o número de subconjuntos de um conjunto com
elementos que têm exatamente 2 elementos é
.