Se o assunto � Matem�tica, n�o vejo por que n�o ser pertinente � lista.
Entretanto, s� n�o escreva e-mails com assunto "d�vidas". Creio que se possa
definir melhor sobre o que se est� escrevendo, isso � �timo para quem
acompanha as mensagens, acredite.
Sobre o que voc� quer provar, a demonstra��o mais freq�ente � a que se faz
por An�lise Combinat�ria, mas mostrarei as duas formas.
Pelo Princ�pio da Indu��o Finita (PIF):
Se n = 1, ent�o temos um conjunto A que possui 1 elemento, logo o conjunto
das partes (ou subconjuntos) de A tem dois elementos: o subconjunto vazio e
o subconjunto com o �nico elemento de A. Logo, n[P(A)] = 2^1 = 2 �
verdadeiro.
Agora, supondo-se que a propriedade seja verdadeira para n = p, provar-se-�
que ela � verdadeira para n = p + 1. Assim:
Hip�tese: n = p ==> n[P(A)] = 2^p
Tese: n = p + 1 ==> n[P(A)] = 2^(p+1)
n = p ==> n[P(A)] = 2^p
Somando-se 1 na primeira igualdade, dobra-se n[P(A)], pois somar 1 ao valor
de n significa adicionar um elemento ao conjunto A; aos subconjuntos
anteriormente formados poder-se-� acrescentar ou n�o o elemento que
adicionamos ao conjunto A, o que nos d� o dobro de possibilidades. Desse
modo:
n = p + 1 ==> n[P(A)] = 2 * 2^p
n = p + 1 ==> n[P(A)] = 2^(p+1)
(c.q.d.)
A outra forma, por An�lisa Combinat�ria, justifica a f�rmula. Suponha:
A = {1, 2, 3, 4, 5, ..., n}
Quais seriam os subconjuntos poss�veis de A? Primeiramente, o n�mero de
combina��es dos elementos de A escolhidos um a um; posteriormente, as
combina��es dos elementos de A escolhidos dois a dois; e, analogamente, at�
todos os elementos serem escolhidos. Dois detalhes s�o importantes: a ordem
de escolha desses elementos n�o importa para a forma��o do subconjunto, por
isso usamos as combina��es; e, por fim, lembre-se de que o conjunto vazio �
subconjunto de qualquer conjunto. Matematicamente:
C(n,0) + C(n,1) + C(n,2) + C(n,3) + ... + C(n,n)
em que C(n,k) = n!/[k!(n-k)!] s�o as combina��es de n elementos
tomados k a k.
C(n,0) ---- dos n elementos n�o se escolhe qualquer um (*)
C(n,1) ---- dos n elementos escolhe-se um deles
......
C(n,n-1) ---- dos n elementos escolhem-se n-1 elementos
C(n,n) ---- dos n elementos escolhem-se todos eles (**)
* Subconjunto vazio.
** Todo o conjunto est� contido nele pr�prio, por isso � subconjunto de si
mesmo.
Pelo teorema do bin�mio de Newton, temos:
(x + y)^n = Sum[C(n,k) * x^(n-k) * y^k, {k, 0, n}]
que significa que se est�o somando as parcelas C(n,k)*x^(n-k)*y^k,
com k variando de 0 a n.
Fazendo x = y = 1, teremos:
(1 + 1)^n = Sum[C(n,k) * 1^(n-k) * 1^k, {k, 0, n}]
2^n = Sum[C(n,k), {k, 0, n}] = C(n,0) + C(n,1) + C(n,2) + ... + C(n,n)
(c.q.d.)
Espero ter podido esclarecer a sua d�vida e seja bem-vindo � lista.
Abra�os,
Rafael de A. Sampaio
----- Original Message -----
From: <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
Sent: Saturday, March 27, 2004 5:33 PM
Subject: [obm-l] 2^n ? pq ?
oi pessoal, sou novo na lista e nao sei se o assunto eh pertinente:
ten um exercicio no livro 1 da colecao fundamentos de matematica
elementar, q pede o seguinte:
seja um conjunto A com n elementos. O conjunto P(A) tem 2^n elementos.
Prove pelo principio da inducao finita.
alguem poderia me ajudar ?
=========================================================================
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================
