, 2007

For convenience, define $a(0)=0$; then condition (1) persists for all pairs of nonnegative indices.

Lemma 1. For arbitrary nonnegative indices $n_{1}, \ldots, n_{k}$, we have
$$a\left(\sum_{i=1}^{k} n_{i}\right) \leq \sum_{i=1}^{k} 2^{i} a\left(n_{i}\right) \tag{3}$$
and
$$a\left(\sum_{i=1}^{k} n_{i}\right) \leq 2 k \sum_{i=1}^{k} a\left(n_{i}\right) . \tag{4}$$
Proof. Inequality (3) is proved by induction on $k$. The base case $k=1$ is trivial, while the induction step is provided by
$a\left(\sum_{i=1}^{k+1} n_{i}\right)=a\left(n_{1}+\sum_{i=2}^{k+1} n_{i}\right) \leq 2 a\left(n_{1}\right)+2 a\left(\sum_{i=1}^{k} n_{i+1}\right) \leq 2 a\left(n_{1}\right)+2 \sum_{i=1}^{k} 2^{i} a\left(n_{i+1}\right)=\sum_{i=1}^{k+1} 2^{i} a\left(n_{i}\right)$.

To establish (4), first the inequality
$$a\left(\sum_{i=1}^{2^{d}} n_{i}\right) \leq 2^{d} \sum_{i=1}^{2^{d}} a\left(n_{i}\right)$$
can be proved by an obvious induction on $d$. Then, turning to (4), we find an integer $d$ such that $2^{d-1}<k \leq 2^{d}$ to obtain
$$a\left(\sum_{i=1}^{k} n_{i}\right)=a\left(\sum_{i=1}^{k} n_{i}+\sum_{i=k+1}^{2^{d}} 0\right) \leq 2^{d}\left(\sum_{i=1}^{k} a\left(n_{i}\right)+\sum_{i=k+1}^{2^{d}} a(0)\right)=2^{d} \sum_{i=1}^{k} a\left(n_{i}\right) \leq 2 k \sum_{i=1}^{k} a\left(n_{i}\right) .$$

Fix an increasing unbounded sequence $0=M_{0}<M_{1}<M_{2}<\ldots$ of real numbers; the exact values will be defined later. Let $n$ be an arbitrary positive integer and write
$$n=\sum_{i=0}^{d} \varepsilon_{i} \cdot 2^{i}, \quad \text{ where } \varepsilon_{i} \in\{0,1\}$$
Set $\varepsilon_{i}=0$ for $i>d$, and take some positive integer $f$ such that $M_{f}>d$. Applying (3), we get
$$a(n)=a\left(\sum_{k=1}^{f} \sum_{M_{k-1} \leq i<M_{k}} \varepsilon_{i} \cdot 2^{i}\right) \leq \sum_{k=1}^{f} 2^{k} a\left(\sum_{M_{k-1} \leq i<M_{k}} \varepsilon_{i} \cdot 2^{i}\right) .$$
Note that there are less than $M_{k}-M_{k-1}+1$ integers in interval $\left[M_{k-1}, M_{k}\right)$; hence, using (4) we have
$$\begin{aligned} a(n) & \leq \sum_{k=1}^{f} 2^{k} \cdot 2\left(M_{k}-M_{k-1}+1\right) \sum_{M_{k-1} \leq i<M_{k}} \varepsilon_{i} \cdot a\left(2^{i}\right) \\ & \leq \sum_{k=1}^{f} 2^{k} \cdot 2\left(M_{k}-M_{k-1}+1\right)^{2} \max _{M_{k-1} \leq i<M_{k}} a\left(2^{i}\right) \\ & \leq \sum_{k=1}^{f} 2^{k+1}\left(M_{k}+1\right)^{2} \cdot \frac{1}{\left(M_{k-1}+1\right)^{c}}=\sum_{k=1}^{f}\left(\frac{M_{k}+1}{M_{k-1}+1}\right)^{2} \frac{2^{k+1}}{\left(M_{k-1}+1\right)^{c-2}} \end{aligned}$$
Setting $M_{k}=4^{k /(c-2)}-1$, we obtain
$$a(n) \leq \sum_{k=1}^{f} 4^{2 /(c-2)} \frac{2^{k+1}}{\left(4^{(k-1) /(c-2)}\right)^{c-2}}=8 \cdot 4^{2 /(c-2)} \sum_{k=1}^{f}\left(\frac{1}{2}\right)^{k}<8 \cdot 4^{2 /(c-2)}$$
and the sequence $a(n)$ is bounded.

