PERFEITO cara...valew mesmo... (rafael e domingos jr)
essa lista eh muito ativa...muito boa mesmo...brigado a todos...como eh
boa entender...
> 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
> =========================================================================
>
=========================================================================
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
=========================================================================
