Mostre que, usando o princípio da indução:
Se A=1,2,3, ldots, n e P(A) é o conjunto das partes de A, mostre que |P(A)|=2^n.

Passo 1

O enunciado pede para provar, por indução em n, que se
A = 1,2,dots,n
então o conjunto das partes de A, denotado por P(A), satisfaz
|P(A)| = 2^n
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 n=1 temos
A = 1,
então
P(A) = varnothing,1
é formado por exatamente dois subconjuntos. Logo
|P(A)| = 2 = 2^1,
o que estabelece o caso base.

Passo 3

(Passo indutivo) Suponha que, para algum k>=1, valha
l|;P(1,2,dots,k)r| = 2^k
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.
  1. Os que não contêm k+1 são exatamente os elementos de P(Ak), ou seja, há l|P(Ak)r|=2^k deles.
  2. Os que contêm k+1 correspondem a tomar um subconjunto qualquer Bin P(Ak) e formar Bcupk+1. Também há l|P(Ak)r|=2^k dessas escolhas.
Portanto
l|P(Ak+1)r| = underbracel|P(Ak)r|2^k + underbracel|P(Ak)r|2^k =2cdot2^k =2^k+1
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,
l|P(1,2,dots,n)r| = 2^n

Exercícios relacionados