Solution 2:

Lemma 2. Suppose that $s_{1}, \ldots, s_{k}$ are positive integers such that
$$\sum_{i=1}^{k} 2^{-s_{i}} \leq 1$$
Then for arbitrary positive integers $n_{1}, \ldots, n_{k}$ we have
$$a\left(\sum_{i=1}^{k} n_{i}\right) \leq \sum_{i=1}^{k} 2^{s_{i}} a\left(n_{i}\right)$$
Proof. Apply an induction on $k$. The base cases are $k=1$ (trivial) and $k=2$ (follows from the condition (1)). Suppose that $k>2$. We can assume that $s_{1} \leq s_{2} \leq \cdots \leq s_{k}$. Note that
$$\sum_{i=1}^{k-1} 2^{-s_{i}} \leq 1-2^{-s_{k-1}}$$
since the left-hand side is a fraction with the denominator $2^{s_{k-1}}$, and this fraction is less than 1 . Define $s_{k-1}^{\prime}=s_{k-1}-1$ and $n_{k-1}^{\prime}=n_{k-1}+n_{k}$; then we have
$$\sum_{i=1}^{k-2} 2^{-s_{i}}+2^{-s_{k-1}^{\prime}} \leq\left(1-2 \cdot 2^{-s_{k-1}}\right)+2^{1-s_{k-1}}=1$$
Now, the induction hypothesis can be applied to achieve
$$\begin{aligned} a\left(\sum_{i=1}^{k} n_{i}\right)=a\left(\sum_{i=1}^{k-2} n_{i}+n_{k-1}^{\prime}\right) & \leq \sum_{i=1}^{k-2} 2^{s_{i}} a\left(n_{i}\right)+2^{s_{k-1}^{\prime}} a\left(n_{k-1}^{\prime}\right) \\ & \leq \sum_{i=1}^{k-2} 2^{s_{i}} a\left(n_{i}\right)+2^{s_{k-1}-1} \cdot 2\left(a\left(n_{k-1}\right)+a\left(n_{k}\right)\right) \\ & \leq \sum_{i=1}^{k-2} 2^{s_{i}} a\left(n_{i}\right)+2^{s_{k-1}} a\left(n_{k-1}\right)+2^{s_{k}} a\left(n_{k}\right) \end{aligned}$$

Let $q=c / 2>1$. Take an arbitrary positive integer $n$ and write
$$n=\sum_{i=1}^{k} 2^{u_{i}}, \quad 0 \leq u_{1}<u_{2}<\cdots<u_{k} .$$
Choose $s_{i}=\left\lfloor\log _{2}\left(u_{i}+1\right)^{q}\right\rfloor+d\ (i=1, \ldots, k)$ for some integer $d$. We have
$$\sum_{i=1}^{k} 2^{-s_{i}}=2^{-d} \sum_{i=1}^{k} 2^{-\left\lfloor\log _{2}\left(u_{i}+1\right)^{q}\right\rfloor},$$
and we choose $d$ in such a way that
$$\frac{1}{2}<\sum_{i=1}^{k} 2^{-s_{i}} \leq 1$$
In particular, this implies
$$2^{d}<2 \sum_{i=1}^{k} 2^{-\left\lfloor\log _{2}\left(u_{i}+1\right)^{q}\right\rfloor}<4 \sum_{i=1}^{k} \frac{1}{\left(u_{i}+1\right)^{q}} .$$
Now, by Lemma 2 we obtain
$$\begin{aligned} a(n)=a\left(\sum_{i=1}^{k} 2^{u_{i}}\right) & \leq \sum_{i=1}^{k} 2^{s_{i}} a\left(2^{u_{i}}\right) \leq \sum_{i=1}^{k} 2^{d}\left(u_{i}+1\right)^{q} \cdot \frac{1}{\left(u_{i}+1\right)^{2 q}} \\ & =2^{d} \sum_{i=1}^{k} \frac{1}{\left(u_{i}+1\right)^{q}}<4\left(\sum_{i=1}^{k} \frac{1}{\left(u_{i}+1\right)^{q}}\right)^{2} \end{aligned}$$
which is bounded since $q>1$.