Robbins and Ardila meet Berstel

摘要

In 1996, Neville Robbins proved the amazing fact that the coefficient of X-n in the Fibonacci infinite productPi(n = 2) (1 - X-Fn ) = (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. I 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. (C) 2020 Elsevier B.V. All rights reserved.