6
$\begingroup$

Consider the problem of tiling a board of length $n$ with squares of size $1×1$ and dominoes of size $1×2$, Let's denote $f_n$ to be the number of ways to tile this so-called ($n$)-board.Then $f_n=F_{n+1}$, where $F_n$ is the nth Fibonacci number.

Now the question is as follows:

Is there any combinatorial way to prove Catalan's identity which states: $$F_{n}^2-F_{n-r}F_{n+r}=(-1)^{n-r}F_r^2$$


It's easy to prove this identity using induction or using a more generalized form of that which is indeed Vajda's identity.

Cassini's identity (a special case of Catalan's identity ) has been proved using combinatorial interpretation in a few books, but I've never seen any combinatorial proof of this one.

$\endgroup$
1
  • $\begingroup$ "Vajda's identity" is really Tagiuri's identity: A. Tagiuri, Di alcune successioni ricorrenti a termini interi e positivi, Periodico di Matematica 16 (1900–1901), 1–12. See also math.stackexchange.com/questions/1356391/…. $\endgroup$
    – Ira Gessel
    Feb 29, 2020 at 16:57

5 Answers 5

6
$\begingroup$

I always believed that this puzzle combined with Pick's theorem is the most visually appealing proof of the identity. You can also think of it as a bijective proof, if you allow "geometric bijections", cf. this answer.

$\endgroup$
5
$\begingroup$

The method used to prove Example 2.7 here (which also appears in the book by Benjamin and Quinn) easily extends to give a combinatorial proof of Catalan's identity.

$\endgroup$
1
  • $\begingroup$ Yes, I remember being fond of this method, since the time I saw it. But I also think, much before I read the method from the book, I saw a method closely related to it (if not exactly identical to the method described in the book) to prove some similar types of identities in a paper published by Fibonacci quarterly, but I never found it again (or may have overlooked it). $\endgroup$ Mar 15, 2020 at 14:29
2
$\begingroup$

This would not be a combinatorial proof but you may take it as an alternative method. I'm referring to the method of condensation for determinants as illustrated in this joint paper. See pages 10-11.

$\endgroup$
2
$\begingroup$

You may simply interpret both $F_n^2$ and $F_{n-r}F_{n+r}$ as the numbers of domino tylings of $2\times (2n-2)$ rectangle with additional restrictions --- vertical cuts on place $n$ (restriction 1) or $n-r$ (restriction 2), and subtract: "tylings with restriction 1" minus "tylings with restriction 2"="tylings with restriction 1 but not 2" minus "tylings with restrictions 2 but not 1". The illustration:

picture

$\endgroup$
1
$\begingroup$

I don’t have my copy in front of me, but I am almost positive that a combinatorial proof of this identity appears in the first chapter of Proofs that Really Count: The Art of Combinatorial Proof.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.