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)}$	(induction hypothesis)
$\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
Canonical name	ProofOfCatalansIdentity
Date of creation	2013-03-22 14:45:01
Last modified on	2013-03-22 14:45:01
Owner	PrimeFan (13766)
Last modified by	PrimeFan (13766)
Numerical id	20
Author	PrimeFan (13766)
Entry type	Proof
Classification	msc 11B39