Sumsets of Wythoff Sequences, Fibonacci Representation, and Beyond

2020/06/07 by Jeffrey Shallit, Shallit, Jeffrey · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Number Theory (math.NT) #cs.DM #cs.FL #math.CO #math.NT

paper · pdf · doi:10.48550/arxiv.2006.04177

arxiv created 2020/06/07 · arxiv updated 2020/06/09

Abstract

Let α= (1+√(5))/2 and define the lower and upper Wythoff sequences by a_i = \lfloor i α\rfloor, b_i = \lfloor i α² \rfloor for i ≥ 1. In a recent interesting paper, Kawsumarng et al. proved a number of results about numbers representable as sums of the form a_i + a_j, b_i + b_j, a_i + b_j, and so forth. In this paper I show how to derive all of their results, using one simple idea and existing free software called Walnut. The key idea is that for each of their sumsets, there is a relatively small automaton accepting the Fibonacci representation of the numbers represented. I also show how the automaton approach can easily prove other results.

Cited by

• Anti-recurrence sequences

Related

• Generalizing the Wythoff Array and other Fibonacci Facts to Tribonacci Numbers
• Some Fibonacci-Related Sequences
• Transduction of Automatic Sequences and Applications
• On certain Fibonacci representations
• Complexity of Linear Subsequences of Fibonacci-Automatic Sequences