QUESTÃO Prove por indução que se
, então
.
Passo 1
Vamos começar entendendo o que a questão pede. Precisamos provar, usando o princípio da indução matemática, que se um conjunto
tem
elementos (isto é,
), então o número de subconjuntos de
, representado por
, é igual a
. Para isso, vamos precisar entender como a indução funciona e aplicar isso passo a passo.
Passo 2
Caso Base: Vamos verificar se a afirmação é verdadeira para
.
Quando
, o conjunto
é o conjunto vazio, ou seja,
. O conjunto das partes de
,
, contém apenas um subconjunto, que é o próprio conjunto vazio. Então:
E como
, temos que:
Portanto, o caso base é verdadeiro.
Passo 3
Hipótese de Indução: Suponha que a afirmação seja verdadeira para algum inteiro
, ou seja, suponha que para um conjunto
com
, vale que:
Passo 4
Passo Indutivo: Precisamos mostrar que a afirmação também é verdadeira para
. Ou seja, para um conjunto
com
, devemos provar que:
Considere o conjunto
como a união de um conjunto
com
elementos e um novo elemento
, ou seja,
. Cada subconjunto de
ou não contém o elemento
, ou contém
.
- Os subconjuntos que não contêm
são exatamente os subconjuntos de , e há deles (pela hipótese de indução). - Os subconjuntos que contêm
são obtidos adicionando a cada subconjunto de , também totalizando .
Portanto, o número total de subconjuntos de
é:
Resposta
Assim, por indução matemática, provamos que se
, então
.