proof of Catalan’s Identity
For all positive integers , let denote the Fibonacci number, with = = 1. We will show that for all positive integers and such that the following holds:
But in order to prove this we first need two lemmas:
Lemma 0.1.
For all positive integers and such that , the identity
is true.
Proof.
We will prove this by induction on . When , the identity states that
which is true by the definition of the Fibonacci numbers. Now, assume for possible values of less than some positive integer such that , the proposition is true. Then
(induction hypothesis) | ||||
(definition of the Fibonacci numbers) |
This concludes the proof. ∎
Lemma 0.2.
For all positive integers such that , the following holds:
Proof.
We will (again) proceed by induction. First, when , we have
which is true. Now let us assume that the proposition is true forall positive integers which are greater than 1 and less than somepositive integer . Then
(by induction hypothesis) | ||||
and the proof is complete.∎
Now to the main proposition. Let us make the substitutions and so that the theorem now states:
Theorem 0.3.
For all positive integers and , the following identity holds:
Proof.
We follow a series of calculations
(by lemma 1) | ||||
(by lemma 1 again) | ||||
(by the definition of Fibonacci numbers) | ||||
(by lemma 2) |
completing our proof of the theorem.∎