# Some Doubly Exponential Sequences

• Published in 1970
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$!

## Other information

key
SomeDoublyExponentialSequences
type
article
2020-07-13
date_published
1970-09-05
journal
Fibonacci Quarterly

### 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 = {},
}