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 <[email protected]> > 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 <[email protected]> > > 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-♑
