Elementary sequences, sub-Fibonacci sequences
type: Item
instance of: scholarly article
title: Elementary sequences, sub-Fibonacci sequences
zbMATH Open document ID: 0789.11015
DOI: 10.1016/0166-218X(93)90236-H
author: Fred Roberts
author: Peter Fishburn
published in: Discrete Applied Mathematics
publication date: 1993-11-30T00:00:00Z
review text: A nondecreasing integer sequence \(x_ 1,x_ 2,\dots,x_ k\) with \(x_ 1=x_ 2=1\) and \(n \geq 2\) is said to be elementary if for all \(k \leq n\) \((x_ k>1 \Rightarrow x_ k=x_ i+x_ j\) for some \(i \neq j)\) and sub- Fibonacci if for all \(k \in \{3,\dots,n\}\) \((x_ k \leq x_{k-1}+x_{k- 2})\). These notions were motivated by questions of uniqueness of solutions for finite measurement structures [cf. the authors, IMA Vol. Appl. 17, 103-137 (1989; Zbl 0702.92024)]. The authors touch upon three complexes of questions (supported by rich computational underlying material) related to these sequences, however not answering most of them completely, thereby leaving a number of problems open. For instance, if \(E_ n\) is the set of all \(n\)-term elementary sequences and \(F_ n\) the set of all \(n\)-term sub-Fibonacci sequences then \(| E_ n |/ | F_ n | \to 0\) with \(| F_ n | = \alpha^{n^ 2(1+ o(1))/2}\), \(\alpha=(1+\sqrt 5)/2\). The second complex of results focuses on investigation of the length \(e(m)\) of a shortest elementary sequence whose last term is \(m\). This is a nondecreasing quantity. The previously proved lower bound \(k+1\) for \(e(m)\) with \(m\) between two adjacent Fibonacci numbers \(f_ k\) and \(f_{k+1}\) is improved to \(k+2\) for \(m \in(2f_{k-1}+f_{k-3}, f_{k+1})\). Finally, lower bounds for the maximum number of one-term extensions into \(E_{n+1}\) for an elementary sequence in \(E_ n\) is proved.
reviewed by: Štefan Porubský
Mathematics Subject Classification ID: 11B83
Mathematics Subject Classification ID: 91C05
Mathematics Subject Classification ID: 05A15
zbMATH DE Number: 428117
zbMATH Keywords: length of shortest elementary sequence
zbMATH Keywords: finite measurement structures
zbMATH Keywords: elementary sequences
zbMATH Keywords: sub-Fibonacci sequences
zbMATH Keywords: adjacent Fibonacci numbers
zbMATH Keywords: maximum number of one-term extensions
MaRDI profile type: Publication
cites work: Unique Finite Difference Measurement
cites work: Q3834778
cites work: Q4732510
cites work: Unique finite conjoint measurement
cites work: Q3481545
cites work: Axioms for unique subjective probability on finite sets
cites work: Van Lier sequences
cites work: Q5595249
cites work: Q4774085
cites work: A simple sufficient condition for the unique representability of a finite qualitative probability by a probability measure
full work available at URL: 0166-218x(93)90236-h
OpenAlex ID: W2046248711
Recommended article: Conway's Subprime Fibonacci Sequences
Recommended article: Q4732510
Recommended article: Q3360945
Recommended article: Q3717113
Recommended article: A Small Fib
Recommended article: Q3429176
Recommended article: Q5666625
Recommended article: Q4556750
Recommended article: On minimal words with given subword complexity
Recommended article: Q4825993
description: scientific article; zbMATH DE number 428117