Robbins and Ardila meet Berstel

DOI10.1016/J.IPL.2020.106081arXiv2007.14930MaRDI QIDQ6346114

Publication date: 29 July 2020

Abstract: In 1996, Neville Robbins proved the amazing fact that the coefficient of

X^{n}

in the Fibonacci infinite product

prod_{n geq 2} (1-X^{F_n}) = (1-X)(1-X^2)(1-X^3)(1-X^5)(1-X^8) cdots = 1-X-X^2+X^4 + cdots

is always either

- 1

,

0

, or

1

. The same result was proved later by Federico Ardila using a different method. Meanwhile, in 2001, Jean Berstel gave a simple 4-state transducer that converts an "illegal" Fibonacci representation into a "legal" one. We show how to obtain the Robbins-Ardila result from Berstel's with almost no work at all, using purely computational techniques that can be performed by existing software.

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17) Formal languages and automata (68Q45) Automata sequences (11B85) Fibonacci and Lucas numbers and polynomials and generalizations (11B39)

This page was built for publication: Robbins and Ardila meet Berstel

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6346114)