Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
show 4 more comments

2 Answers

up vote 15 down vote accepted
+50

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.

share|improve this answer
4  
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.