indução finita

Prévia do material em texto

Induc¸a˜o Finita
Rodrigo Carlos Silva de Lima ‡
rodrigo.uff.math@gmail.com
‡
1
Suma´rio
1 Induc¸a˜o 3
1.1 Princı´pio da induc¸a˜o finita . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 P0 :Princı´pio da boa ordenac¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Induc¸a˜o e somato´rios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4 Induc¸a˜o e divisibilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5 Induc¸a˜o e produto´rios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.6 Nu´mero de elementos do conjunto das partes e induc¸a˜o de primeira
forma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.7 Induc¸a˜o e desigualdades . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.7.1 Exercı´cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.8 Segundo princı´pio da induc¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.8.1 Teorema fundamental da aritme´tica . . . . . . . . . . . . . . . . . 13
1.8.2 Nu´mero de elementos do conjunto das partes . . . . . . . . . . . 14
2
Capı´tulo 1
Induc¸a˜o
1.1 Princı´pio da induc¸a˜o finita
Para provarmos que uma relac¸a˜o e´ va´lida para todo n ∈ N empregamos o princı´pio
da induc¸a˜o finita(P.I.F).
m Definic¸a˜o 1. Seja n0 um nu´mero natural, definimos Nn0 como o conjunto
dos nu´meros naturais n ≥ n0. Se n0 = 0 com isso temos N0 = N.
‡ Axioma 1 (Princı´pio da induc¸a˜o). Sejam P(n) uma proposic¸a˜o aplica´vel no con-
junto Nn0 , S um subconjunto de Nn0 tal que Pn seja verdadeira, a proposic¸a˜o Pn sera´
verdadeira para todo Nn0 (logo S = Nn0) quando:
1. P(n0) e´ verdadeira, isto e´, a propriedade e´ va´lida para n = n0 ( n0 ∈ S)
2. Se k ∈ Nn0 e P(k) e´ verdadeira (κ ∈ S), enta˜o P(k + 1) tambe´m e´ verdadeira
(k+ 1 ∈ S, isto e´ k+ 1 ∈ S sempre que k ∈ S ).
Nessas condic¸o˜es S conte´m todos elementos de Nn0
O P.I.F, sera´ usado para provar a maioria dos resultados neste texto, por isso ele
e de fundamental importaˆncia.
3
CAPI´TULO 1. INDUC¸A˜O 4
Z Exemplo 1. Vamos provar que a soma dos n primeiros inteiros positivos e´
n(n+ 1)/2.
Isto e´
n∑
i=0
i = 1+ 2+ 3+ ...+ n = n(n+ 1)/2
da definic¸a˜o de somato´rio temos que
n∑
i=0
i =
n−1∑
i=0
i+ n
e
0∑
i=0
i = 0
temos que mostrar inicialmente que a proposic¸a˜o e´ va´lida para n = 1. Para n = 1,
temos
1∑
i=0
i = 1 = 1(1+ 1)/2
faremos agora a hipo´tese de que a propriedade e´ va´lida para n − 1 (obs: apenas
coloque n− 1 no lugar de n na hipotese)
n−1∑
i=0
i = (n− 1)(n)/2
a partir da hipo´tese da validade pra n− 1 devemos mostrar que vale para n
enta˜o devemos mostrar que
n∑
i=0
i = (n)(n+ 1)/2
mas pela definic¸a˜o de somato´rio temos
n∑
i=0
i =
n−1∑
i=0
i+ n
e da hipo´tese
n−1∑
i=0
i = (n− 1)(n)/2
CAPI´TULO 1. INDUC¸A˜O 5
substituindo a hipo´tese
n∑
i=0
i =
n−1∑
i=0
i+ n
n∑
i=0
i = (n− 1)(n)/2+ n
colocando n em evideˆncia
(n)[(n− 1)/2+ 1] = (n)[n− 1+ 2]/2 = (n)(n+ 1)/2
enta˜o esta provado que
n∑
i=0
i = (n+ 1)(n)/2
Todas as provas foram feitas em cima das definic¸o˜es, isso mostra a importaˆncia
de ter definic¸o˜es formais do que se quer provar.
Vamos agora provar o resultado acima de maneira menos formal, sem usar a
notac¸a˜o de somato´rio, e vamos mostrar um metodo de deduc¸a˜o para a fo´rmula
Tambe´m.
Informal
Tomando a soma
1+ 2+ 3+ ...++n− 2n− 1+ n = s
n+ n− 1+ n− 2+ ...+ 3+ 2+ 1 = s
somando ambas termo a termo n com 1,2 com n− 1 e continuando assim, ficamos
com n termos n+ 1, isto e´
2s = n(n+ 1)
logo
s =
n(n+ 1)
2
.
Essa maneira pode ser usada como deduc¸a˜o da fo´rmula pore´m uma prova mais
formal pode ser feita por induc¸a˜o novamente.
Para n = 1 temos
1 = 1(1+ 1)/2
CAPI´TULO 1. INDUC¸A˜O 6
Tomando a hipo´tese para n
1+ 2+ 3+ ...+ n = n(n+ 1)
2
e tentando provar para n+ 1
1+ 2+ 3+ ...+ n+ n+ 1
sabemos que 1+ 2+ 3+ ...+ n = n(n+ 1)
2
da hipo´tese, substituindo ficamos com
1+ 2+ 3+ ...+ n+ n+ 1 = n(n+ 1)
2
+ (n+ 1) = (n+ 1)(n+ 2)
2
.
Logo esta provado.
1.2 P0 :Princı´pio da boa ordenac¸a˜o
‡ Axioma 2. Todo conjunto na˜o vazio de inteiros na˜o negativos conte´m um elemento
mı´nimo, em sı´mbolos, para todo subconjunto S de Z, tal que S 6= ∅ e ∀p ∈ S tivermos
p ≥ 0 enta˜o S conte´m um elemento p0 tal que para todo p ∈ S se verifica p ≥ p0.
O princı´pio da boa ordenac¸a˜o e´ um axioma equivalente ao princı´pio da induc¸a˜o,
axiomas A e B sa˜o equivalentes quando podemos a partir de A demonstrar B e a
partir de B demonstrar A. Vamos enta˜o demonstrar o princı´pio da induc¸a˜o a partir
do princı´pio da boa ordenac¸a˜o.
b Propriedade 1 (P1:Princı´pio da induc¸a˜o). Sejam P(n) uma proposic¸a˜o aplica´vel
no conjunto Nn0 , S um subconjunto de Nn0 tal que Pn seja verdadeira, a proposic¸a˜o
Pn sera´ verdadeira para todo Nn0 (logo S = Nn0) quando:
1. P(n0) e´ verdadeira, isto e´, a propriedade e´ va´lida para n = n0 ( n0 ∈ S)
2. Se k ∈ Nn0 e P(k) e´ verdadeira (κ ∈ S), enta˜o P(k + 1) tambe´m e´ verdadeira
(k+ 1 ∈ S, isto e´ k+ 1 ∈ S sempre que k ∈ S ).
Nessas condic¸o˜es S conte´m todos elementos de Nn0
CAPI´TULO 1. INDUC¸A˜O 7
ê Demonstrac¸a˜o.
Vamos fazer a demonstrac¸a˜o por absurdo. Considere que o princı´pio da induc¸a˜o
seja verdadeiro, pore´m o conjunto S na˜o seja igual a Nn0 .
Como S e´ subconjunto de Nn0 , deve haver um conjunto S ′ tal que a proposic¸a˜o
P(n) seja falsa com S ∪ S ′ = Nn0 e S ∩ S ′ = ∅ pois uma proposic¸a˜o na˜o pode ser
verdadeira e falsa.
O conjunto S ′ deve ser na˜o vazio de nu´meros na˜o negativos (pois Nn0 e´ um
subconjunto dos nu´meros naturais, logo seus subconjuntos so´ possuem elementos
na˜o negativos) logo o princı´pio da boa ordenac¸a˜o e´ aplica´vel tendo o conjunto S ′ um
menor elemento l.
Esse elemento deve ser diferente de n0 pois por hipo´tese esse elemento pertence
a S, como l >n0 e´ o menor elemento de S ′, temos que l − 1 ≥ n0 esta´ em Nn0 e em
S, mas pelo princı´pio da induc¸a˜o se l − 1 ∈ S, l − 1 + 1 = l ∈ S logo chegamos a
um absurdo pois l na˜o pode pertencer a S e S ′, assim o princı´pio da induc¸a˜o esta´
provado.
b Propriedade 2 (P2:Segundo princı´pio da induc¸a˜o). Sejam P(n) uma proposic¸a˜o
aplica´vel no conjunto Nn0 , S um subconjunto de Nn0 tal que Pn seja verdadeira,
a proposic¸a˜o Pn sera´ verdadeira para todo Nn0 (logo S = Nn0) quando:
1. P(n0) e´ verdadeira, isto e´, a propriedade e´ va´lida para n = n0 ( n0 ∈ S)
2. Se para todo t ∈ Nn0 e t ∈ [n0, k] com k ≥ n0 natural tivermos P(t) e´
verdadeira , enta˜o P(k + 1) tambe´m e´ verdadeira (k + 1 ∈ S, isto e´ k + 1 ∈ S
sempre que todo t ∈ Nn0 e t ∈ [n0, k] ∈ S ).
Nessas condic¸o˜es S conte´m todos elementos de Nn0
ê Demonstrac¸a˜o.
Vamos mostrar que P1 ⇒ P2, o primeiro princı´pio da induc¸a˜o implica o segundo.
Seja U um conjunto onde sa˜o satisfeitas as condic¸o˜es de P2, devemos mostrar que
U = Nn0 . Vamos denotar por An a sentenc¸a "os naturais de n0 ate´ n (incluindo os
naturais n0 e n) esta˜o em U. An0 e´ verdadeira pois por hipo´tese de P2, n0 esta´ em
U", assumindo que Ak e´ verdadeira para um natural k ≥ n0. Enta˜o os inteiros de n0
CAPI´TULO 1. INDUC¸A˜O 8
ate´ k esta˜o em U e por hipo´tese de P2, k + 1 esta´ em U, implicando assim que Ak+1
e´ verdadeira, logo pelo princı´pio da induc¸a˜o P1 aplicado em An, An sera´ verdadeira
para todo n ∈ Nn0 e portanto U = Nn0 .
Para terminar a demonstrac¸a˜o de que o princı´pio da induc¸a˜o e´ equivalente ao
princı´pio da boa ordenac¸a˜o, vamos demonstrar que P2 =⇒ P0
F Teorema 1 (Princı´pio da boa ordenac¸a˜o). Todo conjunto na˜o vazio de inteiros
na˜o negativos conte´m um elemento mı´nimo.
ê Demonstrac¸a˜o. Seja S um conjunto na˜o vazio de inteiros na˜o negativos.
Devemos mostrar queS possui um elemento mı´nimo. Assumindo que S na˜o possui
elemento mı´nimo e denotando por Un a sentenc¸a "n na˜o e´ um elemento de S".
Temos que B0 e´ verdadeira, pois se 0 ∈ S ele seria seu elemento mı´nimo. Assumindo
agora que Bk e´ verdadeira para todo n de 0 ate´ k (incluindo 0 e k), temos que os
elementos de 0 ate´ k na˜o pertencem a S, se o elemento k+ 1 estivesse em S, seria seu
menor elemento enta˜o, na˜o pode estar, sendo assim Bk+1 verdadeira e por P2, Bn seria
verdadeira pra todos naturais, implicando o conjunto S ser vazio, que e´ contra´rio a
hipo´tese, logo temos o teorema provado.
1.3 Induc¸a˜o e somato´rios
Z Exemplo 2. Mostrar que
n∑
k=1
1
k(k+ 1)(k+ 2)
=
n(n+ 3)
4(n+ 1)(n+ 2)
.
Para n = 1 temos
1∑
k=1
1
k(k+ 1)(k+ 2)
=
1
1(2)(3)
=
1
6
=
1(4)
4(2)(3)
=
1
6
.
Supondo a validade para n
n∑
k=1
1
k(k+ 1)(k+ 2)
=
n(n+ 3)
4(n+ 1)(n+ 2)
CAPI´TULO 1. INDUC¸A˜O 9
vamos provar para n+ 1
n+1∑
k=1
1
k(k+ 1)(k+ 2)
=
(n+ 1)(n+ 4)
4(n+ 2)(n+ 3)
.
n+1∑
k=1
1
k(k+ 1)(k+ 2)
=
n(n+ 3)
4(n+ 1)(n+ 2)
+
1
(n+ 1)(n+ 2)(n+ 3)
=
=
1
(n+ 1)(n+ 2)
(
n(n+ 3)
4
+
1
n+ 3
) =
n(n+ 3)2 + 4
4(n+ 1)(n+ 2)(n+ 3)
agora n(n+ 3)2 + 4 = n3 + 6n2 + 9n+ 4 = (n+ 1)2(n+ 4) enta˜o
n+1∑
k=1
1
k(k+ 1)(k+ 2)
=
(n+ 1)(n+ 4)
4(n+ 2)(n+ 3)
.
Z Exemplo 3. Mostrar por induc¸a˜o que
(a− 1)
n∑
k=0
ak = an+1 − 1.
Para n = 1 temos
(a− 1)
1∑
k=0
ak = (a− 1)(a+ 1) = a2 − 1.
Supondo que (a − 1)
n∑
k=0
ak = an+1 − 1 vamos provar que (a − 1)
n+1∑
k=0
ak = an+2 − 1.
Por definic¸a˜o de somato´rio e pela hipo´tese da induc¸a˜o temos
(a− 1)
n+1∑
k=0
ak = (a− 1)an+1 + (a− 1)
n∑
k=0
ak = an+2 − an+1 + an+1 − 1 = an+2 − 1 .
1.4 Induc¸a˜o e divisibilidade
Z Exemplo 4. Mostrar que 6|52n − 1 para todo n ∈ N. Para n = 0 vale
6|50 − 1 = 0. Supondo que 6|52n − 1, vamos mostrar que 6|52n+2 − 1.
CAPI´TULO 1. INDUC¸A˜O 10
52n+2 − 1 = 25.52n − 1 = 24.52n + 52n − 1︸ ︷︷ ︸
6|
seis divide as duas parcelas enta˜o divide a soma .
Z Exemplo 5. Mostrar que 5|42n+1 + 6n+1 n ∈ N. Para n = 0, 5|4 + 6 = 10.
Supondo para n, vamos provar para n+ 1.
42n+1+2 + 6n+1+1 = 42n+1.16+ 6.6n+1 = 6.(42n+1 + 6n+1) + 10.42n+1
segue enta˜o por induc¸a˜o.
1.5 Induc¸a˜o e produto´rios
Z Exemplo 6. Mostre que se n ≥ 4 enta˜o n! > 2n.
Para n = 4 vale 4! = 24 > 24 = 16. Suponha validade para n , n! > 2n, vamos
provar para n+ 1, (n+ 1)! > 2n+1. Multiplicando n! > 2n por n+ 1 de ambos lados
segue que
(n+ 1)! > (n+ 1)︸ ︷︷ ︸
>2
2n > 2.2n = 2n+1 .
1.6 Nu´mero de elementos do conjunto das partes e
induc¸a˜o de primeira forma
b Propriedade 3. Seja |A| = n enta˜o |P(A)| = 2n. Onde |A| simboliza o nu´mero
de elementos de A e P(A) o conjunto dos subconjuntos de A, chamado de conjunto
das partes.
ê Demonstrac¸a˜o. Por induc¸a˜o sobre n, se n = 1, enta˜o A = {a1} possui dois
subconjuntos que sa˜o ∅ e {α1}. Suponha que qualquer conjunto qualquer B com n
CAPI´TULO 1. INDUC¸A˜O 11
elementos tenha |P(B)| = 2n, vamos provar que um conjunto C com n + 1 elementos
implica |P(C)| = 2n+1. Tomamos um elemento a ∈ C, C \ {a} possui 2n subconjuntos
(por hipo´tese da induc¸a˜o), sk de k = 1 ate´ k = 2n, que tambe´m sa˜o subconjuntos de
C, pore´m podemos formar mais 2n subconjuntos de C com a unia˜o do elemento {a},
logo no total temos 2n + 2n = 2n+1 subconjuntos de C e mais nenhum subconjunto,
pois na˜o temos nenhum outro elemento para unir aos subconjuntos dados.
1.7 Induc¸a˜o e desigualdades
Z Exemplo 7. Mostre que
(1+ x)n ≥ 1+ nx+ n(n− 1)x
2
2
para n natural e x ≥ 0. Vamos chamar
C(n, x) = 1+ nx+ n(n− 1)x
2
2
.
Para n = 0 temos
(1+ x)0 = 1 = 1+ 0x+ 0(0− 1)x
2
2
= 1
logo vale a igualdade considere agora a validade da hipo´tese
(1+ x)n ≥ 1+ nx+ n(n− 1)x
2
2
vamos mostrar que vale
(1+x)n+1 ≥ 1+(n+1)x+(n+1)(n)x
2
2
= 1+
(
n+ 1
1
)
x+
(
n+ 1
2
)
x2 = 1+nx+n(n− 1)x
2
2
+x+nx2
(1+ x)n+1 ≥ C(n, x) + x+ nx2
onde usamos a relac¸a˜o de Stiefel, multiplicando a desigualdade da hipo´tese da
induc¸a˜o por 1+x, na˜o alteramos a desigualdade pois 1+x e´ positivo, temos enta˜o
(1+ x)n+1 ≥ C(n, x)(1+ x) = C(n, x) + C(n, x)x
CAPI´TULO 1. INDUC¸A˜O 12
agora vamos mostrar que
C(n, x) + C(n, x)x ≥ C(n, x) + x+ nx2
vale pois equivale a
C(n, x)x ≥ x+ nx2
que vale se x = 0, agora se x > 0 equivale a
C(n, x) ≥ 1+ nx
1+ nx+ n(n− 1)x
2
2
≥ 1+ nx⇔ n(n− 1)x2
2
≥ 0
se n = 0 ou n = 1 vale, agora se n 6= 0, 1 vale pois temos x2 > 0.
1.7.1 Exercı´cios
Prove usando induc¸a˜o
1+ 2+ 3+ ...+ n =
n∑
i=0
i =
n(n+ 1)
2
∀ n ∈ N. (1.1)
2+ 5+ 8+ ...+ 2+ 3n =
n∑
i=0
2+ 3i = n(3n+ 4)
2
∀ n ∈ N. (1.2)
20 + 21 + 22 + ...+ 2n−1 =
n−1∑
i=0
2i = 2n − 1 ∀ n ∈ N. (1.3)
12 + 22 + 32 + ...+ n2 =
n∑
i=0
i2 =
n(n+ 1)(2n+ 1)
6
∀ n ∈ N. (1.4)
13|22+4n + 32+4n ∀ n ∈ N. (1.5)
64|32n+1 + 40n− 67 ∀ n ∈ N. (1.6)
1+ 3+ 5+ ...+ 2n− 1 =
n∑
i=0
2i− 1 = n2 ∀ n ∈ N. (1.7)
CAPI´TULO 1. INDUC¸A˜O 13
n∑
k=1
k3 =
[
n(n+ 1)
2
]2
n∑
k=1
k3 =
[
n(n+ 1)
2
]2
1.8 Segundo princı´pio da induc¸a˜o
b Propriedade 4 (P2:Segundo princı´pio da induc¸a˜o). Sejam P(n) uma proposic¸a˜o
aplica´vel no conjunto dos naturais.
Se
1. P(0) for verdadeira .
2. E se o fato de P(k) for verdadeira para todo k ∈ N com 0 ≤ k ≤ n implicar
P(n+ 1) tambe´m verdadeira, enta˜o
P(n) e´ verdadeira para todo n natural .
A parte (2) e´ chamada de hipo´tese de induc¸a˜o e a parte (1) de base da induc¸a˜o .
1.8.1 Teorema fundamental da aritme´tica
b Propriedade 5 (Existeˆncia da fatorac¸a˜o em primos). Seja n > 1 um nu´mero
natural, enta˜o n pode ser escrito como produto de primos .
ê Demonstrac¸a˜o. Caso n = 2 enta˜o n e´ produto´rio de primo, n =
1∏
k=1
pk onde
pk = 2, provamos a base da induc¸a˜o .
Suponha que todo nu´mero menor que n e maior que 1 natural, possa ser escrito
como produto de primos (hipo´tese da induc¸a˜o), enta˜o vamos mostrar que n tambe´m
pode ser escrito como produto de primos .
Se n e´ primo, nada pecisamos fazer . Caso n na˜o seja primo, enta˜o ele e´ composto,
podendo ser escrito como n = m.s, onde m e s sa˜o maiores que 1 e menores que n,
aplicamos a hipo´tese da induc¸a˜o em m e n, o que implica
CAPI´TULO 1. INDUC¸A˜O 14
m =
t∏
k=1
pk, s =
w∏
k=t+1
pk
sa˜o produto de primos, enta˜o
n = m.n =
w∏
k=1
pk
e´ produto de primos .
b Propriedade 6 (Unicidade da fatorac¸a˜o em primos). Seja n ∈ N,n > 1. Se
n =
m∏
k=1
pk =
s∏
k=1
qk onde cada pk e qk sa˜o primos, na˜o necessariamente distintos
enta˜o m = s e pk = qk∀ k , apo´s, se necessa´rio, uma renomeac¸a˜o dos termos.
ê Demonstrac¸a˜o. Vamos provar usando o segundo princı´pio da induc¸a˜o, para
n = 2 a propriedade vale. Suponha a validade para todo t < n vamos provar que
nessas condic¸o˜es vale para n.
n = pm
m−1∏
k=1
pk = qs
s−1∏
k=1
qk
pm divide o produto
s∏
k=1
qk enta˜o deve dividir um dos fatores, por exemplo qs (se
na˜o, renomeamos os termos), como pm|qs enta˜o pm = qs
pm
m−1∏
k=1
pk = pm
s−1∏
k=1
qk ⇒ m−1∏
k=1
pk =
s−1∏
k=1
qk = n0 < n
como n0 e´ menor que n, usamos a hipo´tese da induc¸a˜o, que implica m − 1 = s − 1,
qk = pk de k = 1 ate´ m− 1, daı´ segue que m = n e qk = pk de k = 1 ate´ m.
1.8.2 Nu´mero de elementos do conjunto das partes
b Propriedade 7. Se A possui n elementos enta˜o o seu conjunto das partes
possui 2n elementos. Conjunto das partes de A e´ o conjunto P(A) de subconjuntos
de A .
CAPI´TULO 1. INDUC¸A˜O 15
ê Demonstrac¸a˜o.
Iremos provar a seguinte propriedade, por induc¸a˜o de segunda forma . Se An
possui n elementos, enta˜o
Se A = ∅ e´ vazio enta˜o P(A) possui apenas um elemento que e´ o conjuntovazio,
portanto a base da induc¸a˜o esta´ verificada, A possui 0 elementos e P(A) possui 20 = 1
elemento .
Suponha, por hipo´tese de induc¸a˜o que todo conjunto A com pelo menos k ele-
mentos possua 2k subconjuntos com k elementos, para 1 ≤ k ≤ n − 1, vamos provar
que se A possui n elementos enta˜o tem 2n subconjuntos .
Seja A = {a1, · · · , an} enta˜o um conjunto com n elementos , para contar quantos
subconjuntos ele possui podemos separar
A = {a1, · · · , an−2}︸ ︷︷ ︸
B
∪{an−1, an}.
B possui n−2 elementos, por isso possui 2n−2 subconjuntos por hipo´tese de induc¸a˜o ,
a cada subconjunto desses tomando a unia˜o com {an−1} formamos no total mais 2n−2
conjunto e com unia˜o de {an} formamos mais 2n−2 e por fim com unia˜o de {an−1, an},
formamos mais 2n−2 conjuntos, enta˜o temos no total
4.2n−2 = 222n−2 = 2n
subconjuntos.
	Indução
	Princípio da indução finita
	P0:Princípio da boa ordenação
	Indução e somatórios
	Indução e divisibilidade
	Indução e produtórios
	Número de elementos do conjunto das partes e indução de primeira forma
	Indução e desigualdades
	 Exercícios
	Segundo princípio da indução
	Teorema fundamental da aritmética
	Número de elementos do conjunto das partes