# 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?

• I find $a_{n+2}=a_{n+1}+a_{n}(a_{n+1}-a_{n})$ and we have to show $\lim_{n\to \infty} ln(a_{n})/\phi^{n}$ exists. Any ideas? Commented Jul 23, 2016 at 4:22
• At least the growth rate of $\ln \ln a_n$ shouldn't be too hard: for $n>1$ we have $b_n > a_n$ so that $b_{n+1}/a_{n+1} > a_n/2 \to \infty$, so $a_{n+1}/a_n = 1 + b_n/a_n\to \infty$ and so $a_{n+2}$ behaves like $a_n a_{n+1}$. I'm guessing $c$ is formed from the accumulation of the multiplicative errors of this approximation, so perhaps it can be represented as an infinite product (involving $a_n$). Commented Jul 23, 2016 at 5:05
• Pro tip: always search the Online Encyclopedia of Integer Sequences Commented Jul 23, 2016 at 6:11
• @GregMartin Yes, I edited the corresponding OEIS entry several days ago. I added a link to it in my question. Commented Jul 23, 2016 at 18:00
• The OEIS entry actually claims an asymptotic for $a_n$ itself rather than $\log a_n$, which is a much stronger statement. I'm not sure if it is true or not. Has anyone taken a look at that? Commented Jul 24, 2016 at 13:57

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.

• This is of course the right heuristic, and possibly even an approach that can be made into a proof. But "it seems clear" doesn't reach the standard for an answer, in my opinion. Commented Jul 23, 2016 at 19:17
• Fair enough. An actual proof is on the way. Commented Jul 24, 2016 at 13:35