# Fibonacci sequence identity

• Dec 3rd 2011, 12:24 AM
Mathsdog
Fibonacci sequence identity
Hi, we've been trying to prove this identity and can't quite see how its done. Any insights would be greatly appreciated. . .

$\displaystyle \text{where } \newline F_1 = 1 \newline F_2 = 1, \newline F_n = F_{n-1} + F_{n-2} \text{ for } n \geq 3 \newline \newline L_1 = 1 \newline L_n = F_{n+1} + F_{n-1} \text{ for } n \geq 2$

show that

$\displaystyle F_{2n} = F_n L_n$

Thanks, MD
• Dec 3rd 2011, 12:35 PM
Opalg
Re: Fibonacci sequence identity
Quote:

Originally Posted by Mathsdog
Hi, we've been trying to prove this identity and can't quite see how its done. Any insights would be greatly appreciated. . .

$\displaystyle \text{where } \newline F_1 = 1 \newline F_2 = 1, \newline F_n = F_{n-1} + F_{n-2} \text{ for } n \geq 3 \newline \newline L_1 = 1 \newline L_n = F_{n+1} + F_{n-1} \text{ for } n \geq 2$

show that

$\displaystyle F_{2n} = F_n L_n$

Thanks, MD

The slick way to do this is as follows. Define a 2x2 matrix A by $\displaystyle A = \begin{bmatrix}1&1\\1&0 \end{bmatrix}.$ Prove by induction that $\displaystyle A^n = \begin{bmatrix}F_{n+1}&F_n\\F_n&F_{n-1} \end{bmatrix}.$ Then look at the off-diagonal elements of the matrices $\displaystyle A^n\times A^n$ and $\displaystyle A^{2n}$ (which are equal, of course).