Mostre que, usando o princípio da indução:
Se
e
é o conjunto das partes de
, mostre que
.
Se
Passo 1
O enunciado pede para provar, por indução em
, que se
então o conjunto das partes de
, denotado por
, satisfaz
O conteúdo é o princípio da indução matemática: mostramos um caso base e depois o passo indutivo.
Passo 2
(Caso base) Para
temos
então
é formado por exatamente dois subconjuntos. Logo
o que estabelece o caso base.
Passo 3
(Passo indutivo) Suponha que, para algum
, valha
Chamemos
Ak = 1,2,dots,k e
Ak+1=Akcupk+1 . Cada subconjunto de
Ak+1 ou não contém
k+1 , ou contém
k+1 .
- Os que não contêm
são exatamente os elementos dek+1 , ou seja, háP(Ak) deles.l|P(Ak)r|=2^k - Os que contêm
correspondem a tomar um subconjunto qualquerk+1 e formarBin P(Ak) . Também háBcupk+1 dessas escolhas.l|P(Ak)r|=2^k
Portanto
Isso completa o passo indutivo.
Resposta
Como o caso base e o passo indutivo estão estabelecidos, pelo princípio da indução segue que, para todo
n>=1 ,