Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 $$ 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} $$

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.

share|improve this question
    
I recommend Dirichlet series instead of power series. Dirichlet series with coefficients $b_n$ is easy to find, then Wiener-Ikehara Tauberian Theorem solves the problem. This idea was already discussed in the AOPS forum from the link. –  i707107 Jan 9 '14 at 13:24
    
But it will be nice to see if anyone solves directly with your formula for $b_n$. –  i707107 Jan 9 '14 at 13:27
1  
OEIS reference: oeis.org/A007731 –  Michael Lugo Jun 22 at 17:39

2 Answers 2

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)$.

share|improve this answer

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 $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.