If $(a_n)$ is a sequence such that $a_n=a_{f(n)}+a_{g(n)}$, where $\lim \frac{f(n)}{n}+\lim\frac{g(n)}{n}<1$, can we claim that $\lim\frac{a_n}{n}=0$? The inspiration for this question came with an attempt to solve this.
Let $(a_n)_{n\in\Bbb{N}}$ be a sequence of real numbers satisfying $a_n = a_{f(n)} + a_{g(n)}~\forall n\in\Bbb{N}$, where $f, g: \Bbb{N}\rightarrow \Bbb{N}$ are functions such that $\begin{aligned}\lim \frac{f(n)}{n}+\lim\frac{g(n)}{n}<1\end{aligned}$. Can we claim that $\begin{aligned}\lim\frac{a_n}{n} = 0\end{aligned}$ (i.e., that this sequence grows more slowly than any linear function)?
I know the statement is true if we assume that the limit exists. In fact, if $\begin{aligned}\lim\frac{a_n}{n} = \alpha\end{aligned}$, then
$$\alpha = \lim\frac{a_n}{n} = \lim \frac{a_{f(n)}+a_{g(n)}}{n} = \lim \Big(\frac{f(n)}{n}\frac{a_{f(n)}}{f(n)}+\frac{g(n)}{n}\frac{a_{g(n)}}{g(n)}\Big) = \alpha\Big( \lim \frac{f(n)}{n}+\lim\frac{g(n)}{n}\Big)$$
Because $\begin{aligned}\lim \frac{f(n)}{n}+\lim\frac{g(n)}{n}\neq 1\end{aligned}$ we have $\alpha = 0$. Therefore, it remains to be seen whether the limit really exists.
My ideia was to try to show that the sequence $\begin{aligned}\Big(\frac{a_n}{n}\Big)_{n\in\Bbb{N}}\end{aligned}$ is decreasing from a certain point, but I don't know how to proceed.
 A: Your claim about the limit of $b_n=\frac{a_n}{n}$ is indeed true. Here is a proof.
Choose $\alpha,\beta$ with $\lim_{n\to\infty}\frac{f(n)}{n} \lt \alpha$, $\lim_{n\to\infty}\frac{g(n)}{n} \lt \beta$ and $\alpha+\beta \lt 1$.
By the definition of a limit, there is a $N$ such that $f(n)\lt \alpha n$
and $g(n)\lt \beta n$ for $n\geq N$.
Let $N_0={\sf max}(N,\frac{1}{1-\alpha},\frac{1}{1-\beta})$. Then for $n\geq N_0$, we have $\alpha n \leq n-1$ whence $f(n) \leq n-1$ ; similarly $g(n) \leq n-1$, so that
$$
f(n) \lt n, g(n) \lt n \ (n\geq N_0) \tag{1}
$$
On the other hand, from $n\geq N_0 \geq \frac{1}{1-\alpha} \geq \frac{\alpha}{1-\alpha}$ we deduce $n\geq \frac{1}{\frac{1}{\alpha}-1}$ or $n\big(\frac{1}{\alpha}-1\big)\geq 1$, so that $\lfloor \frac{n}{\alpha}\rfloor \geq n+1$, and hence
$$
\lfloor\frac{n}{\alpha}\rfloor \gt n, \lfloor\frac{n}{\beta}\rfloor \gt n \ (n\geq N_0) \tag{2}
$$
It follows from (1) that
$$
|b_n|=\bigg|\frac{f(n)}{n}b_{f(n)}+\frac{g(n)}{n}b_{g(n)}\bigg| \leq
(\alpha + \beta) \max(|b_{f(n)}|,|b_{g(n)}|) \ (n\geq N_0) \tag{3}
$$
Let $M=\max\big(|b_k| \ | \ 1 \leq k \leq N_0\big)$ and $N_1=\lfloor \frac{N_0}{\max(\alpha,\beta)}\rfloor=\min(\lfloor \frac{N_0}{\alpha}\rfloor,\lfloor \frac{N_0}{\beta}\rfloor)$. By (2), we have $N_2 \gt N_1$. Let $n\in [N_0,N_1]$. Then $f(n)\leq \alpha n \leq \alpha N_1 \leq N_0$ and hence  $|b_{f(n)}|\leq M$ ; similarly $|b_{g(n)}|\leq M$. Combining this with (3), we deduce
$$
 |b_n| \leq (\alpha+\beta) M \ (n \in [N_0,N_1]) \tag{4}
$$
Since $(\alpha+\beta) M \lt M$, we see that $M$ is also equal to $\max\big(|b_k| \ | \ 1 \leq k \leq N_1\big)$, and the argument we have just made can be repeated with $N_1$ in place of $N_0$ ; we then deduce $|b_n| \leq (\alpha+\beta) M$ for $n\in [N_1,N_2]$ where $N_2=\lfloor \frac{N_1}{\min(\alpha,\beta)}\rfloor \gt N_1$. Iterating this argument, it is now clear that
$$
\forall n \geq N_0, |b_n| \leq (\alpha+\beta) M  \tag{4'}
$$
Combining (4') with the definition of $M$, we see that
$$
\forall n \in {\mathbb N}, |b_n| \leq M \tag{5}
$$
We can now revisit (3) and strengthen it. Suppose that for some $T\geq N_0$ and $\varepsilon >0$ we have
$$
\forall n \geq T, |b_n| \leq \varepsilon \tag{6}
$$
We can then deduce the following. Let $n\in{\mathbb N}$. If $f(n)\leq T$, then $|b_{f(n)}| \leq M$ and hence $|\frac{a_{f(n)}}{n}| \leq \frac{Mf(n)}{n} \leq \frac{MT}{n}$. If, on the other hand, $f(n) \geq T$, then $|b_{f(n)}| \leq \varepsilon$ by (6), whence $|\frac{a_{f(n)}}{n}| \leq \frac{Mf(n)}{n} \leq \alpha\varepsilon$ (it is here that we use the hypothesis $T\geq N_0$). In both cases, we have $|\frac{a_{f(n)}}{n}| \leq \max(\frac{MT}{n},\alpha\varepsilon)$ and similarly $|\frac{a_{g(n)}}{n}| \leq \max(\frac{MT}{n},\beta\varepsilon)$. Combining the two, we have
$$
\forall n \in {\mathbb N}, |b_n| \leq  |\frac{a_{f(n)}}{n}|+|\frac{a_{g(n)}}{n}|
\leq \max(\frac{MT}{n},\alpha\varepsilon) + \max(\frac{MT}{n},\beta\varepsilon)
\tag{7}
$$
For large enough $n$, the RHS of (7) reduces to $(\alpha+\beta)\varepsilon$ ; in other words,
$$
\forall n \geq T', |b_n| \leq (\alpha+\beta)\varepsilon \ (\textrm{where} \ T'=\frac{MT}{\min(\alpha,\beta)\varepsilon})\tag{6'}
$$
Then, if we define a sequence $(T_k)_{k\geq 1}$ with $T_1=N_0$ and $T_{k+1}=\lceil\frac{MT_k}{\min(\alpha,\beta)}\rceil$ then we have
$$
\forall n \geq T_k, |b_n| \leq M(\alpha+\beta)^k  \tag{8}
$$
The proof of (8) is by induction on $k$ : the base case follows from (5), and the induction step is a special case of  the implication $(6) \Rightarrow (6')$ that we have just shown (with $\varepsilon = M(\alpha+\beta)^k$). This shows that $(b_n)\to 0$ as wished.
