Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sylvester's sequence is defined as

http://upload.wikimedia.org/math/1/6/f/16feba8ab6368dc9d965dbec35e445bb.png

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

http://upload.wikimedia.org/math/e/d/b/edb03103fbb72767dd6e3ab262ed9e66.png

How did they reach that equation?

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

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.