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
