[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Indução para n +1 e (n-1, n)
Isso, seria assim mesmo :) 2009/5/30 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 > > 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 >> >> 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
[obm-l] Re: [obm-l] Re: [obm-l] Indução para n+1 e (n-1, n )
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 > 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 > > 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] Indução para n+1 e (n-1, n)
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 > 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
[obm-l] Indução para n+1 e (n-1, n)
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-♑
