6

This seems like a really straightforward recurrence.

I wrote out the first few terms: $1,1,2,6,42,1806$... It seems to grow faster than $n!$ but slower than $n^n$. Any suggestions about the closed form or the rate of growth are very welcome.

Alex
  • 19,262

1 Answers1

6

$$ a_{n+1} = a_n (1+a_n) $$ ..................

So, with or without closed form, there is some positive real $\theta$ such that $$ a_n \approx \theta^{\left( 2^n \right)} $$

and $\theta $ can be approximated by $a_n^{1/2^n},$ while $\log \theta$ can be approximated by $\frac{\log a_n}{2^n}. $

EEddIItt: Convergence for $\theta$ should be rapid. I get that $\frac{\log a_n}{2^n} $ increases with $n,$ however $$ \frac{\log a_{n+1}}{2^{n+1}} - \frac{\log a_n}{2^n} < \frac{\log \left(1 + \frac{1}{2 a_n} \right)}{2^n} $$

I numbered my version with $$ a_1 = 6, \; a_2 = 42, \; a_3 = 1806. $$ With this numbering I get $\theta \approx 2.553317.$ Anyway, just look at the logarithms, this grows much faster than $n^n$

Will Jagy
  • 139,541
  • 2
    This paper has some closed form results and will be applicable to $x_{n} = a_{n} + \frac{1}{2}$. http://www.fq.math.ca/Scanned/11-4/aho-a.pdf – Aryabhata Nov 25 '13 at 05:04
  • @Aryabhata, thank you. They seem to be saying that there are a few cases with a closed form for my $\theta$ but that this is a matter of luck. They call it $k.$ – Will Jagy Nov 25 '13 at 05:19
  • In particular, they get no closed form for $k$ in $x_{n+1} = x_n^2 + 1,$ which is the closest relative. – Will Jagy Nov 25 '13 at 05:33
  • They define $k$ in terms of a limit, but in this case, the $x_n$ I defined above will be half an odd integer, and you have a closed form, assuming $k$ is part of your constants. See Equation (21) on page 434. – Aryabhata Nov 25 '13 at 16:44
  • Can you explain the step from $a_{n+1} = a_{n}(1+a_{n})$ to $\theta^{2^n}$? I don't quite get it – Alex Nov 25 '13 at 20:10
  • This also doesn't quite answer the question, but I guess it's the closest solution available. – Alex Nov 25 '13 at 20:14
  • @Alex, I suggest you download the pdf to which Aryabhata links, and read it with an eye to his comment about $x_n = a_n + 1/2.$ Note that, no matter what $a_{n+1} > a_n^2.$ I did write some calculations last night but can't currently find them. – Will Jagy Nov 25 '13 at 20:33