3

We all know the Fibonacci sequence, but how about a version where you take the sum of squares of two previous numbers:

$$\begin{cases}a_0 = 0\\ a_1=1\\ a_{n} = a_{n-1}^2 + a_{n-2}^2 \end{cases} $$

There is an OEIS entry of this sequence that has the formula

$$a_n = \lfloor A^{2^{n-1}}\rfloor$$ where $A=1.2353927377854368896223310132284408243...$

But how does one get this number and can the generating function of $a_n$ be derived somehow? I've tried it, but the non-linearity seems to hinder the process.

Somos
  • 35,251
  • 3
  • 30
  • 76
ploosu2
  • 8,707

1 Answers1

2

The constant $\, A \,$ is easily found as $\, A = \lim_{n\to \infty} a_n^{2^{1-n}}. \,$ The convergence is very rapid. Now the generating function of any sequence of numbers is a formal power series and this is the case here also. The trouble is that the sequence grows so rapidly that the radius of convergence is $\,0.\,$ This severely limits what you can do with the generating function. In rare cases, for example the alternating factorial numbers (A133943), the generating function can be interpreted as an integral or a continued fraction. In some cases the exponential generating function is well behaved. In the case of this sequence, it seems hopeless to be able to do anything significant with the generating function power series.

Somos
  • 35,251
  • 3
  • 30
  • 76
  • 4
    Incidentally (for OP), it's a general theorem that any recurrence of the form $a_{n+1}=a_n^2+\epsilon_n$, where $\epsilon_n$ is 'sufficiently smaller' (I don't recall the specific hypotheses, but they're pretty broad), has a solution of the form $a_n=\lfloor A^{2^n}\rfloor$ for some constant $A$, and generically these sorts of recurrences almost never have closed forms more explicit than this. – Steven Stadnicki Jun 24 '18 at 19:05
  • @StevenStadnicki You are correct. I could have mentioned that. Thanks. – Somos Jun 24 '18 at 19:16
  • @StevenStadnicki Maybe the paper http://www.fq.math.ca/Scanned/11-4/aho-a.pdf mentioned in this comment. – dxiv Jun 24 '18 at 19:48