date:20090530

[obm-l] Indução para n+1 e (n-1, n)

2009-05-30 Por tôpico HugLeo

Eu posso substituir n na minha fórmula de reccorrência para provar para n+1,
mas se eu substituir para n-1 para provar n também funciona.
Alguém saberia explicar?

O exemplo está abaixo:

n = 2^n -1

T(n) = 2T(n) + 1

Para n
T(n) = 2T(n-1) + 1 = 2(2^[n-1] - 1) + 1 = 2^n -1


Para n+1

T(n+1) = 2T(n) + 1 = 2(2^n -1) + 1 = 2^[n+1] + 1

Qual das duas alternativas é certa ou melhor e por que funciona?



-- 
-hUgLeO-♑

Re: [obm-l] Acai berry, Your ticket to a new life

2009-05-30 Por tôpico HugLeo

Já jogou spam de mais na lista, não acha?

On Fri, May 29, 2009 at 10:46 PM, lucianarodrigg...@uol.com.br wrote:

Em 21/05/2009 20:46, *nico...@mat.puc-rio.br* escreveu:

If you have trouble viewing this e-mail, please click
herehttp://www.uijobil.cn/?xuoxzggedxqrq
.

*Everyone http://www.uijobil.cn/?xuoxzggedxqrq
Will Want http://www.uijobil.cn/?xuoxzggedxqrq
Your New Secret http://www.uijobil.cn/?xuoxzggedxqrq

ACAI POWER SLIM http://www.uijobil.cn/?xuoxzggedxqrq
*

Discover the secret today!
Click here for details http://www.uijobil.cn/?xuoxzggedxqrq

To review our Privacy Policy, please *click
herehttp://www.uijobil.cn/?xuoxzggedxqrq
*.

To ensure the delivery of your informative updates from Dr. Lark and the
Daily Balance
Team, please add
*nico...@mat.puc-rio.brhttp://mce_host/compose?to=nico...@mat.puc
*to your email address book.

TO UNSUBSCRIBE
You are receiving this e-mail at nico...@mat.puc-rio.br because you
indicated an interest in receiving special updates and offers from Dr.
Lark.
We hope that you find these updates helpful, but if you would rather not
receive them, you can unsubscribe by clicking
herehttp://www.uijobil.cn/?xuoxzggedxqrq.
You will be
immediately unsubscribed from our database. Remember, your personal
information
will only be used by Healthy Directions, LLC, for editorial and marketing
purposes.
Thank you.

*Daily Balance
700 Indian Springs Drive
Lancaster, PA 17601*
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.htmlhttp://www.mat.puc-rio.br/%7Eobmlistas/obm-l.html=

=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.htmlhttp://www.mat.puc-rio.br/%7Eobmlistas/obm-l.html=

--
-hUgLeO-♑

[obm-l] Re: [obm-l] Indução para n+1 e (n-1, n)

2009-05-30 Por tôpico Rafael Ando

As duas alternativas são iguais, não tem uma melhor que a outra.

Para entender porque funciona, vc entende pq a indução funciona? Se uma
afirmação vale para o valor inicial, e vc consegue provar que, quando ela
vale para um certo valor, também vale para o próximo, então a afirmação vale
para todos os valores. Dá pra ver que tanto mostrando que f(n) - f(n+1), ou
que f(n-1) - f(n), conseguimos mostrar que quando ela vale para um certo
valor, também vale para o próximo.

O seu exemplo é meio estranho! n = 2^n -1 não é uma equação verdadeira, pra
começar... Acho que vc quis dizer:

Seja T(n) = 2^n - 1. Prove que T(n) = 2T(n-1) + 1. Não é necessário
indução para provar essa. O que vc fez está correto, mas não é indução...
vc só substituiu a equação de T(n) e mostrou que vale.

Por outro lado, se tivéssemos:

Seja T(0) = 0 e T(n) = 2T(n-1) + 1, n0. Prove T(n) = 2^n -1 (n≥0). (note
que os dois problemas são diferentes).

Nesse caso poderíamos usar indução para demostrar... Verificamos que o caso
inicial vale substituindo n=0. Em seguida, demostra-se (como acima) que se
hipótese vale para n-1, então vale para n. Poderíamos, é claro, também ter
provado a hipótese para n+1 a partir de n, também daria certo.

