Thread: Proof by induction

I need to proove by induction that for the Fibonacci sequence

(Fn * Fn+2) - (Fn+1)^2 = (-1)^n+1

Fn being a Fibonacci number

Is there anyone capable of doing this or know where on the internet I can find it. I have spent over 1 hrs trying to find something, without success.

Originally Posted by Natasha1

I need to proove by induction that for the fibonacci sequence

(Fn * Fn+2) - (Fn+1)^2 = (-1)^n+1

Is there anyone capable of doing this or know where on the internet I can find it. I have spent over 1 hrs trying to find something, without success.

Something is wrong because $\displaystyle n=1$
$\displaystyle F(1)F(3)-(F(2))^2=2-1=2=(-1)^1+1=0$

Originally Posted by ThePerfectHacker

Something is wrong because $\displaystyle n=1$
$\displaystyle F(1)F(3)-(F(2))^2=2-1=2=(-1)^1+1=0$

This formula shows that for even Fib numbers you get -1 and odd ones you get +1

Originally Posted by Natasha1

This formula shows that for even Fib numbers you get -1 and odd ones you get +1

But the formula is clearly wrong.
Unless you want to say, that starting with some value for $\displaystyle n$ it is correct, for example, $\displaystyle n>1$. I believe I have seen this identity somewhere and will search through my book if I can find it. Then possibly posts their proof.

What I am trying to say is:

1, 1, 2, 3, 5, 8, 13.....


if you do take f1*f3 - f2^2 you get 1
for the next in the series f2 you get f2*f4 - f3^2 you get -1

What I'm saying is that you keep having 1, -1, 1, -1 for ever.... and i need to proove that. Can't find it on the net?

(Fn * Fn+2) - (Fn+1)^2 = (-1)^n+1

Presumably should be read as $\displaystyle (F_n \cdot F_{n+2}) - (F_{n+1})^2 = (-1)^{n+1}$. I assume the convention F0 = 0, F1 = 1, so that F2 = 1: in that case the inductive hypothesis is correct for n=0.

Originally Posted by rgep

Presumably should be read as $\displaystyle (F_n \cdot F_{n+2}) - (F_{n+1})^2 = (-1)^{n+1}$. I assume the convention F0 = 0, F1 = 1, so that F2 = 1: in that case the inductive hypothesis is correct for n=0.

rgep you are spot on!

Okay,
$\displaystyle F(n)^2-F(n+1)F(n-1)$=$\displaystyle F(n)(F(n-1)+F(n-2))-F(n+1)F(n-1)$*
$\displaystyle =F(n)F(n-1)+F(n)F(n-2)-F(n+1)F(n-1)$
$\displaystyle =(F(n)-F(n+1))F(n-1)+F(n)F(n+2)$
$\displaystyle =(-1)(F(n-1)^2-F(n)F(n-2))$*
*)Used the fibonacci recrusion formula,

Thus,
$\displaystyle F(n)^2-F(n+1)F(n-1)$=$\displaystyle (-1)(F(n-1)^2-F(n)F(n-2))$
Note, the subscripts decrease by one with a negative in front.
Thus,
$\displaystyle (-1)(F(n-1)^2-F(n)F(n-2))$=$\displaystyle (-1)^2(F(n-2)^2-F(n-1)F(n-3))$
Thus,
$\displaystyle F(n)^2-F(n+1)F(n-1)$=$\displaystyle (-1)^2(F(n-2)^2-F(n-1)F(n-3))$
Countinuing this $\displaystyle n-2$ times we have,
$\displaystyle F(n)^2-F(n+1)F(n-1)$=$\displaystyle (-1)^{n-2}(F(2)^2-F(3)F(1))$=$\displaystyle (-1)^{n-2}(-1)=(-1)^{n-1}$

Q.E.D.

Originally Posted by ThePerfectHacker

Okay,
$\displaystyle F(n)^2-F(n+1)F(n-1)$=$\displaystyle F(n)(F(n-1)+F(n-2))-F(n+1)F(n-1)$*
$\displaystyle =F(n)F(n-1)+F(n)F(n-2)-F(n+1)F(n-1)$
$\displaystyle =(F(n)-F(n+1))F(n-1)+F(n)F(n+2)$
$\displaystyle =(-1)(F(n-1)^2-F(n)F(n-2))$*
*)Used the fibonacci recrusion formula,

