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:


*

*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
$$

*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.

*If such a sequence existes, it must satisfy
$$
\sup\frac{a_n}{n}=\sup\frac{n}{a_n}=\infty.
$$

 A: 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. 
A: We use  Abel's (or Pringsheim's) theorem: 

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.$$
A: 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.
