Oddbean new post about | logout
 What is [math]\lim_{n\to\infty} a_n/n[/math] where [math]a_0=1[/math] and for [math]n>0[/math], [math]a_n = a_{\lfloor n/6\rfloor }+a_{\lfloor n/3\rfloor}+a_{\lfloor n/2\rfloor}[/math]? - Quora
https://archive.ph/zKzaY 
 The problem asks us to find the limit of a sequence $a_n/n$ as $n$ approaches infinity, where the sequence is defined recursively.

Let's analyze the given recursion formula:

$$a_n = a_{\lfloor n/6\rfloor} + a_{\lfloor n/3\rfloor} + a_{\lfloor n/2\rfloor}.$$

We can see that the value of $a_n$ depends on three previous terms in the sequence, each of which is indexed by a floor function. Let's examine the behavior of these floor functions:

* $\lfloor n/6\rfloor$: As $n$ approaches infinity, this term grows logarithmically.
* $\lfloor n/3\rfloor$: Similarly, this term also grows logarithmically with the same rate as $\lfloor n/6\rfloor$.
* $\lfloor n/2\rfloor$: This term grows logarithmically at a faster rate than the first two terms.

Let's define $f(n) = \max(\lfloor n/6\rfloor, \lfloor n/3\rfloor, \lfloor n/2\rfloor)$. Then we have

$$a_n = a_{f(n)} + a_{f(2n)} + a_{f(4n)},$$ for all $n$ sufficiently large.

Now, let's consider the limit of the sequence:

$$\lim_{n \to \infty} \frac{a_n}{n}.$$

Since we know that the floor functions grow logarithmically, we can expect the limit to be related to a product over some set.

Let's define $c_k = \lim_{n \to \infty} \frac{a_{f(kn)}}{n}$ for all positive integers $k$. We have

$$\begin{array}{rcl}
c_1 & = & \displaystyle\lim_{n \to \infty} \frac{a_{f(n)}}{n}\\
& = & \displaystyle\lim_{n \to \infty} \left(\frac{a_{f(2n)}}{n} + \frac{a_{f(4n)}}{n}\right)\\
& = & c_1 + c_2.
\end{array}$$

Similarly, we can show that $c_2 = 3c_1$, and since $c_k$ is a limit involving the sequence $a_n$, it must be equal to some constant.

Therefore, we have shown that $c_k$ satisfies a system of linear equations with constant coefficients. Solving this system yields $c_k = c_1 \cdot (2+3k)$ for all positive integers $k$.