Interesting Esoterica

Some Doubly Exponential Sequences

Article by A. V. Aho and N. J. A. Sloane
  • Published in 1970
  • Added on
In the collections
Let \(x_0, x_1, x_2, \cdots\) be a sequence of natural numbers satisfying a nonlinear recurrence of the form \(x_{n+1} = x_n^2 + g_n\), where \(|g_n| \lt \frac{1}{4}x_n\) for \(n \geq n_0\). Numerous example of such sequences are given, arising from Boolean functions, graph theory, language theory, automata theory, and number theory. By an elementary method it is shown that the solution is \(x_n =\) nearest integer to \(k^{2^n}\), for \(n \geq n_0\), where \(k\) is a constant. That is, these are doubly exponential sequences. In some cases \(k\) is a "known" constant (such as \(\frac{1}{2}(1+\sqrt{5})\), but in general the formula for \(k\) involves \(x_0,x_1,x_2,\cdots\)!

Links

Other information

journal
Fibonacci Quarterly

BibTeX entry

@article{SomeDoublyExponentialSequences,
	title = {Some Doubly Exponential Sequences},
	author = {A. V. Aho and N. J. A. Sloane},
	url = {http://neilsloane.com/doc/doubly.html},
	urldate = {2020-07-13},
	year = 1970,
	abstract = {Let \(x{\_}0, x{\_}1, x{\_}2, \cdots\) be a sequence of natural numbers satisfying a nonlinear recurrence of the form \(x{\_}{\{}n+1{\}} = x{\_}n^2 + g{\_}n\), where \(|g{\_}n| \lt \frac{\{}1{\}}{\{}4{\}}x{\_}n\) for \(n \geq n{\_}0\). Numerous example of such sequences are given, arising from Boolean functions, graph theory, language theory, automata theory, and number theory. By an elementary method it is shown that the solution is \(x{\_}n =\) nearest integer to \(k^{\{}2^n{\}}\), for \(n \geq n{\_}0\), where \(k\) is a constant. That is, these are doubly exponential sequences. In some cases \(k\) is a "known" constant (such as \(\frac{\{}1{\}}{\{}2{\}}(1+\sqrt{\{}5{\}})\), but in general the formula for \(k\) involves \(x{\_}0,x{\_}1,x{\_}2,\cdots\)!},
	comment = {},
	journal = {Fibonacci Quarterly},
	collections = {fun-maths-facts,integerology}
}