2009/5/30 HugLeo hugocana...@gmail.com

 Eu posso substituir n na minha fórmula de reccorrência para provar para
 n+1, mas se eu substituir para n-1 para provar n também funciona.
 Alguém saberia explicar?

 O exemplo está abaixo:

 n = 2^n -1

 T(n) = 2T(n) + 1

 Para n
 T(n) = 2T(n-1) + 1 = 2(2^[n-1] - 1) + 1 = 2^n -1


 Para n+1

 T(n+1) = 2T(n) + 1 = 2(2^n -1) + 1 = 2^[n+1] + 1

 Qual das duas alternativas é certa ou melhor e por que funciona?



 --
 -hUgLeO-♑




-- 
Rafael

Re: [obm-l] Ajuda em probabilidade

2009-05-30 Por tôpico Fernando Lima Gama Junior

Também não entendi...
Fernando Gama




2009/5/29 Rafael Ando rafael.a...@gmail.com

 ?

 Rita, não entendo como vc está pensando...

 2009/5/29 RitaGomes rcggo...@terra.com.br

  Como agora ela esta na terceira posição, fazemos a permutação de 3, que
 6 e descontamos 1 condição ficando com 5 possibilidades de sair na terceira
 posição.

 - Original Message -
  *From:* Fernando Lima Gama Junior fgam...@gmail.com
 *To:* obm-l@mat.puc-rio.br
  *Sent:* Friday, May 29, 2009 8:56 PM
 *Subject:* Re: [obm-l] Ajuda em probabilidade

 Qual seria a chance, então, de ela ser tirada até a terceira bola?

 Fernando Gama

 Sent from Brasilia, Distrito Federal, Brazil


 2009/5/29 RitaGomes rcggo...@terra.com.br

  Fernando,

 Como são 5 bolas e 1 sendo preta, fazemos permutação de 5 que é 240,
 porem a preta deve ser a última a ser retirada. Faz permutação de 4, que é
 24 , sendo a possibilidade da bola preta sair em ordem diferente da última.
 Desconta do totoal das condições, ou seja 240 - 24 = 216 possibilidades
 de ser a última a ser retirada.
 Espero não ter feito o cálculo errado, pois estou meio atorodoada aqui
 com outros estudos.

 Rita Gomes

   - Original Message -
  *From:* Fernando Lima Gama Junior fgam...@gmail.com
 *To:* obm-l@mat.puc-rio.br
 *Sent:* Friday, May 29, 2009 7:18 PM
 *Subject:* [obm-l] Ajuda em probabilidade

 Uma urna tem 5 bolas, sendo 1 preta e as outra 4 brancas. As bolas são
 retiradas da urna sem reposição. Qual a chance de até a bola preta ser a
 última a ser retirada?

 Fernando Gama


  --
 Esta mensagem foi verificada pelo E-mail Protegido Terra.
 Atualizado em 29/05/2009

  --


 No virus found in this incoming message.
 Checked by AVG - www.avg.com
 Version: 8.5.339 / Virus Database: 270.12.46/2142 - Release Date:
 05/29/09 17:53:00


  --
 Esta mensagem foi verificada pelo E-mail Protegido Terra.
 Atualizado em 29/05/2009

  --


 No virus found in this incoming message.
 Checked by AVG - www.avg.com
 Version: 8.5.339 / Virus Database: 270.12.46/2142 - Release Date: 05/29/09
 17:53:00




 --
 Rafael

[obm-l] Re: [obm-l] Re: [obm-l] Indução para n+1 e (n-1, n )

2009-05-30 Por tôpico HugLeo

Sim, eu escrevi errado, o certo é como você disse: T(n) = 2^n - 1

Muito obrigado pela explicação, agora deu para entender ;-)

Só mais um detalhe:
Você disse ..Em seguida, demostra-se (como acima) que se hipótese vale para
n-1, então vale para n...
Seria assim né?:
T(n)=2(2^[n-1] - 1) + 1
T(n)=2^n -1


