𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A bijective proof of Cassini's fibonacci identity

✍ Scribed by M. Werman; D. Zeilberger

Publisher
Elsevier Science
Year
1986
Tongue
English
Weight
42 KB
Volume
58
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

can be easily proved by either induction, Binet's formula, or ([1, p. 80]) by taking determinants in In this paper we give a bijective proof, based upon the following combinatorial interpretation of the Fibonacci numbers. Proposition. Let A(n) = {(al, β€’ β€’ β€’ , at); r >I O, ai = 1 or 2, a I +''' + a~ = n}. We have IA(n)l = F,,+l. Proof. IA(0)I = 1, IA(1)I = 1 and IA(n)[ = [A(n -1)1 + IA(n -2)1, since ar = 1 or 2. [] Proof of (1). Let e = (2,..., 2); define the bijection ~r: A(n)Γ—A (n)(e, e)--~ A(n-1) Γ—A(n + 1)(e,e) as follows. Let [(al,... ,ar),(bl,. . . ,bs)]eA(n) Γ— A(n) and look for the first 1 in al, bl, a2, b2, β€’ β€’ β€’, ak, bk, .... Case I. The first 1 is an ak. Delete ak = 1 from the first vector and insert it between bk-1 and bk in the second vector.

Case II. The first 1 is a bk, (then ak = 2). Exchange ak and bk.

πŸ“œ SIMILAR VOLUMES

Hook–Schur Functions Analogues of Little
Hook–Schur Functions Analogues of Littlewood's Identities and their Bijective Proofs
✍ M. Yang; J.B. Remmel πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 233 KB

We give bijective proofs of the Hook-Schur function analogues of two well-known identities of Littlewood. In the course of our proof, we propose a new correspondence which can be considered as a generalization of the Burge correspondences used in proving the Littlewood identities.

Three Alternating Sign Matrix Identities
Three Alternating Sign Matrix Identities in Search of Bijective Proofs
✍ David M. Bressoud πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 121 KB

This paper highlights three known identities, each of which involves sums over alternating sign matrices. While proofs of all three are known, the only known derivations are as corollaries of difficult results. The simplicity and natural combinatorial interpretation of these identities, however, sug

A Bijective Proof of Lassalle's Partitio
A Bijective Proof of Lassalle's Partition Identity: Volume 89, Number 2 (2000), pages 289–290
✍ Jiang Zeng πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 29 KB

3016): on page 290, the second paragraph ``We shall prove ... in R'' should read ``We shall prove ... in R, and the restriction of f on R is not a permutation of R.''. In the third paragraph, ``[r]'' should be read as ``R'' and ``[r+s]'' as ``R \_ [n+1, ..., n+s].''