Is there a non-decreasing sequence $(a_n)$ such that $\sum 1/a_n=\infty$ and $\sum1/(n+a_n)<\infty$?

This question is motivated by this one. In the accepted answer, two positive non-decreasing sequences $(a_n)$ and $(b_n)$ are given such that $$\sum_{n=1}^\infty\frac{1}{a_n}=\sum_{n=1}^\infty\frac{1}{b_n}=\infty,\quad\text{but}\quad \sum_{n=1}^\infty\frac{1}{a_n+b_n}<\infty.$$ Now take $b_n=n$.

Is there a positive non-decreasing sequence $(a_n)$ such that $$\sum_{n=1}^\infty\frac{1}{a_n}=\infty,\quad\text{but}\quad \sum_{n=1}^\infty\frac{1}{n+a_n}<\infty\,?$$

Some remarks:

1. If $a,b>0$, then $\max(a,b)\le a+b\le2\max(a,b)$. Thus $$\sum_{n=1}^\infty\frac{1}{n+a_n}<\infty\quad\text{is equivalent to}\quad\sum_{n=1}^\infty\frac{1}{\max(n,a_n)}<\infty$$
2. If we eliminate the condition that $(a_n)$ be non-decreasing, it is easy to find an example, like $a_n=n^2$ if $n$ is not a squere, $a_n=\sqrt{n}$ is $n$ is a square.
3. If such a sequence existes, it must satisfy $$\sup\frac{a_n}{n}=\sup\frac{n}{a_n}=\infty.$$
-

If $b_n$ is decreasing and positive, and if $\sum b_n$ converges, then $\lim\limits_{n\rightarrow\infty} nb_n=0$.

Now, if $\sum {1\over n+a_n}$ converged, we would have the string of implications: $${n\over n+a_n}\rightarrow 0\quad \Rightarrow \quad{a_n\over n} \rightarrow\infty \quad\Rightarrow\quad {n\over a_n}\rightarrow0\quad\Rightarrow \quad\sup{n\over a_n}<\infty.$$

-
@Gortaur: If $b_n = n^{\alpha}$ with $\alpha > 1$, then $\sum \frac{1}{a_n + b_n}$ converges for every non-negative sequence $a_n$ using the comparison test. –  Willie Wong Nov 21 '11 at 14:36
@Willie: thanks a lot –  Ilya Nov 21 '11 at 14:37
@Gortaur I think you mean $\alpha<1$ (otherwise $\sum1/n^\alpha<\infty$). This is the first thing I checked, and it works. However, I cannot make it work for $n\log n$. –  Julián Aguirre Nov 21 '11 at 14:39
@Julian: I meant $\alpha>1$ since was focused only on the technique David advised - for $\alpha<1$ it was clear that it works. I missed a point that the case $\alpha>1$ would be rejected even before. Nice question by the way! –  Ilya Nov 21 '11 at 14:41

A self contained and elementary proof. (See below the cut for the "explanation" invoking Abel's theorem.)

As noted by the OP, it suffice to consider the series $\sum \max(a_j,j)^{-1}$. Let $(n_k)$ and $(m_k)$ be two sequences of increasing positive integers satisfying

$$0 < \cdots < n_k < m_k < n_{k+1} < m_{k+1} < \cdots$$

such that when $n_k \leq j < m_k$ we have $a_j \geq j$ and $m_k \leq j < n_{k+1}$ we have $j > a_j$.

This implies that (using monotonicity of $a_j$)

$$\sum_{j = 1}^\infty \frac{1}{\max(a_j,j)} = \sum_{k = 1}^{\infty} \left( \sum_{j = n_k}^{m_k-1} \frac{1}{a_j} + \sum_{j = m_k}^{n_{k+1} - 1} j^{-1}\right) \geq \sum_k (1-n_k/m_k) + \ln \frac{n_{k+1}}{m_k}$$

But observing that $\ln$ is concave, we have that

$$\geq - \ln \frac{n_k}{m_k} + \ln \frac{n_{k+1}}{m_k} = \sum \ln n_{k+1} - \ln n_{k}$$

a telescoping sum. Using that $(n_k)$ is strictly increasing and integer valued, we get a contradiction.

Basically this is a modification on Abel's theorem as in David Mitra's answer. If $a_j$ and $j$ interchanges "leads" infinitely often, then $\limsup \frac{n}{n+a_n} \neq 0$, and hence $\frac{1}{n+a_n}$ cannot be convergent. Therefore for that series to converge, there exists some $M < \infty$ such that $a_l > l$ for all $l > M$. This implies than the $(a_l)^{-1}$ must also be a convergent series.

-

Let $S=\{n:n\leq a_n\}$. Then $\sum_{n=1}^\infty\frac{1}{\max(n,a_n)}=\sum_{n\in S}1/a_n+\sum_{n\in N-S}1/n$

In this question it is showed that if a subseries of a diverging sequence has indices dense in N then it diverges. But if S is not dense in N, then N-S must be dense in N, hence one of the sums must diverge.

This also seems to imply a positive answer to the Slowing down divergence 2 question.

-
Asymptotic density is not necessarily well defined. In the solution to the question you linked to, it is necessary to have a $\liminf$ (lower asymptotic density) be bounded away from zero. It is, however, possible to concoct cases where the lower asymptotic densities of both $N$ and $N-S$ be zero (see the solution to the question linked in the OP). In fact, this property is crucially used in that answer. –  Willie Wong Nov 21 '11 at 14:01