# Rewriting sylvester's sequence in a closed form

Sylvester's sequence is defined as

but according to wikipedia and wolfram mathword, this can be rewritten in closed form as

How did they reach that equation?

(sorry about the links, I'm a new user and can't post images)

-

To recap, Sylvester's sequence is defined by $$s_0=2, \qquad s_{n+1}=1+s_0\dots s_n\ \ (n\ge 0)$$ but can also be computed by the formula $$s_n=\lfloor E^{2^{n+1}}+\frac12\rfloor\qquad (*)$$ for some constant $E$. The question is how (*) can be derived.

The first step in the derivation will be to observe that each term in Sylvester's sequence is approximately the square of the previous one. The second step will be, for each $n$, to find bounds for $E$ so that (*) will work for that $n$. The third step will be to prove that all these bounds are consistent and allow some single $E$ to work for all $n$.

First, notice that, if $n\ge 1$, $$s_{n+1}=1+(s_0\dots s_{n-1})s_n =1+(s_n-1)s_n$$ so for all $n\ge 1$ (and in fact also for $n=0$) $$s_{n+1}-\frac12=(s_n-\frac12)^2+\frac14. \qquad (+)$$ For (*) to work for a given $n$, it is sufficient to have the following bounds on $E$: $$E_n^-:=(s_n-\frac12)^{2^{-(n+1)}}\le E \le E_n^+:=(s_n)^{2^{-(n+1)}}.$$ Here, the lower bound for $E$ is $E_n^-$ and the upper bound $E_n^+$. Now by (+), $$E_{n+1}^-=(s_{n+1}-\frac12)^{2^{-(n+2)}} =((s_n-\frac12)^2+\frac14)^{2^{-(n+2)}}> (s_n-\frac12)^{2^{-(n+1)}}=E_n^-$$ and, since $s_n>1$ for all $n$, $$E_{n+1}^+=(s_{n+1})^{2^{-(n+2)}} =((s_n-\frac12)^2+\frac34)^{2^{-(n+2)}}< (s_n)^{2^{-(n+1)}}=E_n^+.$$ Therefore, $$E_0^-< E_1^-< E_2^-< \dots < E_2^+< E_1^+ < E_0^+.$$ Take $E:=\sup_n E_n^-$. Then $E\ge E_n^-$ for all $n$. Also, for any $m$ and $n$, $$E_m^-\le E^-_{\max(m,n)}<E^+_{\max(m,n)}\le E_n^+. \qquad (++)$$ Now, if $E>E_n^+$ for some $n$, then, by the definition of the supremum, there would be some $m$ such that $E_m^->E_n^+$, contradicting (++). Therefore, $E$ is in every interval $[E_n^-, E_n^+]$, so (*) will be satisfied for all $n$.

This derivation is constructive in the sense that it gives an algorithm to compute $E$ to any desired accuracy (by computing the bounds $E_n^{\pm}$), although it does not give a good algorithm for computing Sylvester's sequence since, to find an $E$ that will work for any given $n$, you must first compute $s_n$.

-

For a general method, see this paper:

A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fib. Quart., 11 (1973), 429-437.

In that paper, the constant E is written as the exponential of an infinite sum, but the sum involves the terms of the sequence.

For an equivalent expression for E as a product, see

On Certain Nonlinear Recurring Sequences Solomon W. Golomb The American Mathematical Monthly Vol. 70, No. 4 (Apr., 1963), pp. 403-405.

-