2009/5/30 Rafael Ando rafael.a...@gmail.com

 As duas alternativas são iguais, não tem uma melhor que a outra.

 Para entender porque funciona, vc entende pq a indução funciona? Se uma
 afirmação vale para o valor inicial, e vc consegue provar que, quando ela
 vale para um certo valor, também vale para o próximo, então a afirmação vale
 para todos os valores. Dá pra ver que tanto mostrando que f(n) - f(n+1), ou
 que f(n-1) - f(n), conseguimos mostrar que quando ela vale para um certo
 valor, também vale para o próximo.

 O seu exemplo é meio estranho! n = 2^n -1 não é uma equação verdadeira, pra
 começar... Acho que vc quis dizer:

 Seja T(n) = 2^n - 1. Prove que T(n) = 2T(n-1) + 1. Não é necessário
 indução para provar essa. O que vc fez está correto, mas não é indução...
 vc só substituiu a equação de T(n) e mostrou que vale.

 Por outro lado, se tivéssemos:

 Seja T(0) = 0 e T(n) = 2T(n-1) + 1, n0. Prove T(n) = 2^n -1 (n≥0). (note
 que os dois problemas são diferentes).

 Nesse caso poderíamos usar indução para demostrar... Verificamos que o caso
 inicial vale substituindo n=0. Em seguida, demostra-se (como acima) que se
 hipótese vale para n-1, então vale para n. Poderíamos, é claro, também ter
 provado a hipótese para n+1 a partir de n, também daria certo.

 2009/5/30 HugLeo hugocana...@gmail.com

 Eu posso substituir n na minha fórmula de reccorrência para provar para
 n+1, mas se eu substituir para n-1 para provar n também funciona.
 Alguém saberia explicar?

 O exemplo está abaixo:

 n = 2^n -1

 T(n) = 2T(n) + 1

 Para n
 T(n) = 2T(n-1) + 1 = 2(2^[n-1] - 1) + 1 = 2^n -1


 Para n+1

 T(n+1) = 2T(n) + 1 = 2(2^n -1) + 1 = 2^[n+1] + 1

 Qual das duas alternativas é certa ou melhor e por que funciona?



 --
 -hUgLeO-♑




 --
 Rafael




-- 
-hUgLeO-♑

[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Indução para n +1 e (n-1, n)

2009-05-30 Por tôpico Rafael Ando

Isso, seria assim mesmo :)

2009/5/30 HugLeo hugocana...@gmail.com

 Sim, eu escrevi errado, o certo é como você disse: T(n) = 2^n - 1

 Muito obrigado pela explicação, agora deu para entender ;-)

 Só mais um detalhe:
 Você disse ..Em seguida, demostra-se (como acima) que se hipótese vale
 para n-1, então vale para n...
 Seria assim né?:
 T(n)=2(2^[n-1] - 1) + 1
 T(n)=2^n -1


 2009/5/30 Rafael Ando rafael.a...@gmail.com

 As duas alternativas são iguais, não tem uma melhor que a outra.

 Para entender porque funciona, vc entende pq a indução funciona? Se uma
 afirmação vale para o valor inicial, e vc consegue provar que, quando ela
 vale para um certo valor, também vale para o próximo, então a afirmação vale
 para todos os valores. Dá pra ver que tanto mostrando que f(n) - f(n+1), ou
 que f(n-1) - f(n), conseguimos mostrar que quando ela vale para um certo
 valor, também vale para o próximo.

 O seu exemplo é meio estranho! n = 2^n -1 não é uma equação verdadeira,
 pra começar... Acho que vc quis dizer:

 Seja T(n) = 2^n - 1. Prove que T(n) = 2T(n-1) + 1. Não é necessário
 indução para provar essa. O que vc fez está correto, mas não é indução...
 vc só substituiu a equação de T(n) e mostrou que vale.

 Por outro lado, se tivéssemos:

 Seja T(0) = 0 e T(n) = 2T(n-1) + 1, n0. Prove T(n) = 2^n -1 (n≥0). (note
 que os dois problemas são diferentes).

 Nesse caso poderíamos usar indução para demostrar... Verificamos que o
 caso inicial vale substituindo n=0. Em seguida, demostra-se (como acima) que
 se hipótese vale para n-1, então vale para n. Poderíamos, é claro, também
 ter provado a hipótese para n+1 a partir de n, também daria certo.

 2009/5/30 HugLeo hugocana...@gmail.com

 Eu posso substituir n na minha fórmula de reccorrência para provar para
 n+1, mas se eu substituir para n-1 para provar n também funciona.
 Alguém saberia explicar?

 O exemplo está abaixo:

 n = 2^n -1

 T(n) = 2T(n) + 1

 Para n
 T(n) = 2T(n-1) + 1 = 2(2^[n-1] - 1) + 1 = 2^n -1


 Para n+1

 T(n+1) = 2T(n) + 1 = 2(2^n -1) + 1 = 2^[n+1] + 1

 Qual das duas alternativas é certa ou melhor e por que funciona?



 --
 -hUgLeO-♑




 --
 Rafael




 --
 -hUgLeO-♑




