Elementary sequences, sub-Fibonacci sequences

DOI10.1016/0166-218X(93)90236-HMaRDI QIDQ686269zbMATH OpenOpenAlexFDO

Publication date 30 November 1993

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(93)90236-h

adjacent Fibonacci numbers elementary sequences finite measurement structures length of shortest elementary sequence maximum number of one-term extensions sub-Fibonacci sequences

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Special sequences and polynomials (11B83) Measurement theory in the social and behavioral sciences (91C05)

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.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Elementary sequences, sub-Fibonacci sequences

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