# Does there exist a sequence $\{a_n\}_{n\ge1}$ with $a_n < a_{n+1}+a_{n^2}$ such that $\sum_{n=1}^{\infty}a_n$ converges?

Does there exist a sequence $\{a_n\}_{n\ge1}$ with $a_n < a_{n+1}+a_{n^2}$ such that $\sum_{n=1}^{\infty}a_n$ converges?

Does there exist a sequence with the same property but with each term positive?

-
Do you have any example sequences that even converge to 0? –  user9352 Nov 27 '12 at 1:49
@user9352 Of course. When you do not impose $a_n \ge 0$, then nearly any $a_n$ works. For example, $a_n=-\frac{1}{(n+1)^2}$. –  Ewan Delanoy Nov 27 '12 at 2:57
You can use $a_n = -\cfrac{1}{2^n}$ if you don't impose positiveness. Or the opposite of anything going to $0$ fast enough. –  xavierm02 Nov 30 '12 at 12:23
@xavierm02 But for $n=1, \ a_n \not < a_{n+1}+a_{n^2}$. Do you Know an example s.t. $a_n < a_{n+1}+a_{n^2}, \ \forall n \in \mathbb N?$ –  P.. Dec 7 '12 at 22:28
@Pambos: $a_n=-\cfrac{1}{2^{n+2}}$ If the first terms are the only ones bothering you, you can just truncate the sequence... –  xavierm02 Dec 7 '12 at 22:33

Okay, it is indeed impossible. First we find an $n>1$ such that $a_n$ is strictly positive. The basic idea of the proof is noting that if say $a_n<a_{n+1}+a_{n^2}$, then we can repeat this step to get $a_n<a_{n+2}+a_{(n+1)^2}+a_{n^2+1}+a_{n^4}$ and if we combine the two, we get $2a_n<a_{n+1}+a_{n^2}+a_{n+2}+a_{(n+1)^2}+a_{n^2+1}+a_{n^4}$ and as long as we can insure that the indices remain distinct, then we can bound our infinite sum by the right hand side and thus by an arbitrarily large multiple of $a_n$. Since $a_n$ is strictly positive, this would immediately imply divergence.

Define two functions on the positive integers, $S: m\mapsto m^2$ and $A: m\mapsto m+1$ ($S$ stands for squaring and $A$ for adding). Then recursively define the following sets: $I_0=\{n\}$ and $I_{i+1}=S(I_i)\cup A(I_i)$, i.e. $I_k$ is a $k$-fold composition of $A$s and $S$s applied to $n$. Then it follows immediately from $n>1$ that the smallest element of $I_k$ is $n+k$. I now claim that $I_k$ has $2^k$ elements. To prove it, we use induction. It's certainly true for $I_0$. If it's true for $I_{k}$, then by injectivity of $S$ and $A$, it must be the case that $S(I_{k})$ and $A(I_{k})$ both have $2^{k}$ elements. Suppose they have an element in common. Then we can write that element as a perfect square of a number that's at least $n+k$ and also either as $n+k+1$ (which is impossible - $(n+k)^2>n+k+1$ since $n+k\geq2$ by assumption) or as $u^2+i$ for some integers $u$ and $i$ with $i<k+1$ (i.e. every element of $A(I_{k})$ can be written as either $A^{k+1}(n)$ or $A^iS(x)$ for some $i<k+1$ and $x\in I_{k-i}$). In the former case, Then we find that $i$ is the difference between two squares, the largest of which is at least the square of $n+k$, so $i$ is at least $(n+k)^2-(n+k-1)^2=2(n+k)-1>k+1$, which is a contradiction. Thus $S(I_{k})$ and $A(I_{k})$ are disjoint and $I_{k+1}$ has $2^{k+1}$ elements and our inductive proof is complete.

We now obtain the inequalities $a_n=\sum_{i\in I_0}a_i<\sum_{i\in I_1}a_i<\sum_{i\in I_2}a_i<....$, the only problem is that $I_i$ and $I_j$ may not be disjoint. So define a new sequence of finite index sets $J_k$ by $J_0=I_{0}$ and if $J_k$ has largest element $r$, then we define $J_{k+1}=I_r$ whose smallest element is $n+r$ so that $s<t$ whenever $s\in J_u$ and $t\in J_v$ with $u<v$, so the $J_k$ are distinct finite index sets and they inherit the inequalities $a_n=\sum_{i\in J_0}a_i<\sum_{i\in J_1}a_i<\sum_{i\in J_2}a_i<....$. Now we note that $\sum_{i=1}^{\infty}a_i\geq\sum_{k=0}^{\infty}\sum_{i\in J_k}a_i>\sum_{k=0}^{\infty}a_n$, so the sum diverges.

-
Nice proof! Maybe the last paragraph could be simplified a little: if $\sum_{i=1}^\infty a_i$ converges, then as $k\to\infty$, $\sum_{i\in I_k}a_i\le\sum_{i=k}^\infty a_i\to 0$, a contradiction. –  23rd Nov 27 '12 at 15:02

Suppose such a positive sequence $\{a_n\}_{n \in \mathbb{N}}$ exists.

Then by repeated application of the property $a_n < a_{n+1}+a_{n^2}$ on each term appearing starting from $a_2$, gives: $a_2 < a_3 + a_4 < a_4 + a_5 + a_9 +a_{16} < \ldots$ and so on.

Let, $\{S_k\}_{k\ge 1}$ be the resulting sequence of subscripts formed by such repeated applications. So, $S_1=\{2\},S_2=\{3,4\},S_3=\{4,5,9,16\},\ldots$ and so on.

The idea is to show that these $S_k$'s have no repeating elements, so that $\sum\limits_{n=1}^{\infty} a_n$ must diverge, because any tail of the series must be greater than $a_2 > 0$.

Now, Choose the smallest $l$, where a repetition happens in $S_l$. Then the repeating element must be of the form $m^2$, for some $m \in \mathbb{N}$, which comes from $m \in S_{l-1}$ and $m^2-1 \in S_{l-1}$.

But, then $m^2-1 \in S_{l-1} \implies m^2-2 \in S_{l-2} \implies \ldots \implies m^2-2m+2 \in S_{l-2m +2}$ since, none of $m^2-1,m^2-2,\ldots,m^2-2m+2$ are perfect squares. Thus we must have $l > 2m-2$.

Also, $m \in S_{l-1} \implies m > l-1$.

Which is absurd as $m$ is greater than $2$.

(Q.E.D.)

-