-- 
Rafael

Re: [obm-l] Ajuda em probabilidade

2009-05-30 Por tôpico RitaGomes

Ai gente eu fiz uma confusão danada aqui, me desculpem
  - Original Message - 
  From: Fernando Lima Gama Junior 
  To: obm-l@mat.puc-rio.br 
  Sent: Saturday, May 30, 2009 11:13 AM
  Subject: Re: [obm-l] Ajuda em probabilidade

  Também não entendi...

  Fernando Gama

  2009/5/29 Rafael Ando rafael.a...@gmail.com

?

Rita, não entendo como vc está pensando... 

2009/5/29 RitaGomes rcggo...@terra.com.br

  Como agora ela esta na terceira posição, fazemos a permutação de 3, que 6 
e descontamos 1 condição ficando com 5 possibilidades de sair na terceira 
posição.
- Original Message - 
From: Fernando Lima Gama Junior 
To: obm-l@mat.puc-rio.br 
Sent: Friday, May 29, 2009 8:56 PM
Subject: Re: [obm-l] Ajuda em probabilidade

Qual seria a chance, então, de ela ser tirada até a terceira bola? 

Fernando Gama

Sent from Brasilia, Distrito Federal, Brazil

2009/5/29 RitaGomes rcggo...@terra.com.br

  Fernando,

  Como são 5 bolas e 1 sendo preta, fazemos permutação de 5 que é 240, 
porem a preta deve ser a última a ser retirada. Faz permutação de 4, que é 24 , 
sendo a possibilidade da bola preta sair em ordem diferente da última.
  Desconta do totoal das condições, ou seja 240 - 24 = 216 
possibilidades de ser a última a ser retirada.
  Espero não ter feito o cálculo errado, pois estou meio atorodoada 
aqui com outros estudos.

  Rita Gomes
- Original Message - 
From: Fernando Lima Gama Junior 
To: obm-l@mat.puc-rio.br 
Sent: Friday, May 29, 2009 7:18 PM
Subject: [obm-l] Ajuda em probabilidade

Uma urna tem 5 bolas, sendo 1 preta e as outra 4 brancas. As bolas 
são retiradas da urna sem reposição. Qual a chance de até a bola preta ser a 
última a ser retirada?

Fernando Gama

Esta mensagem foi verificada pelo E-mail Protegido Terra.
Atualizado em 29/05/2009

No virus found in this incoming message.
Checked by AVG - www.avg.com 
Version: 8.5.339 / Virus Database: 270.12.46/2142 - Release Date: 
05/29/09 17:53:00

Esta mensagem foi verificada pelo E-mail Protegido Terra.
Atualizado em 29/05/2009

No virus found in this incoming message.
Checked by AVG - www.avg.com 
Version: 8.5.339 / Virus Database: 270.12.46/2142 - Release Date: 
05/29/09 17:53:00

-- 
Rafael

--
  Esta mensagem foi verificada pelo E-mail Protegido Terra.
  Atualizado em 30/05/2009

--

  No virus found in this incoming message.
  Checked by AVG - www.avg.com 
  Version: 8.5.339 / Virus Database: 270.12.46/2144 - Release Date: 05/30/09 
17:53:00

