proof of Catalan’s Identity


For all positive integers i, let Fi denote the ith Fibonacci numberMathworldPlanetmath, with F1 = F2 = 1. We will show that for all positive integers n and r such that n>r the following holds:

Fn2-Fn+rFn-r=(-1)n-rFr2.

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

Fa+b=FaFb+1+Fa-1Fb

is true.

Proof.

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

Fa+1=FaF2+Fa-1F1Fa+1=Fa1+Fa-11

which is true by the definition of the Fibonacci numbers. Now, assume for possible values of b less than some positive integer b0 such that b0>1, the propositionPlanetmathPlanetmathPlanetmath is true. Then

FaFb0+1+Fa-1Fb0
= Fa(Fb0+Fb0-1)+Fa-1(Fb0-1+Fb0-2)
= (FaFb0+Fa-1Fb0-1)+(FaFb0-1+Fa-1Fb0-2)
= Fa+(b0-1)+F(a-1)+(b0-1) (induction hypothesis)
= Fa+b0 (definition of the Fibonacci numbers)

This concludes the proof. ∎

Lemma 0.2.

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

Ft-12+FtFt-1-Ft2=(-1)t.
Proof.

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

F12+F2F1-F22=11+11-12=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 t0 (t0>2). Then

Ft0-12+Ft0Ft0-1-Ft02
= Ft0-12+(Ft0-1+Ft0-2)Ft0-1-(Ft0-1+Ft0-2)2
= Ft0-12+Ft0-12+Ft0-2Ft0-1-Ft0-12-Ft0-22-2Ft0-1Ft0-2
= Ft0-12-2Ft0-1Ft0-2-Ft0-22
= -(Ft0-22-2Ft0-2Ft0-1-Ft0-12)
= (-1)(-1)t0-1 (by induction hypothesis)
= (-1)t0

and the proof is completePlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath. ∎

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:

Fx+a2-Fx+2aFx=(-1)xFa2.
Proof.

We follow a series of calculations

Fx+a2-Fx+2aFx
= (FxFa+1+Fx-1Fa)2-(FxF2a+1+Fx-1F2a)Fx (by lemma 1)
= Fx2Fa+12+2FxFa+1Fx-1Fa+Fx-12Fa2-
Fx(Fx(Fa+12+Fa2)+Fx-1(FaFa+1+Fa-1Fa)) (by lemma 1 again)
= FxFx-1Fa(Fa+1-Fa-1)+Fa2(Fx-12-Fx2)
= FxFx-1Fa(Fa)+Fa2(Fx-12-Fx2) (by the definition of Fibonacci numbers)
= Fa2(Fx-12+FxFx-1-Fx2)
= Fa2(-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