Behaviour of $u_{n}=u_{\lfloor n/2\rfloor}+u_{\lfloor n/3\rfloor}+u_{\lfloor n/6\rfloor}$

Question

I was looking at the following sequence: $$\begin{cases} u_0=1\\ \forall n \in \mathbb{N^*}, \quad u_{n}=u_{\lfloor n/2\rfloor}+u_{\lfloor n/3\rfloor}+u_{\lfloor n/6\rfloor} \end{cases}$$ and wanted to show that $$\forall n \in \mathbb{N}, \quad u_n\leq 3(n+1)$$ I know a way to do this is to see that $u_{n+1}\leq u_n+3$ but I can't seem to easily prove that fact (case by case analysis should work, I guess).

I also wrote a Python script to check the first $1000000$ terms and found that the best bounding constant isn't $3$, but actually $C=\frac{169}{73}$. I read somewhere that you could find an explicit expression of $C$ in terms of $u_0$, but I can't figure out how. What am I missing? Any help would be appreciated.

Answer 1

See OEIS sequence A007731. This references a paper of P. Erdős, A. Hildebrand, A. Odlyzko, P. Pudaite and B. Reznick, The asymptotic behavior of a family of sequences, Pacific J. Math., 126 (1987), pp. 227-241, according to which the limit of $u_n/n$ is $12/\log(432)$.

Answer 2

Why don't you simply prove $\forall n\in\mathbb{N_+},\ u_n\leq3n$ by induction?

At least $u[1:6]$ satisfies this inequality.