[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Geometria Plana - 3 problema s clássicos

2009-05-30 Por tôpico lucianarodriggues


Em 26/05/2009 09:00, Fernando Lima Gama Junior  fgam...@gmail.com  escreveu:ComeÃ§ou...
Fernando GamaSent from Brasilia, DF, Brazil 
2009/5/26 
Em 25/05/2009 22:05, Carlos Nehab < ne...@infolink.com.br > escreveu: 
Aos aficcionados:TrÃªs problemas clÃ¡ssicos e interessantes de geometria plana:1) Dado um triÃ¢ngulo ABC, identifique o triÃ¢ngulo de perÃmetro mÃnimo 

nele inscrito (cada vÃ©rtice - P, Q e R, em um lado distinto de ABC).2) Determinar o centro de uma circunferÃªncia dada utilizando apenas compasso.3) Determinar o ponto mÃ©dio de um segmento dado, utilizando apenas 

compasso (difÃcil).Nehab=InstruÃ§Ãµes para entrar na lista, sair da lista e usar a lista emhttp://www.mat.puc-rio.br/~obmlistas/obm-l.html

== InstruÃ§Ãµes para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = 




=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=

[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Geome tria Plana - 3 problemas clássicos

2009-05-30 Por tôpico lucianarodriggues

Em 26/05/2009 10:58, Carlos Nehab  ne...@infolink.com.br  escreveu:
Oi, Luiz,Seu problema:"Duas circunferÃªncias secantesÂ se interceptam nos pontos A e B. TraÃ§ar o segmento CD, passando por A ( C em uma circunferÃªncia e D na outra), de modo que os segmentos CA=AD."PossÃvel soluÃ§Ã£o:Sendo M o ponto mÃ©dio do segmento que une os centros das circunferÃªncias, me parece que a "reta" CD Ã© simplesmente a perpendicular a AM passando por A.AbraÃ§os,Nehabluiz silva escreveu:





OlÃ¡ Carlos,
Â 
NÃ£o sou muito bom nestes tipos de problemas. PorÃ©m, com relaÃ§Ã£o ao 3o., dado um segmento qqer AB,Â  nÃ£o bastaria utilizarmos o procedimento "padrÃ£o" para traÃ§ar mediatriz, sÃ³ que, ao invÃ©s de unirmos os pontosÂ C e D, obtidos comÂ a utilizaÃ§Ã£o do compasso,Â traÃ§arÃamos a ciscunferÃªncia com centro em A ou B e tangente ao segmento ?
Â 
Um outro problema muito legal :
Â 
Duas circunferÃªncias secantesÂ se interceptam nos pontos A e B. TraÃ§ar o segmento CD, passando por A ( C em uma circunferÃªncia e D na outra), de modo que os segmentos CA=AD.
Â 
Abs
Felipe--- Em seg, 25/5/09, Carlos Nehab escreveu:
De: Carlos Nehab Assunto: [obm-l] Geometria Plana - 3 problemas clÃ¡ssicosPara: obm-l@mat.puc-rio.brData: Segunda-feira, 25 de Maio de 2009, 22:05
Aos aficcionados:TrÃªs problemas clÃ¡ssicos e interessantes de geometria plana:1) Dado um triÃ¢ngulo ABC, identifique o triÃ¢ngulo de perÃmetro mÃnimo nele inscrito (cada vÃ©rtice - P, Q e R, em um lado distinto de ABC).2) Determinar o centro de uma circunferÃªncia dada utilizando apenas compasso.3) Determinar o ponto mÃ©dio de um segmento dado, utilizando apenas compasso (difÃcil).Nehab=InstruÃ§Ãµes para entrar na lista, sair da lista e usar a lista emhttp://www.mat.puc-rio.br/~obmlistas/obm-l.html=







Veja quais sÃ£o os assuntos do momento no Yahoo! + Buscados: Top 10 - Celebridades - MÃºsica - Esportes
= InstruÃ§Ãµes para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = 
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=

Re: [obm-l] Ajuda em probabilidade

2009-05-30 Por tôpico lucianarodriggues

Em 29/05/2009 20:47, Rafael Ando  rafael.a...@gmail.com  escreveu:
Ã a mesma chance dela ser a primeira a ser retirada, ou seja, 1/5.
2009/5/29 RitaGomes rcggo...@terra.com.br


