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, 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
>>
>
>
>
> --
> -hUgLeO-♑
>



-- 
Rafael

Responder a