Use indução matemática para mostrar que um conjunto com n elementos tem 12 n(n-1) subconjuntos com exactamente dois elementos, para todo o n >= 2.

Passo 1

O enunciado pede para provar por indução matemática que um conjunto com n elementos tem exatamente 12 n(n-1) subconjuntos com dois elementos. O conteúdo principal aqui é o princípio de indução e a contagem de combinações simples de n elementos tomados 2 a 2.

Passo 2

Para o caso base n=2, um conjunto com 2 elementos, digamos a,b, só tem um único subconjunto de tamanho 2, que é a,b. Por outro lado, a fórmula dá
12cdot 2cdot(2-1)=12cdot2cdot1=1
Logo, o caso base está correto.

Passo 3

Suponha como hipótese de indução que todo conjunto com n elementos possui tfrac12n(n-1) subconjuntos de tamanho 2.

Passo 4

Para o passo de indução, considere um conjunto A com n+1 elementos. Escolha um elemento xin A e divida os subconjuntos de tamanho 2 em dois tipos:
  1. Os que não contêm x: são precisamente os subconjuntos de tamanho 2 de Asetminusx, que tem n elementos. Pela hipótese de indução, há
12,n(n-1)
subconjuntos desse tipo.
  1. Os que contêm x: cada subconjunto é x,y com y em um dos outros n elementos, gerando exatamente n subconjuntos.
Somando os dois casos, o total é
12n(n-1)+n=n(n-1)+2n2=n(n+1)2
Observe que n(n+1)/2=tfrac12(n+1)[(n+1)-1], ou seja, confere a fórmula para n+1.

Passo 5

Pela base e pelo passo de indução, concluímos que para todo n>=2 um conjunto com n elementos tem exatamente tfrac12n(n-1) subconjuntos de tamanho 2.

Resposta

Para todo n>=2, o número de subconjuntos de um conjunto com n elementos que têm exatamente 2 elementos é 12n(n-1).

Exercícios relacionados