Fernando,
Â 
Como sÃ£o 5 bolas e 1 sendo preta, fazemos permutaÃ§Ã£o de 5 que Ã© 240, porem a preta deve ser a Ãºltima a ser retirada. Faz permutaÃ§Ã£o de 4, que Ã© 24 , sendo a possibilidade da bola preta sair em ordem diferente da Ãºltima.
Desconta do totoal das condiÃ§Ãµes, ou seja 240 - 24 = 216 possibilidades de ser a Ãºltima a ser retirada.
Espero nÃ£o ter feito o cÃ¡lculo errado, pois estou meio atorodoada aqui com outros estudos.
Â 
Rita Gomes



- Original Message -
From: Fernando Lima Gama Junior
To: obm-l@mat.puc-rio.br
Sent: Friday, May 29, 2009 7:18 PM
Subject: [obm-l] Ajuda em probabilidade

Uma urna tem 5 bolas, sendo 1 preta e as outra 4 brancas. As bolas sÃ£o retiradas da urna sem reposiÃ§Ã£o. Qual a chance de atÃ© a bola preta ser a Ãºltima a ser retirada?
Fernando Gama


Â 

Esta mensagem foi verificada pelo E-mail Protegido Terra.Atualizado em 29/05/2009
Â 
Â 

Â 
No virus found in this incoming message.Checked by AVG - www.avg.com Version: 8.5.339 / Virus Database: 270.12.46/2142 - Release Date: 05/29/09 17:53:00



-- Rafael
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=

[obm-l] Re: [obm-l] Indução para n+1 e (n-1, n)

2009-05-30 Por tôpico lucianarodriggues

Em 30/05/2009 11:09, Rafael Ando  rafael.a...@gmail.com  escreveu:
As duas alternativas sÃ£o iguais, nÃ£o tem uma "melhor" que a outra.Para entender porque funciona, vc entende pq a induÃ§Ã£o funciona? Se uma afirmaÃ§Ã£o vale para o valor inicial, e vc consegue provar que, quando ela vale para um certo valor, tambÃ©m vale para o prÃ³ximo, entÃ£o a afirmaÃ§Ã£o vale para todos os valores. DÃ¡ pra ver que tanto mostrando que f(n) - f(n+1), ou que f(n-1) - f(n), conseguimos mostrar que "quando ela vale para um certo valor, tambÃ©m vale para o prÃ³ximo".O seu exemplo Ã© meio estranho! n = 2^n -1 nÃ£o Ã© uma equaÃ§Ã£o verdadeira, pra comeÃ§ar... Acho que vc quis dizer:Seja T(n) = 2^n - 1. Prove que T(n) = 2T(n-1) + 1. NÃ£o Ã© necessÃ¡rio "induÃ§Ã£o" para provar essa. O que vc fez estÃ¡ correto, mas nÃ£o Ã© induÃ§Ã£o... vc sÃ³ substituiu a equaÃ§Ã£o de T(n) e mostrou que vale.Por outro lado,
  se tivÃ©ssemos:Seja T(0) = 0 e T(n) = 2T(n-1) + 1, n0. Prove T(n) = 2^n -1 (nâ¥0). (note que os dois problemas sÃ£o diferentes).Nesse caso poderÃamos usar induÃ§Ã£o para demostrar... Verificamos que o caso inicial vale substituindo n=0. Em seguida, demostra-se (como acima) que se hipÃ³tese vale para n-1, entÃ£o vale para n. PoderÃamos, Ã© claro, tambÃ©m ter provado a hipÃ³tese para n+1 a partir de n, tambÃ©m daria certo.
2009/5/30 HugLeo hugocana...@gmail.com
Eu posso substituir n na minha fÃ³rmula de reccorrÃªncia para provar para n+1, mas se eu substituir para n-1 para provar n tambÃ©m funciona.AlguÃ©m saberia explicar?O exemplo estÃ¡ abaixo:n = 2^n -1T(n) = 2T(n) + 1Para nT(n) = 2T(n-1) + 1 = 2(2^[n-1] - 1) + 1 = 2^n -1Para n+1T(n+1) = 2T(n) + 1 = 2(2^n -1) + 1 = 2^[n+1] + 1Qual das duas alternativas Ã© certa ou melhor e por que funciona?-- -hUgLeO-â

-- Rafael
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=

