Proof by induction

**Natasha1** · May 26th 2006, 08:44 AM

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.

**ThePerfectHacker** · May 26th 2006, 08:47 AM

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 $n=1$
$F(1)F(3)-(F(2))^2=2-1=2=(-1)^1+1=0$

**Natasha1** · May 26th 2006, 09:01 AM

Originally Posted by ThePerfectHacker

Something is wrong because $n=1$
$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

**ThePerfectHacker** · May 26th 2006, 09:05 AM

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 $n$ it is correct, for example, $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.

**Natasha1** · May 26th 2006, 09:35 AM

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?

**rgep** · May 26th 2006, 09:35 AM

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

Presumably should be read as $(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.

**Natasha1** · May 26th 2006, 09:36 AM

Originally Posted by rgep

Presumably should be read as $(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!

**ThePerfectHacker** · May 26th 2006, 10:12 AM

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

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

Q.E.D.

**Natasha1** · May 26th 2006, 10:21 AM

Originally Posted by ThePerfectHacker

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

Thus,
$F(n)^2-F(n+1)F(n-1)$ = $(-1)(F(n-1)^2-F(n)F(n-2))$
Note, the subscripts decrease by one with a negative in front.
Thus,
$(-1)(F(n-1)^2-F(n)F(n-2))$ = $(-1)^2(F(n-2)^2-F(n-1)F(n-3))$
Thus,
$F(n)^2-F(n+1)F(n-1)$ = $(-1)^2(F(n-2)^2-F(n-1)F(n-3))$
Countinuing this $n-2$ times we have,
$F(n)^2-F(n+1)F(n-1)$ = $(-1)^{n-2}(F(2)^2-F(3)F(1))$ = $(-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

**ThePerfectHacker** · May 26th 2006, 10:23 AM

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

**Natasha1** · May 26th 2006, 10:24 AM

is this an induction proof?

**ThePerfectHacker** · May 26th 2006, 10:30 AM

Originally Posted by Natasha1

is this an induction proof?

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

Since there is a $k\geq 2$ such as,
$F(k)^2-F(k+1)F(k-1)=(-1)^{k-1}$
Then proof it hold for $k+1$ . But the expression,
$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,
$F(k)^2-F(k+1)(k-1)=(-1)^{k-1}$
Thus,
$F(k+1)^2-F(k+1)F(k)=(-1)(-1)^{k-1}=(-1)^k$
Thus, it hold true for $k+1$ and the proof is complete.

**earboth** · May 26th 2006, 10:39 AM

Originally Posted by ThePerfectHacker

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

Hello,

$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 $(-1)^{1+1}$ as it is given with the formula.

Greetings

EB

**ThePerfectHacker** · May 26th 2006, 10:41 AM

Originally Posted by earboth

Hello,

$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 $(-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.

**Natasha1** · May 28th 2006, 01:28 AM

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

Step 1: For n = 1, we have

$(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:

$(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:

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

So we have:

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

Hence the equation holds true for n = k + 1

Thread: Proof by induction

LinkBack

Thread Tools

Display

Proof by induction

Similar Math Help Forum Discussions

Proof by Induction

Proof by Induction

Mathemtical Induction Proof (Stuck on induction)

Proof by Induction??

Proof with algebra, and proof by induction (problems)

Search Tags