Proof of Catalan's identity

By Dean Hanafy on Tuesday, September 10, 2002 - 03:17 pm:

F_n ² - F_n+r F_n-r = (-1)ⁿ -r.F_r ²

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 $F_{n} = A (λ^{n} - (- λ)^{- n})$ where $A = 1 / \sqrt{5}$ so:

$\begin{matrix} F_{n}^{2} - F_{n - r} F_{n + r} & = & A^{2} (λ^{n} - (- λ)^{- n})^{2} - A^{2} (λ^{n - r} - λ^{- n + r} (- 1)^{- n + r}) (λ^{n + r} - λ^{- n - r} (- 1)^{- n - r}) \\ = & A^{2} (- 2 (- 1)^{n} + λ^{2 r} (- 1)^{- n + r} + λ^{- 2 r} (- 1)^{- n - r}) \\ = & (- 1)^{n - r} A^{2} (- 2 (- 1)^{r} + λ^{2 r} + λ^{- 2 r}) \\ = & (- 1)^{n - r} A^{2} (λ^{r} - (- λ^{- r})^{2} \\ = & (- 1)^{n - r} F_{r}^{2} \end{matrix}$

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

A^{2} (λ^{n - r} - λ^{- n + r} (- 1)^{- n + r}) (λ^{n + r} - λ^{- n - r} (- 1)^{- n - r})

i do obtain the $λ^{2 r} (- 1)^{- n + r} + λ^{- 2 r} (- 1)^{- n - r}$ terms

I also obtain $λ^{2 n}$ and $λ^{- 2 n} (- 1)^{- 2 n}$ 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:

\begin{matrix} [(λ^{n} - (- λ)^{n})^{2}] - [(λ^{n - r} - λ^{- n + r} (- 1)^{- n + r}] [λ^{n + r} - λ^{- n - r} (- 1)^{- n - r}] & = & [λ^{2 n} - 2 (- 1)^{n} + λ^{2 n}] - [λ^{2 n} - λ^{- 2 r} (- 1)^{- n - r} - λ^{2 r} (- 1)^{- n + r} + λ^{2 n}] \\ = & [- 2 (- 1)^{n} + λ^{- 2 r} (- 1)^{- n - r} + λ^{2 r} (- 1)^{- n + r}] \\ = & (- 1)^{n - r} [- 2 (- 1)^{r} + λ^{- 2 r} (- 1)^{- 2 r} + λ^{2 r} (- 1)^{2 r}] \\ = & (- 1)^{n - r} [- 2 (- 1)^{r} + λ^{- 2 r} + λ^{2 r}] \end{matrix}

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:

F_r ^n-1 A_n = Bⁿ (*)

where A_n is the matrix:

F_n+r	(-1)^r+1 F_n
F_n	(-1)^r+1 F_n-r

and B is the matrix:

F_r+1	(-1)^r+1
1	-F_r-1

To do this you just need to apply the identity F_a+b = F_a F_b+1 + F_a-1 F_b which is itself easily proved by induction, and you also need the fact that F_-a = (-1)^a+1 F_a 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 (*):

F_r ^2n-2 det A_n = (det B)ⁿ

This becomes:

F_r ^2n-2 (-1)^r+1 (F_n+r F_n-r - F_n ² ) = (-F_r+1 F_r-1 + (-1)^r )ⁿ

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