A pair of sequences defined by mutual addition/multiplication

Define sequences $\{a_n\},\,\{b_n\}$ by mutual recurrence relations: $$a_0=b_0=1,\quad a_{n+1}=a_n+b_n,\quad b_{n+1}=a_n\cdot b_n.\tag1$$ The sequence $\{a_n\}$ begins: $$1,\,2,\,3,\,5,\,11,\,41,\,371,\,13901,\,5033531,\,69782910161,\,...\tag2$$ It appears in OEIS as $A003686$ under the name "Number of genealogical $1$-$2$ rooted trees of height $n$." (note that indexing starts with $1$ rather than $0$ in OEIS).

It seems that for $n\to\infty$, $$\ln\ln a_n=n\cdot\ln\phi+c+o(1),\tag3$$ where $\phi=\frac{1+\sqrt5}2$ is the golden ratio, the last term $o(1)$ exponentially decays in absolute value (and seems to have alternating signs for $n\ge8$), and the constant $$c\approx-1.11328370529375397170010672464407271138948509227239...\tag4$$ (see more digits here)

The equivalent asymptotics is given in OEIS without proof.

How can we prove $(3)$?

Is there a closed form or some alternative representation (integral, series, product, continued fraction, etc) for the constant $c$? Is it irrational?

Is there an efficient way to numerically calculate $c$ to a higher precision?

Solution 1:

Given a sequence $\{A_n\}$ with the Fibonacci recurrence relation $$A_{n+2} = A_{n+1} + A_n$$ we get the well-known asymptotic $$A_n \sim C\phi^n$$ where $\phi$ is the golden ratio and $C$ depends on the initial terms $A_1$ and $A_2$. For example if $A_1 = A_2 = 1$ we get the Fibonacci sequence and $C = 1/\sqrt{5}$. But if we start with different initial values we get a difference constant $C$.

Now consider a more general recurrence: $$A_{n+2} = A_{n+1} + A_n + g_n$$ where $g_n \rightarrow 0$ as $n \rightarrow \infty$. Then it seems clear that we'll also get the asymptotic $$A_n \sim C\phi^n$$ where now the constant $C$ depends also on the function $g_n$.

In particular, for our sequence we have $$\log a_{n+2} = \log a_{n+1} + \log a_{n} + \log \left(1 + \frac{1}{a_n} - \frac{a_n}{a_{n+1}}\right)$$ where the last term goes to zero pretty quickly, so we have $$\log a_n \sim C\phi^n$$ for some $C$, but I am doubtful that we can get a closed formula for $C$.

DETAILED PROOF ADDED LATER:

LEMMA: Let $$A_{n+2} = A_{n+1} + A_n + c$$ be a recurrent sequence with constant $c$ and initial conditions $A_1$ and $A_2$. Then $$A_n = \frac{\phi^{n-1}-\psi^{n-1}}{\sqrt{5}} A_2 + \frac{\phi^{n-2}-\psi^{n-2}}{\sqrt{5}} A_1 + \left[\left(\frac{5+3\sqrt{5}}{10}\right)\phi^{n-2} + \left(\frac{5-3\sqrt{5}}{10}\right)\psi^{n-2} -1 \right]c$$ where $\phi = (1+\sqrt{5})/2$ and $\psi = (1-\sqrt{5})/2$. In particular, as $n \rightarrow \infty$, $$A_n = \left(\frac{\phi A_2 + A_1}{\sqrt{5}} + \frac{5+3\sqrt{5}}{10} c\right)\phi^{n-2} - c + o(1).$$

PROPOSITION: Let $$A_{n+2} = A_{n+1} + A_n + c_n$$ be a recurrent sequence with initial conditions $A_1$ and $A_2$ and $c_n$ a bounded sequence. Then $$A_n \sim C \phi^n$$ for some constant $C$ and $\phi = (1+\sqrt{5})/2$, i.e. the limit $$\lim_{n \rightarrow \infty} \frac{A_n}{\phi^n}$$ exists.

Proof of LEMMA: Write recurrence in matrix form and take matrix powers.

Proof of PROPOSITION: We can use the Lemma to bound our sequence by sequences with constants $c = M$ and $c = -M$ to see that $A_n/\phi^n$ is bounded, say $|A_n/\phi^n| \leq B.$

We will further prove that $A_n/\phi^n$ is a Cauchy sequence, and therefore converges to a limit. We have $|c_n| < M$ for some $M$. Let $\epsilon > 0$. Choose $N$ large enough so that $M / \phi^N < \epsilon$. For $n \geq N$, we again use the Lemma to bound our sequence by sequences with constants $c = M$ and $c = -M$, but now starting from at initial values $A_{N-1}$ and $A_N$. So we have $$\left| A_n - \left(\frac{\phi^{n-N+1}-\psi^{n-N+1}}{\sqrt{5}} A_N + \frac{\phi^{n-N}-\psi^{n-N}}{\sqrt{5}} A_{N-1} \right)\right|$$ $$\leq \left(\left(\frac{5+3\sqrt{5}}{10}\right)\phi^{n-N} + \left(\frac{5-3\sqrt{5}}{10}\right)\psi^{n-N} -1 \right)M.$$ We divide through by $\phi^n$ to get $$\left| \frac{A_n}{\phi^n} - \left(\phi \frac{1 - (\psi/\phi)^{n-N+1}}{\sqrt{5}} \frac{A_N}{\phi^N} + \frac{1}{\phi}\frac{1-(\psi/\phi)^{n-N}}{\sqrt{5}} \frac{A_{N-1}}{\phi^{N-1}} \right)\right|$$ $$\leq \left(\left(\frac{5+3\sqrt{5}}{10}\right) + \left(\frac{5-3\sqrt{5}}{10}\right)\left(\frac{\psi}{\phi}\right)^{n-N} - \frac{1}{\phi^{n-N}} \right) \frac{M}{\phi^N} < 2\epsilon.$$

Now choose $N_2 > N$ large enough so that $|\psi/\phi|^{N_2-N} B < \epsilon$. Then for $n \geq N_2$ we have $$\left| \frac{A_n}{\phi^n} - \left(\phi \frac{1}{\sqrt{5}} \frac{A_N}{\phi^N} + \frac{1}{\phi}\frac{1}{\sqrt{5}} \frac{A_{N-1}}{\phi^{N-1}} \right)\right| < 3 \epsilon.$$ By the triangle inequality, when $n \geq N_2$, we have $$\left| \frac{A_n}{\phi^n} - \frac{A_{N_2}}{\phi^{N_2}}\right| < 6 \epsilon,$$ proving that $A_n/\phi^n$ is a Cauchy sequence.