Some Doubly Exponential Sequences

• Published in 1970
• Added on 2020-07-13

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

• http://neilsloane.com/doc/doubly.html

Other information

BibTeX entry

@article{SomeDoublyExponentialSequences,
	key = {SomeDoublyExponentialSequences},
	type = {article},
	title = {Some Doubly Exponential Sequences},
	author = {A. V. Aho and N. J. A. Sloane},
	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 = {},
	date_added = {2020-07-13},
	date_published = {1970-12-07},
	urls = {http://neilsloane.com/doc/doubly.html},
	collections = {fun-maths-facts,integerology},
	url = {http://neilsloane.com/doc/doubly.html},
	urldate = {2020-07-13},
	year = 1970,
	journal = {Fibonacci Quarterly}
}