# proof of Catalan’s Identity

For all positive integers $i$, let $F_{i}$ denote the $i^{th}$ Fibonacci number, with $F_{1}$ = $F_{2}$ = 1. We will show that for all positive integers $n$ and $r$ such that $n>r$ the following holds:

 $F_{n}^{2}-F_{n+r}F_{n-r}=(-1)^{n-r}F_{r}^{2}.$

But in order to prove this we first need two lemmas:

###### Lemma 0.1.

For all positive integers $a$ and $b$ such that $a>1$, the identity

 $F_{a+b}=F_{a}F_{b+1}+F_{a-1}F_{b}$

is true.

###### Proof.

We will prove this by induction on $b$. When $b=1$, the identity states that

 $F_{a+1}=F_{a}F_{2}+F_{a-1}F_{1}\quad\Longleftrightarrow\quad F_{a+1}=F_{a}% \cdot 1+F_{a-1}\cdot 1$

which is true by the definition of the Fibonacci numbers. Now, assume for possible values of $b$ less than some positive integer $b_{0}$ such that $b_{0}>1$, the proposition is true. Then

 $\displaystyle F_{a}F_{b_{0}+1}+F_{a-1}F_{b_{0}}$ $\displaystyle=$ $\displaystyle F_{a}(F_{b_{0}}+F_{b_{0}-1})+F_{a-1}(F_{b_{0}-1}+F_{b_{0}-2})$ $\displaystyle=$ $\displaystyle(F_{a}F_{b_{0}}+F_{a-1}F_{b_{0}-1})+(F_{a}F_{b_{0}-1}+F_{a-1}F_{b% _{0}-2})$ $\displaystyle=$ $\displaystyle F_{a+(b_{0}-1)}+F_{(a-1)+(b_{0}-1)}$ $\displaystyle=$ $\displaystyle F_{a+b_{0}}$ (definition of the Fibonacci numbers)

This concludes the proof. ∎

###### Lemma 0.2.

For all positive integers $t$ such that $t>1$, the following holds:

 $F_{t-1}^{2}+F_{t}F_{t-1}-F_{t}^{2}=(-1)^{t}.$
###### Proof.

We will (again) proceed by induction. First, when $t=2$, we have

 $F_{1}^{2}+F_{2}F_{1}-F_{2}^{2}=1\quad\Longleftrightarrow\quad 1+1\cdot 1-1^{2}=1$

which is true. Now let us assume that the proposition is true for all positive integers which are greater than 1 and less than some positive integer $t_{0}$ $(t_{0}>2)$. Then

 $\displaystyle F_{t_{0}-1}^{2}+F_{t_{0}}F_{t_{0}-1}-F_{t_{0}}^{2}$ $\displaystyle=$ $\displaystyle F_{t_{0}-1}^{2}+(F_{t_{0}-1}+F_{t_{0}-2})F_{t_{0}-1}-(F_{t_{0}-1% }+F_{t_{0}-2})^{2}$ $\displaystyle=$ $\displaystyle F_{t_{0}-1}^{2}+F_{t_{0}-1}^{2}+F_{t_{0}-2}F_{t_{0}-1}-F_{t_{0}-% 1}^{2}-F_{t_{0}-2}^{2}-2F_{t_{0}-1}F_{t_{0}-2}$ $\displaystyle=$ $\displaystyle F_{t_{0}-1}^{2}-2F_{t_{0}-1}F_{t_{0}-2}-F_{t_{0}-2}^{2}$ $\displaystyle=$ $\displaystyle-(F_{t_{0}-2}^{2}-2F_{t_{0}-2}F_{t_{0}-1}-F_{t_{0}-1}^{2})$ $\displaystyle=$ $\displaystyle(-1)(-1)^{t_{0}-1}$ (by induction hypothesis) $\displaystyle=$ $\displaystyle(-1)^{t_{0}}$

and the proof is complete. ∎

Now to the main proposition. Let us make the substitutions $x=n-r$ and $a=r$ so that the theorem now states:

###### Theorem 0.3.

For all positive integers $x$ and $a$, the following identity holds:

 $F_{x+a}^{2}-F_{x+2a}F_{x}=(-1)^{x}F_{a}^{2}.$
###### Proof.

We follow a series of calculations

 $\displaystyle F_{x+a}^{2}-F_{x+2a}F_{x}$ $\displaystyle=$ $\displaystyle(F_{x}F_{a+1}+F_{x-1}F_{a})^{2}-(F_{x}F_{2a+1}+F_{x-1}F_{2a})F_{x}$ (by lemma 1) $\displaystyle=$ $\displaystyle F_{x}^{2}F_{a+1}^{2}+2F_{x}F_{a+1}F_{x-1}F_{a}+F_{x-1}^{2}F_{a}^% {2}-$ $\displaystyle\quad F_{x}(F_{x}(F_{a+1}^{2}+F_{a}^{2})+F_{x-1}(F_{a}F_{a+1}+F_{% a-1}F_{a}))$ (by lemma 1 again) $\displaystyle=$ $\displaystyle F_{x}F_{x-1}F_{a}(F_{a+1}-F_{a-1})+F_{a}^{2}(F_{x-1}^{2}-F_{x}^{% 2})$ $\displaystyle=$ $\displaystyle F_{x}F_{x-1}F_{a}(F_{a})+F_{a}^{2}(F_{x-1}^{2}-F_{x}^{2})$ (by the definition of Fibonacci numbers) $\displaystyle=$ $\displaystyle F_{a}^{2}(F_{x-1}^{2}+F_{x}F_{x-1}-F_{x}^{2})$ $\displaystyle=$ $\displaystyle F_{a}^{2}(-1)^{x}$ (by lemma 2)

completing our proof of the theorem. ∎

Title proof of Catalan’s Identity ProofOfCatalansIdentity 2013-03-22 14:45:01 2013-03-22 14:45:01 PrimeFan (13766) PrimeFan (13766) 20 PrimeFan (13766) Proof msc 11B39