Robbins and Ardila meet Berstel

07/29/2020
by   Jeffrey Shallit, et al.
0

In 1996, Neville Robbins proved the amazing fact that the coefficient of X^n in the Fibonacci infinite product ∏_n ≥ 2 (1-X^F_n) = (1-X)(1-X^2)(1-X^3)(1-X^5)(1-X^8) ⋯ = 1-X-X^2+X^4 + ⋯ 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset