At 23:26 09/05/02 -0300, you wrote: >Oi, > Estou com problemas nos conceitos do metodo de prova da inducao >matematica, alguem poderia ajduar? Vejam os exemplos abaixo e por favor >tentem me explicar o q esta errado ... ah, os problemas foram tirados do >livro do knuth...
Que livro do Knuth? >1) Let "a" be any positive number. For all positive integers "n" we have >a^(n-1) = 1. >Proof: If n = 1, a^(n-1) = 1. And by induction, assuming that the theorem is >true for 1, 2, 3 ..., n, we have: >a^[(n+1) - 1] = a^n = a^(n-1) * a^(n-1) / a^(n-2) = 1*1/1 = 1 > >Onde esta o erro da prova de acordo com a definicao de inducao? Parece claro >q a hipotese a^(n-1) nao e valida para todo n, mas pela definicao de inducao >e necessario tambem provar para n=2? Ha tb o problema do termo a^(n-2) nao >estar definido para n=1, mas se ele estivesse definido como a^(n-2) = 1 a >prova estaria correta? O problema parece ser o seguinte: a^(n-2) não é inteiro positivo se n =1 logo o começo da indução está errado. (vc está usando uma hipótese que NAO é a hipotese de indução) >2) The following proof by induction seems correct, but for some reason the >equation for n = 6 gives >1/2 + 1/6 + 1/12 / + 1/20 + 1/30 = 5/6 on the left-hand sid, and 3/2 - 1/6 >= 4/3 on the right-hand side. Find a mistake: > >Theorem: >1/1*2 + 1/2*3 + 1/3*4 + ... + 1/(n-1)*n = 3/2 - 1/n > >Proof: We use induction on n. For n = 1, 3/2 - 1/n = 1/1*2 and, assuming >the theorem is true for n, > >1/1*2 + 1/2*3 + 1/3*4 + ... + 1/(n-1)*n + 1/n*(n+1) > >= 3/2 - 1/n + 1/n*(n+1) = 3/2 -1/n + [1/n - 1/(n+1)] = 3/2 - 1/(n+1) > >Nesse eu so vi o problema do termo (n-1) nao estar definido para todo "n" >... sera so este o problema? Sim, mas este já é um problema grave: 1/1*2 + 1/2*3 + 1/3*4 + ... + 1/(n-1)*n = 3/2 - 1/n NAO VALE para n=1. Por outro lado, na indução vc usa que vale para 1 para provar que vale para 2 para provar que vale para 3...se vc partir de uma bobagem, pode chegar em bobagem. Por exemplo. é fácil provar por indução que para todo n inteiro positivo, n+10=n, se assumirmos que vale para n=1. Afinal, n+1+10=n+1 se e só se n+10=n. Isso é diferente de começarmos a indução com um número que não seja 1. Por exemplo: "prove que se n>=4, n!>2^n" Aqui, se n=1,2 ou 3, o que queremos provar é falso, mas isso não atrapalha pq nem usaremos estes casos para completar a indução. Bruno Leite http://www.ime.usp.br/~brleite >Obrigado, >Anderson > > > > > > >========================================================================= >Instruções para entrar na lista, sair da lista e usar a lista em >http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html >O administrador desta lista é <[EMAIL PROTECTED]> >========================================================================= ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é <[EMAIL PROTECTED]> =========================================================================