Generating function solution to previous question $a_{n}=a_{\lfloor n/2\rfloor}+a_{\lfloor n/3 \rfloor}+a_{\lfloor n/6\rfloor}$

In attempting to answer this question, I reduced it to a seemingly simple generating functions question, but after days of work was unable to construct a proof. Since I do not have experience trying to do asymptotics with generating functions, I would like to know if a proof is salvageable from these methods.

The problem introduces the sequence $a_n$, defined by $a_0 = 1$ and $$ a_{n}=a_{\left\lfloor n/2\right\rfloor}+a_{\left\lfloor n/3 \right\rfloor}+a_{\left\lfloor n/6\right\rfloor} $$ and asks for a proof that $$ \lim_{n\to\infty}\dfrac{a_{n}}{n}=\dfrac{12}{\log{432}}. $$ Writing the generating function $\displaystyle A(x) = \sum_{n \ge 0} a_n x^n$, this translates to $$ A(x) = (1 + x)A(x^2) + (1 + x + x^2) A(x^3) + (1 + x + x^2 + \cdots + x^5)A(x^6) - 2 $$

Even better, let $b_0 = a_0$ and $b_n = a_n - a_{n-1}$ for all $n \ge 1$, and define the generating function $\displaystyle B(x) = \sum_{n \ge 0} b_n x^n = (1 - x)A(x)$. Multiplying the above by $(1-x)$ gives $$ (1 - x)A(x) = (1 - x^2)A(x^2) + (1 - x^3)A(x^3) + (1 - x^6)A(x^6) + 2x - 2 $$ i.e. $$ B(x) = B(x^2) + B(x^3) + B(x^6) + 2x - 2 \tag{1} $$

After unsuccessfully trying to do assymptotics with the above elegant formula, I used it to find an explicit representation of $B$, using the Delannoy Numbers:

$$ B(x) = 1 + 2 \sum_{l, m \ge 0} \sum_{d \ge 0} 2^d {l \choose d}{m \choose d} x^{2^l 3^m} $$

It follows that in fact \begin{align*} b_n&= \begin{cases} 1 &n=0 \\ 2 \sum_{d \ge 0} 2^d \binom{l}{d} \binom{m}{d} &n =2^l3^m \\ 0 &\text{otherwise} \end{cases} \\[10pt] a_n&=1+2\sum_{d\ge0}2^d\sum_{\begin{matrix}l,m\ge0\\2^l 3^m \le n\end{matrix}}{l \choose d}{m \choose d} \tag{2} \end{align*}

One can do naive bounds on the sum in (2) - replacing the condition $2^l 3^m \le n$ with $2^l 2^m \le n$ and $3^l 3^m \le n$ for upper and lower bounds, respectively. But this isn't good enough; it gives (after algebra and combinatorial work) approximately $$ \frac{n^{\log_3(1 + \sqrt{2}) - 1}}{2} < \frac{a_n}{n} < \frac{n^{\log_2(1 + \sqrt{2}) - 1}}{2} $$

This seems to suggest trying to approximate (2) with the condition $(1 + \sqrt{2})^l (1 + \sqrt{2})^m \le n$, but I have no idea how to justify that.

At any rate, I've made too much of what feels like progress to give up on the problem, and if anyone can think of a way to use (2) to get a solution or else to use (1) and find the asymptotics directly, I'd be very thankful.

Solution 1:

The "master theorem" by Leighton is applicable. For a recurrence $T(z) = g(z) + \sum_{1 \le k \le n} a_k T(b_k z + h_k(z))$ where $z \ge 0$, such that there are sufficient base cases; all $a_k > 0$ and $0 < b_k < 1$; there is a constant $c$ such that $\lvert g(z) \rvert = O(c^z)$; and all $\lvert h_k(z)\rvert = O(z /(\log z)^2$. Then for $p$ such that $\sum_{1 \le k \le n} a_k b_k^p = 1$, the solution satisfies:

$$ T(z) = \Theta \left( z^p \left( 1 + \int_1^z \frac{g(u)}{u^{p + 1}} \, \mathrm{d} u \right) \right) $$

The $h_k$ are fudge factors, they cover cases like the difference to floors and ceilings.

Here we have $g(z) = 0$, $a_1 = a_2 = a_3 = 1$, $b_1 = 1/2$, $b_2 = 1/3$, and $b_3 = 1/6$, so that $p = 1$. With $g(z) = 0$, the theorem tells you that $a_n = \Theta(n)$.

Solution 2:

A complete asymptotic solution to exactly this kind of recurrences is derived by Erdös et al "The Asymptotic Behavior of a Family of Sequences" Pacific Journal of Mathematics 126:2 (1987), pp 227-241. They use this exact recurrence as an example, and show that:

$$ a_n \sim \frac{12}{\log 432} n $$