Em 30/05/2009 11:09, Rafael Ando < rafael.a...@gmail.com > escreveu:
========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =========================================================================
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, n>0. 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
