## You are here

Homeproof of Catalan's Identity

## Primary tabs

# 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}.$ |

###### 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. ∎

## Mathematics Subject Classification

11B39*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

new question: Prove a formula is part of the Gentzen System by LadyAnne

Mar 30

new question: A problem about Euler's totient function by mbhatia

new problem: Problem: Show that phi(a^n-1), (where phi is the Euler totient function), is divisible by n for any natural number n and any natural number a >1. by mbhatia

new problem: MSC browser just displays "No articles found. Up to ." by jaimeglz

Mar 26

new correction: Misspelled name by DavidSteinsaltz

Mar 21

new correction: underline-typo by Filipe

Mar 19

new correction: cocycle pro cocyle by pahio

Mar 7

new image: plot W(t) = P(waiting time <= t) (2nd attempt) by robert_dodier

new image: expected waiting time by robert_dodier

new image: plot W(t) = P(waiting time <= t) by robert_dodier