# Proof of d'Ocagne's identity

It's known that Fibonacci numbers satisfy the following relation:

$$F_mF_{n+1}-F_{m+1}F_n=(-1)^nF_{m-n}$$

Which is called d'Ocagne's identity.

This identity with the following identities are well-known:

$$F_{n-1}F_{n+1}-F_{n}^2=(-1)^n\tag{Cassini's identity}$$ $$F_{n}^2-F_{n-r}F_{n+r}=(-1)^{n-r}F_r^2\tag{Catalan's identity }$$ $$F_{n+i}F_{n+j}-F_{n}F_{n+i+j}=(-1)^{n}F_iF_j\tag{Vajda's identity }$$ $$F_{k−1}F_n + F_kF_{n+1} = F_{n+k} \tag{Honsberger identity}$$

Cassini's identity is a special case of Catalan's identity and can be derived with $$r=1$$.

The usual way for proving these identities is using $$2×2$$ matrix , another way would be induction,I know how to prove Catalan's identity using induction but still I have not seen any proof of d'Ocagne's identity,I'm asking if someone know a proof of that (induction preferred)?

Also is their any combinatorial poof for d'Ocagne's identity? if yes, so it would be really nice to see the proof.

My try:

• Define: $$a:=\frac{1+\sqrt{5}}{2}\;\;\;\;\;\;\text{and}\;\;\;\;\;\;\; b:=\frac{1-\sqrt{5}}{2}$$ Then using this follows: $$F_mF_{n+1}-F_{m+1}F_n$$ $$=\left(\frac{a^{m}-b^{m}}{\sqrt{5}}\right)\left(\frac{a^{\left(n+1\right)}-b^{\left(n+1\right)}}{\sqrt{5}}\right)-\left(\frac{a^{\left(m+1\right)}-b^{\left(m+1\right)}}{\sqrt{5}}\right)\left(\frac{a^{n}-b^{n}}{\sqrt{5}}\right)$$

$$=\frac{\color{red}{a^{\left(m+n+1\right)}}-a^{m}b^{\left(n+1\right)}-a^{\left(n+1\right)}b^{m}+\color{blue}{b^{\left(m+n+1\right)}}}{5}-\frac{\color{red}{a^{\left(m+n+1\right)}}-a^{\left(m+1\right)}b^{n}-a^{n}b^{\left(m+1\right)}+\color{blue}{b^{\left(m+n+1\right)}}}{5}$$ $$=\frac{-a^{m}b^{\left(n+1\right)}-a^{\left(n+1\right)}b^{m}+a^{\left(m+1\right)}b^{n}+a^{n}b^{\left(m+1\right)}}{5}$$$$=\frac{a^{m}b^{n}\left(a-b\right)+a^{n}b^{m}\left(b-a\right)}{5}=\frac{\left(a-b\right)\left(a^{m}b^{n}-a^{n}b^{m}\right)}{5}$$$$=\left(a-b\right)\frac{\left(a^{\left(m-n\right)}-b^{\left(m-n\right)}\right)}{\sqrt{5}}\frac{a^{n}b^{n}}{\sqrt{5}}$$$$=\left(a-b\right)\frac{a^{n}b^{n}}{\sqrt{5}}F_{m-n}$$$$=\bbox[5px,border:2px solid #00A000]{\left(-1\right)^{n}F_{m-n}}$$

Which is the claim.

• Another way for proving this identity would be setting $$i \mapsto m-n$$ and $$j \mapsto 1$$ in Vajda's identity.
• In turn, Catalan's identity is a special case of Vajda's identity with $i=-j$. – Théophile Feb 26 at 19:21

See the paper Fibonacci Numbers and Identities by Lang and Lang. The authors discuss an elegant framework, involving what they call $$\mathcal F$$-functions, that unifies proofs for many identities for Fibonacci and Lucas numbers, including d'Ocagne.

Call the left-hand side $$u_{m,\,n}$$ so\begin{align}u_{m+1,\,n+1}+u_{m,\,n}&=F_{m+1}F_{n+2}-F_{m+2}F_{n+1}+F_mF_{n+1}-F_{m+1}F_n\\&=F_{m+1}F_{n+2}-F_{m+1}F_{n+1}-F_{m+1}F_n=0,\end{align}so some sequence $$a_k$$ satisfies $$u_{m,\,n}=(-1)^na_{m-n}$$. To verify $$a_k=F_k$$, we only need to check the case $$n=0$$, i.e. $$u_{m,\,0}=F_m$$, but that's trivial.

d'Ocagne identity comes straightly from the matrix form \eqalign{ & \left( {\matrix{ {F_{\,k + 2} } \cr {F_{\,k + 1} } \cr } } \right) = \left( {\matrix{ 1 & 1 \cr 1 & 0 \cr } } \right)\left( {\matrix{ {F_{\,k + 1} } \cr {F_{\,k} } \cr } } \right)\quad \Rightarrow \cr & \Rightarrow \quad \left( {\matrix{ {F_{\,m + 1} } & {F_{\,n + 1} } \cr {F_{\,m} } & {F_{\,n} } \cr } } \right) = \left( {\matrix{ 1 & 1 \cr 1 & 0 \cr } } \right)\left( {\matrix{ {F_{\,m} } & {F_{\,n} } \cr {F_{\,m - 1} } & {F_{\,n - 1} } \cr } } \right) = \cr & = \left( {\matrix{ 1 & 1 \cr 1 & 0 \cr } } \right)^{\,n} \left( {\matrix{ {F_{\,m - n + 1} } & {F_{\,1} } \cr {F_{\,m - n} } & {F_{\,0} } \cr } } \right) = \left( {\matrix{ 1 & 1 \cr 1 & 0 \cr } } \right)^{\,n} \left( {\matrix{ {F_{\,m - n + 1} } & 1 \cr {F_{\,m - n} } & 0 \cr } } \right) \cr} and taking the determinant

Define:

$$a:=\frac{1+\sqrt{5}}{2}\;\;\;\;\;\;\text{and}\;\;\;\;\;\;\; b:=\frac{1-\sqrt{5}}{2}$$ Then using this follows:

$$F_{n+i}F_{n+j}-F_{n}F_{n+i+j}$$ $$=\left(\frac{a^{\left(n+i\right)}-b^{\left(n+i\right)}}{\sqrt{5}}\right)\left(\frac{a^{\left(n+j\right)}-b^{\left(n+j\right)}}{\sqrt{5}}\right)-\left(\frac{a^{\left(n\right)}-b^{\left(n\right)}}{\sqrt{5}}\right)\left(\frac{a^{\left(n+i+j\right)}-b^{\left(n+i+j\right)}}{\sqrt{5}}\right)$$$$=\frac{\color{red}{a^{\left(2n+i+j\right)}}-a^{\left(n+i\right)}b^{\left(n+j\right)}-a^{\left(n+j\right)}b^{\left(n+i\right)}+\color{blue}{b^{\left(2n+i+j\right)}}}{5}-\frac{\color{red}{a^{\left(2n+i+j\right)}}-a^{\left(n\right)}b^{\left(n+i+j\right)}-a^{\left(n+i+j\right)}b^{\left(n\right)}+\color{blue}{b^{\left(2n+i+j\right)}}}{5}$$$$=\frac{-a^{\left(n+i\right)}b^{\left(n+j\right)}-a^{\left(n+j\right)}b^{\left(n+i\right)}+a^{\left(n\right)}b^{\left(n+i+j\right)}+a^{\left(n+i+j\right)}b^{\left(n\right)}}{5}$$$$=\frac{a^{n}b^{\left(n+j\right)}\left(b^{i}-a^{i}\right)+b^{n}a^{\left(n+j\right)}\left(a^{i}-b^{i}\right)}{5}$$$$=\frac{\left(a^{i}-b^{i}\right)}{\sqrt{5}}\frac{\left(b^{n}a^{\left(n+j\right)}-a^{n}b^{\left(n+j\right)}\right)}{\sqrt{5}}$$$$=\frac{\left(a^{i}-b^{i}\right)}{\sqrt{5}}\left(a^{n}b^{n}\frac{a^{j}-b^{j}}{\sqrt{5}}\right)$$$$=\bbox[5px,border:2px solid #00A000]{\left(-1\right)^{n}F_{i}F_{j}}$$

Now I will show that how the other identities can be derived using Vajda's identity :

Set $$i \mapsto n-1$$, $$j \mapsto k$$ and fix $$n=-1$$ in Vajda's identity to get:

$$F_nF_{k+1} -F_1F_{n+k}=(-1)^{1}F_{n-1}F_{k}$$ $$F_nF_{k+1}-(-1)^{1}F_{n-1}F_{k}=F_1F_{n+k}$$ $$F_n\color{red}{F_{k+1}}+F_{n-1}F_{k}=F_1F_{n+k}$$ $$F_n(\color{red}{F_{k}+F_{k-1}})+F_{n-1}F_{k}=F_{n+k}$$ $$F_{k-1}F_n+F_k(F_n+F_{n-1})=F_{n+k}$$ $$\bbox[5px,border:2px solid #00A000]{F_{k-1}F_n+F_kF_{n+1}=F_{n+k}}$$

Which is Honsberger identity.

Set $$i \mapsto m-n$$ and fix $$j = 1$$ in Vajda's identity to get:

$$F_mF{n+1}-F_nF_{m+1}=(-1)^{n}F_{m-n}F_1$$ $$\bbox[5px,border:2px solid #00A000]{F_mF_{n+1}-F_{m+1}F_n=(-1)^{n}F_{m-n}}$$

Which is d'Ocagne's identity.

Set $$i,j \mapsto r$$ and $$n \mapsto n-r$$ in Vajda's identity to get:

$$F_nF_n-F_{n-r}F_{n+r}=(-1)^{n-r}F_rF_r$$ $$\bbox[5px,border:2px solid #00A000]{F_n^2-F_{n-r}F_{n+r}=(-1)^{n-r}F_r^2}$$

Which is Catalan's identity.

Set $$i,j \mapsto r$$ , $$n \mapsto n-r$$ and fix $$r = 1$$ in Vajda's identity to get:

$$F_nF_n-F_{n-1}F_{n+1}=(-1)^{n-1}F_1F_1$$ $$F_n^2-F_{n-1}F_{n+1}=(-1)^{n-1}F_1^2$$ $$\bbox[5px,border:2px solid #00A000]{F_{n-1}F_{n+1}-F_n^2=(-1)^{n}}$$

Which is Cassini's identity.