Re: [obm-l] Inducao

["Bruno F. C. Leite" <bruleite@xxxxxxxxxxxx>]

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 é <nicolau@mat.puc-rio.br>
>=========================================================================

=========================================================================
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 é <nicolau@mat.puc-rio.br>
=========================================================================