Indução Finita FIbonacci

por **Garota nerd** » Ter Mai 03, 2011 17:52

provar que:
Fn²=(Fn-1).F(n+1)+ (-1)^n+1

comecei assim:
1-1-2-3-5-8-13-21-34-55-89
para n=3.
F(3)=2.
F(2)=1
F(4)=3
2²=1.3+1->4=4,ok!
para n=k.
Fk²=F(k-1).F(k+1)+(-1)^k+1
para n=k+1.
F(k+1)²=F(k+1-1).F(k+1+1)+(-1)^k+1+1
F(k²+2k+1)=Fk.F(k+2)+(-1)^k
Oque eu faço agora?Tenho que provar a igualdade.

não usei o editor de fórmulas porque tenho que sair agora.^^
Se alguém me ajudar fico grata!

por **FilipeCaceres** » Ter Mai 03, 2011 21:02

comecei assim:
1-1-2-3-5-8-13-21-34-55-89
para n=3.
F(3)=2.
F(2)=1
F(4)=3
2²=1.3+1->4=4,ok!

Observe que tem um erro na sua solução, e provavelmente e sua função também esta errada.
Para n=3

temos,
$f(3^2)=f(3-1).f(3+1)+(-1)^{3+1}$
f(9)=f(2).f(4)+1

Temos que,
f(9)=34

Desta forma,
f(9)=f(2).f(4)+1

$34\neq 1.3+1$

Revise a função!!

Abraço.

por **LuizAquino** » Ter Mai 03, 2011 22:54

O problema na verdade está na escrita do exercício, que não foi adequada.

Temos a função F(n) que fornece o n-ésimo termo da sequência de Fibonacci.

Essa função é definida como:
$F(n) = \begin{cases}1\textrm{, se } n = 1 \textrm{ ou } n = 2 \\ F(n-1) + F(n-2)\textrm{, se } n \geq 3 \end{cases}$ , com n natural não nulo.

Vejamos alguns valores para essa função:
F(1) = 1
F(2) = 1
F(3) = F(2) + F(1) = 2
F(4) = F(3) + F(2) = 3
F(5) = F(4) + F(3) = 5
F(6) = F(5) + F(4) = 8

Agora, o que se deseja provar é: $[F(n)]^2 = F(n-1)\cdot F(n+1) + (-1)^{n+1}$ , com n > 1.

Para n=2 é trivial verificar que a relação vale.

Suponha que a relação é válida para n.

Precisamos provar que a relação vale para n + 1: $[F(n+1)]^2 =F(n)\cdot F(n+2) + (-1)^{n+2}$ .

Vamos desenvolver o lado direito da equação para obter o esquerdo.

$F(n)\cdot F(n+2) + (-1)^{n+2} = F(n)\cdot [F(n+1)+F(n)] + (-1)^{n+1}(-1)$

$= F(n)\cdot F(n+1)+ [F(n)]^2 - (-1)^{n+1}$ (nesse passo usamos a hipótese de indução)

$= F(n)\cdot F(n+1)+ F(n-1)\cdot F(n+1) + (-1)^{n+1} - (-1)^{n+1}$

$= [F(n)+ F(n-1)]\cdot F(n+1)$

$= F(n+1)\cdot F(n+1)$

= [F(n+1)]^2