Thus,
$\displaystyle F(n)^2-F(n+1)F(n-1)$=$\displaystyle (-1)(F(n-1)^2-F(n)F(n-2))$
Note, the subscripts decrease by one with a negative in front.
Thus,
$\displaystyle (-1)(F(n-1)^2-F(n)F(n-2))$=$\displaystyle (-1)^2(F(n-2)^2-F(n-1)F(n-3))$
Thus,
$\displaystyle F(n)^2-F(n+1)F(n-1)$=$\displaystyle (-1)^2(F(n-2)^2-F(n-1)F(n-3))$
Countinuing this $\displaystyle n-2$ times we have,
$\displaystyle F(n)^2-F(n+1)F(n-1)$=$\displaystyle (-1)^{n-2}(F(2)^2-F(3)F(1))$=$\displaystyle (-1)^{n-2}(-1)=(-1)^{n-1}$

Q.E.D.

Here's a virtual kiss x :-). By the way the recursive formula is fn = fn-1 + fn-2, for n = 2, 3, 4, ... where f0 =1, f1 = 1, no?. Which would make this invalid as f0 = 0, f1 = 1, so that f2 = 1

Originally Posted by Natasha1

Here's a virtual kiss x :-). By the way the recursive formula is fn = fn-1 + fn-2, for n = 2, 3, 4, ... where f0 =1, f1 = 1, no?. Which would make this invalid as f0 = 0, f1 = 1, so that f2 = 1

f0 is not used here,
f1=1
f2=1
f3=2
....

is this an induction proof?

Originally Posted by Natasha1

is this an induction proof?

Not really.
--
You can turn it into an induction proof.

Since there is a $\displaystyle k\geq 2$ such as,
$\displaystyle F(k)^2-F(k+1)F(k-1)=(-1)^{k-1}$
Then proof it hold for $\displaystyle k+1$. But the expression,
$\displaystyle F(k+1)^2-F(k+2)F(k)=(-1)(F(k)^2-F(k+1)F(k-1))$ as explained in my other proof. But,
$\displaystyle F(k)^2-F(k+1)(k-1)=(-1)^{k-1}$
Thus,
$\displaystyle F(k+1)^2-F(k+1)F(k)=(-1)(-1)^{k-1}=(-1)^k$
Thus, it hold true for $\displaystyle k+1$ and the proof is complete.

Originally Posted by ThePerfectHacker

Something is wrong because $\displaystyle n=1$
$\displaystyle F(1)F(3)-(F(2))^2=2-1=2=(-1)^1+1=0$

Hello,

$\displaystyle F(1)F(3)-(F(2))^2=\underbrace{2-1=2}_\csub{\mbox{That looks a little bit funny to me}}...$

and that's exactly $\displaystyle (-1)^{1+1}$ as it is given with the formula.

Greetings

EB

Originally Posted by earboth

Hello,

$\displaystyle F(1)F(3)-(F(2))^2=\underbrace{2-1=2}_\csub{\mbox{That looks a little bit funny to me}}...$

and that's exactly $\displaystyle (-1)^{1+1}$ as it is given with the formula.

Greetings

EB

I guess I never will win the Fields Medal.

That is why I never get 100 on tests.

Could someone please add the extra couple of lines for me, I'm a little stuck, Thanks!

Step 1: For n = 1, we have


$\displaystyle (F_1 \cdot F_{1+2}) - (F_{1+1})^2 = (-1)^{1+1} = 1$


Hence the equation holds for n = 1

Step 2: Assume the equation is true for n = k (inductive hypothesis), we have:

$\displaystyle (F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}$

Step 3: We then have to use our inductive hypothesis to prove that the statement is also true for n = k + 1, i.e we have to prove:

$\displaystyle (F_{k+1} \cdot F_{k+3}) - (F_{k+2})^2 = (-1)^{k+2}$

So we have:

$\displaystyle (F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}$
$\displaystyle (F_k \cdot F_{k+2}) - (F_{k+1})^2 + k+1= (-1)^{k+1} + k+1$
Could someone write what goes here please?
.
.
$\displaystyle (F_{k+1} \cdot F_{k+3}) - (F_{k+2})^2 = (-1)^{k+2}$

Hence the equation holds true for n = k + 1