Journal of Integer Sequences, Vol. 16 (2013), Article 13.4.5

Compositions and Fibonacci Identities


Ira M. Gessel and Ji Li
Department of Mathematics
Brandeis University
Waltham, MA 02453
USA

Abstract:

We study formulas for Fibonacci numbers as sums over compositions. The Fibonacci number Fn+1 is the number of compositions of n with parts 1 and 2. Compositions with parts 1 and 2 form a free monoid under concatenation, and our formulas arise from free submonoids of this free monoid.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000045 A000129 A000930 A001519 A001906 A003269 A003520 A003946 A005320 A005708 A005709 A005710 A005711 A014445 A015448 A017898 A017900 A017901 A017902 A017903 A017904 A017905 A017906 A017907 A017908 A017909 A033887 A048739 A052542 A052921 A077849 A104934 A122367 A163271.)

Received March 8 2013; revised version received March 16 2013. Published in Journal of Integer Sequences, March 16 2013.

Return to Journal of Integer Sequences home page