[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Indução para n+1 e (n-1, n)

2009-05-30 Por tôpico lucianarodriggues

Em 30/05/2009 11:58, Rafael Ando  rafael.a...@gmail.com  escreveu:
Isso, seria assim mesmo :)
2009/5/30 HugLeo hugocana...@gmail.com
Sim, eu escrevi errado, o certo Ã© como vocÃª disse: T(n) = 2^n - 1Muito obrigado pela explicaÃ§Ã£o, agora deu para entender ;-)SÃ³ mais um detalhe:VocÃª disse "..Em seguida, demostra-se (como acima) que se hipÃ³tese vale para n-1, entÃ£o vale para n..."Seria assim nÃ©?: T(n)=2(2^[n-1] - 1) + 1 
T(n)=2^n -1
2009/5/30 Rafael Ando rafael.a...@gmail.com


As duas alternativas sÃ£o iguais, nÃ£o tem uma "melhor" que a outra.Para entender porque funciona, vc entende pq a induÃ§Ã£o funciona? Se uma afirmaÃ§Ã£o vale para o valor inicial, e vc consegue provar que, quando ela vale para um certo valor, tambÃ©m vale para o prÃ³ximo, entÃ£o a afirmaÃ§Ã£o vale para todos os valores. DÃ¡ pra ver que tanto mostrando que f(n) - f(n+1), ou que f(n-1) - f(n), conseguimos mostrar que "quando ela vale para um certo valor, tambÃ©m vale para o prÃ³ximo".O seu exemplo Ã© meio estranho! n = 2^n -1 nÃ£o Ã© uma equaÃ§Ã£o verdadeira, pra comeÃ§ar... Acho que vc quis dizer:Seja T(n) = 2^n - 1. Prove que T(n) = 2T(n-1) + 1. NÃ£o Ã© necessÃ¡rio "induÃ§Ã£o" para provar essa. O que vc fez estÃ¡ correto, mas nÃ£o Ã© induÃ§Ã£o... vc sÃ³ substituiu a equaÃ§Ã£o de T(n) e mostrou que vale.P
 or outro lado, se tivÃ©ssemos:Seja T(0) = 0 e T(n) = 2T(n-1) + 1, n0. Prove T(n) = 2^n -1 (nâ¥0). (note que os dois problemas sÃ£o diferentes).Nesse caso poderÃamos usar induÃ§Ã£o para demostrar... Verificamos que o caso inicial vale substituindo n=0. Em seguida, demostra-se (como acima) que se hipÃ³tese vale para n-1, entÃ£o vale para n. PoderÃamos, Ã© claro, tambÃ©m ter provado a hipÃ³tese para n+1 a partir de n, tambÃ©m daria certo.
2009/5/30 HugLeo hugocana...@gmail.com


Eu posso substituir n na minha fÃ³rmula de reccorrÃªncia para provar para n+1, mas se eu substituir para n-1 para provar n tambÃ©m funciona.AlguÃ©m saberia explicar?O exemplo estÃ¡ abaixo:n = 2^n -1T(n) = 2T(n) + 1Para nT(n) = 2T(n-1) + 1 = 2(2^[n-1] - 1) + 1 = 2^n -1Para n+1T(n+1) = 2T(n) + 1 = 2(2^n -1) + 1 = 2^[n+1] + 1Qual das duas alternativas Ã© certa ou melhor e por que funciona?-- -hUgLeO-â



-- Rafael



-- -hUgLeO-â

-- Rafael
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=

[obm-l] Indução para n+1 e (n-1, n)

Re: [obm-l] Acai berry, Your ticket to a new life

[obm-l] Re: [obm-l] Indução para n+1 e (n-1, n)

Re: [obm-l] Ajuda em probabilidade

[obm-l] Re: [obm-l] Re: [obm-l] Indução para n+1 e (n-1, n )

[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Indução para n +1 e (n-1, n)

Re: [obm-l] Ajuda em probabilidade

[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Geometria Plana - 3 problema s clássicos

[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Geome tria Plana - 3 problemas clássicos

Re: [obm-l] Ajuda em probabilidade

[obm-l] Re: [obm-l] Indução para n+1 e (n-1, n)

[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Indução para n+1 e (n-1, n)

12 matches

Site Navigation

Mail list logo

Footer information