Re: [obm-l] 2^n ? pq ?

["Rafael" <cyberhelp@xxxxxxxxxx>]

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: <bernardo@macacos.org>
To: <obm-l@mat.puc-rio.br>
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
=========================================================================