Proof of Catalan's identity
By Dean Hanafy on Tuesday, September 10, 2002 - 03:17 pm:

Fn 2 - Fn+r Fn-r = (-1)n -r.Fr 2

I tried to prove it by induction but didn't get very far, can some1 help? (Btw, Fn stands for a fibonacci number)

Thanx
Deano

By Michael Doré on Tuesday, September 10, 2002 - 11:27 pm:

Currently I can't think of anything better than crunching this with Binet's formula. This isn't as messy as it looks - we have Fn=A(ln-(-l)-n) where A=1/Ö5 so:
Fn2 - Fn-rFn+r
=
A2(ln-(-l)-n)2-A2(ln-r- l-n+r(-1)-n+r)(ln+r-l-n-r(-1)-n-r)
=
A2(-2(-1)n+l2r(-1)-n+r+l-2r(-1)-n-r)
=
(-1)n-rA2(-2(-1)r+l2r+l-2r)
=
(-1)n-rA2(lr-(-l-r)2
=
(-1)n-rFr2
but is wholly unenlightening.

By Dean Hanafy on Wednesday, September 11, 2002 - 11:21 am:

Right ok, thanks for yr help :) i'm still a bit unsure though.....after your second line of working using the above formula, i've noticed that terms have either cancelled or been collected but i don't quite see how(I'm new to number thory :) with only A-level Maths and As Further Maths knowledge (U6th)...anyways

when expanding

A2(ln-r-l-n+r(-1)-n+r)(ln+r-l-n-r(-1)-n-r)

i do obtain the l2r(-1)-n+r+l-2r(-1)-n-r terms

I also obtain l2n and l-2n(-1)-2n and i don't know where these have gone in your above working, please explain

Thanx a lot
Deano

By Arun Iyer on Thursday, September 12, 2002 - 08:16 pm:
[(ln-(-l)n)2]-[(ln-r-l-n+r(-1)-n+r] [ln+r-l-n-r(-1)-n-r]
=
[l2n-2(-1)n+l2n] -[l2n-l-2r(-1)-n-r-l2r(-1)-n+r+l2n]
=
[-2(-1)n+l-2r(-1)-n-r+l2r(-1)-n+r]
=
(-1)n-r[-2(-1)r + l-2r(-1)-2r+l2r(-1)2r]
=
(-1)n-r[-2(-1)r + l-2r+l2r]

love arun
By Dean Hanafy on Thursday, September 12, 2002 - 08:30 pm:

That's great...thanks a great deal michael and arun....i understand after the last post arun.....

Thank you both
Deano

By Michael Doré on Tuesday, September 17, 2002 - 01:47 pm:

Thank you Arun for explaining it more fully.

After a bit of fiddling I found one other approach (without using the formula) and that is to prove by induction on n that:

Fr n-1 An = Bn (*)

where An is the matrix:

Fn+r (-1)r+1 Fn
Fn (-1)r+1 Fn-r


and B is the matrix:
Fr+1 (-1)r+1
1 -Fr-1


To do this you just need to apply the identity Fa+b = Fa Fb+1 + Fa-1 Fb which is itself easily proved by induction, and you also need the fact that F-a = (-1)a+1 Fa which is obvious (F-a is of course defined by continuing the usual recurrence relation for low values).

Now take the determinant of each side of (*):

Fr 2n-2 det An = (det B)n

This becomes:

Fr 2n-2 (-1)r+1 (Fn+r Fn-r - Fn 2 ) = (-Fr+1 Fr-1 + (-1)r )n

But by a well known identity (also easily proved by induction) -Fr+1 Fr-1 + (-1)r = -Fr 2 , and on substituting and cancelling the answer comes out.