Re: [obm-l] Prova por indução

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Thu, Feb 23, 2006 at 11:30:45AM -0300, Wanderley Guimarães wrote:
> Demonstre  que (F_{n+1})^2 - F_n*F_{n+2} = (-1)^n. Onde F_n é o
> n-ésimo número da seqüência de Fibonacci.

Antes de mais nada, a notacao mais usual para numeros de Fibonacci
eh F(0) = 0, F(1) = F(2) = 1, F(3) = 2, F(4) = 3, ...
Infelizmente esta notacao nao eh universal: existe muita gente que
defasa a sequencia comecando com F(0) = F(1) = 1, F(2) = 2, ...
Como a propriedada que voce pede dah certo com a notacao mais usual
vou supor que esta eh a que estamos usando.

A escolha da melhor demonstracao dependo que que voce sabe sobre
a sequencia. Se voce sabe apenas que F(n+1) = F(n) + F(n-1)
entao a prova por inducao eh inevitavel. Primeiro verifique
manualmente que dah certo para n = 0 (e para ficarmos mais seguros
aproveite e verifique tambem os casos n = 1 e n = 2).
Suponha agora que a formula da certo para n e escreva
F(n+2)^2 - F(n+1)*F(n+3) = F(n+2)*(F(n)+F(n+1)) - F(n+1)*(F(n+1)+F(n+2)) =
F(n+2)*F(n) - F(n+1)^2 = -((-1)^n) = (-1)^(n+1),
completando a prova.

Se voce sabe que F(n) = (a^n - b^n)/sqrt(5),
a = (1+sqrt(5))/2, b = (1-sqrt(5))/2, entao eh so substituir e expandir.
Note que ab = -1 e a^2 + b^2 = 3.
F(n+1)^2 - F(n)*F(n+2) = 
= (1/5) ((a^(n+1) - b^(n+1))^2 - (a^n - b^n)(a^(n+2) - b^(n+2))) =
= (1/5) (a^(2n+2) - 2 (-1)^(n+1) + b^(2n+2)
  - a^(2n+2) + (-1)^n a^2 + (-1)^n b^2 - b^(2n+2)) =
= (-1)^n (1/5) ( 2 + a^2 + b^2 ) = (-1)^n.

[]s, N.


=========================================================================
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
=========================================================================