Can I get a bound on $\sum_i x_i$ given a bound on $\sum_i x_i/(1+x_i)$?

Question

Suppose that $x_i \geq 0$ and for any $n \geq n_0$, we have

$$\sum_{i=1}^n \frac{x_i}{1+x_i} \leq a \log n + b,$$

for some positive constants $a$ and $b$. Given this information, is it possible to show that for all $n \geq n_1$

$$\sum_{i=1}^n x_i \leq c \log n + d?$$

An upper bound that is a polynomial function in $\log n$ is also fine.

---

• My attempt:

First, note that $0 \leq \frac{x_i}{x_i+1} \leq 1$. I can give examples of three cases where the claim is true.

(1) Suppose that $\frac{x_i}{1+x_i}$ is a harmonic series $$\frac{x_i}{1+x_i} = \frac{1}{i} \rightarrow x_i = \frac{1}{i-1} \text{ for } i \geq 2.$$

Then, $\sum_i x_i$ is also harmonic and bounded by $O(\log n)$.

(2) Suppose that $2 \log n$ elements out of $n$ elements are equal to $1/2$ and all others are zero. We have

$$\sum_{i=1}^n x_i = \log n$$

(3) Suppose that all terms are equal

$$\frac{x_i}{1+x_i} = \frac{\log n}{n} \Rightarrow x_i = \frac{\log n}{n - \log n}$$

And we have $\sum_{i=1}^n x_i = \frac{n \log n}{n - \log n}$ which is of order $\log n$.

Answer 1

I think the answer is negative. The proposition seems correct when the sequence changes gently, but there is a counter example that is a bit abnormal.

For convenience and without loss of generality, assume $a=1,b=0$ and we have $$\sum_{i=1}^n\frac{x_i}{1+x_i}\le\log n$$ We care about $i=[\mathrm e^k+1],k\in\mathbb N$ which provides a increment $1$ of the right side(for every $k\in\mathbb N$). So if $\forall i\neq [\mathrm e^k+1],x_i=0$, equation above will always holds for arbitrary huge $x_{[\mathrm e^k+1]}$(this is because $0\le\frac{x}{1+x}\le 1$ holds for any positive $x$) and one could leads to an uncontrollable change of $\sum_{i=1}^n x_i$.

As a specific construction, let $x_{[\mathrm e^k+1]}=[\mathrm e^k+1]-[\mathrm e^{k-1}+1]$ for $k>1$ and $x_{[\mathrm e^k+1]}=[\mathrm e^k+1]$ for $k=1$, then we have $$\sum_{i=1}^{[\mathrm e^k+1]}x_i=[\mathrm e^k+1]$$ which provides a bound of $O(n)$ to $\sum_{i=1}^n x_i$.

Words below is the reply to the question in comment.

I don't know if it is trivial or suit to your application, $x_i\to 0(i\to\infty)$ is an extra but defective assumption to holds the claim(to say 'defective' is because we could still find some bad examples lead to the conclusion while violate all the assumptions). I'd be happy if it's helpful and the proof is put below.

Since the constant is much less tham the logarithm, $$\sum_{i=1}^nx_i\le r\log n+s\iff\sum_{i=1}^nx_i\le t\log n\iff \overline{\lim_{n\to\infty}}\frac{\sum_{i=1}^nx_i}{\log n}\le t \text{ for some }a,b,c$$ according to O'Stolz theorem and Lagrange's mean value theorem, we obtain $$\lim_{n\to\infty}\frac{\sum_{i=1}^n\frac{x_i}{1+x_i}}{\sum_{i=1}^nx_i}=\lim_{n\to\infty}\frac{\sum_{i=1}^nf(x_i)}{\sum_{i=1}^nx_i}=\lim_{n\to\infty}\frac{f(x_{n+1})-f(x_n)}{x_{n+1}-x_n}=\lim_{n\to\infty}f'(\xi)=\lim_{n\to\infty}\frac{1}{(1+x)^2}\mid_{x=\xi}=1$$ where $f(x)=\frac{x}{1+x},\xi\in(x_n,x_{n+1})$ or $\xi\in(x_{n+1},x_n)$, so$$\overline{\lim_{n\to\infty}}\frac{\sum_{i=1}^nx_i}{\log n}=\overline{\lim_{n\to\infty}}\frac{\sum_{i=1}^n\frac{x_i}{1+x_i}}{\log n}\le a'$$which completes the proof.

Answer 2

Let $x_j = \ln n$ for $1 \leq j \leq [\ln n]$ and $x_j =0 $ for $j > [\ln n]$

Where $[m]$ is the floor function of $m$.

Then $\sum \limits_{j=1}^{[\ln n]} \frac{x_j}{1+x_j} \leq \sum \limits_{j=1}^{[\ln n]} 1 = [\ln n] \leq \ln n+1 $ for $a=b=1$.

On the other side $\sum \limits_{j=1}^{[\ln n]} x_j =\sum \limits_{j=1}^{[\ln n]} \ln j = \ln ([\ln n]!) \approx [\ln n] \ln ([\ln n]) \approx \ln n \ln \ln n $ so no constant $c,d$ are valid for sufficiently large $n$.