[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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



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: <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
> =========================================================================
>

=========================================================================
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
=========================================================================