# 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\mathrm{>}\mathrm{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}\mathit{\hspace{1em}}\u27fa\mathit{\hspace{1em}}{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

${F}_{a}{F}_{{b}_{0}+1}+{F}_{a-1}{F}_{{b}_{0}}$ | ||||

$=$ | ${F}_{a}({F}_{{b}_{0}}+{F}_{{b}_{0}-1})+{F}_{a-1}({F}_{{b}_{0}-1}+{F}_{{b}_{0}-2})$ | |||

$=$ | $({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})$ | |||

$=$ | ${F}_{a+({b}_{0}-1)}+{F}_{(a-1)+({b}_{0}-1)}$ | (induction hypothesis) | ||

$=$ | ${F}_{a+{b}_{0}}$ | (definition of the Fibonacci numbers) |

This concludes the proof. ∎

###### Lemma 0.2.

For all positive integers $t$ such that $t\mathrm{>}\mathrm{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\mathit{\hspace{1em}}\u27fa\mathit{\hspace{1em}}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

${F}_{{t}_{0}-1}^{2}+{F}_{{t}_{0}}{F}_{{t}_{0}-1}-{F}_{{t}_{0}}^{2}$ | ||||

$=$ | ${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}$ | |||

$=$ | ${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}-2{F}_{{t}_{0}-1}{F}_{{t}_{0}-2}$ | |||

$=$ | ${F}_{{t}_{0}-1}^{2}-2{F}_{{t}_{0}-1}{F}_{{t}_{0}-2}-{F}_{{t}_{0}-2}^{2}$ | |||

$=$ | $-({F}_{{t}_{0}-2}^{2}-2{F}_{{t}_{0}-2}{F}_{{t}_{0}-1}-{F}_{{t}_{0}-1}^{2})$ | |||

$=$ | $(-1){(-1)}^{{t}_{0}-1}$ | (by induction hypothesis) | ||

$=$ | ${(-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

${F}_{x+a}^{2}-{F}_{x+2a}{F}_{x}$ | ||||

$=$ | ${({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) | ||

$=$ | ${F}_{x}^{2}{F}_{a+1}^{2}+2{F}_{x}{F}_{a+1}{F}_{x-1}{F}_{a}+{F}_{x-1}^{2}{F}_{a}^{2}-$ | |||

$\mathrm{\hspace{1em}}{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) | |||

$=$ | ${F}_{x}{F}_{x-1}{F}_{a}({F}_{a+1}-{F}_{a-1})+{F}_{a}^{2}({F}_{x-1}^{2}-{F}_{x}^{2})$ | |||

$=$ | ${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) | ||

$=$ | ${F}_{a}^{2}({F}_{x-1}^{2}+{F}_{x}{F}_{x-1}-{F}_{x}^{2})$ | |||

$=$ | ${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 |