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.

I answered this thing Infinite sum of prime reciprocals and now wonder what happens if we do not have such a strong condition as Bertrand's postulate. i have been fiddling with this, not sure either way.

Given a sequence $a_1 > a_2 > a_3 \cdots$ of strictly decreasing positive reals such that $$ a_i \rightarrow 0 \; \; \; \mbox{but} \; \; \sum a_i = \infty, $$ can every positive real number be expressed as the sum of a subsequence of the $a_i?$ The main thing is that we are not given any upper bound on $a_n / a_{n+1}.$ For the reciprocals of the primes, we had an upper bound of $2.$

Note that this is subtler than the thing about rearranging a strictly alternating conditionally convergent series to get anything you specify. That is a matter of overshooting with positive terms, then undershooting with negative terms, back and forth. This one is a little different.

I think what I want is a careful proof of this: given two positive real numbers $B<C,$ we can find a finite subsequence of the $a_n$ with sum between $B$ and $C.$

share|improve this question
    
The upper bound won't matter. $\sum_{i\geq N} a_i = \infty$ also, so any large gap (large $a_n/a_{n+1}$) can be overcome by just accumulating some subsequence of the remaining tail. –  Eric Towers Jun 20 at 4:14
    
@Eric, I dunno. –  Will Jagy Jun 20 at 4:17
1  
Wouldn't the greedy algorithm of selecting the lowest index term that doesn't overshoot work? –  Jyrki Lahtonen Jun 20 at 4:23
    
Here is an algorithmic stab at the problem: Let $ r $ be a positive real number. Set $ S = 0 $ and $ n = 1 $. If $ S + a_{n} < r $, then redefine $ S \mapsto S + a_{n} $, redefine $ n \mapsto n + 1 $ and resume. If $ S = r $, then STOP. If $ S > r $, then redefine $ n \mapsto n + 1 $ and resume. If the algorithm does not terminate, then $ S $ is an infinite sum converging to $ r $ whose terms are a subsequence of $ (a_{n})_{n \in \mathbb{N}} $. –  Berrick Fillmore Jun 20 at 4:26
    
@JyrkiLahtonen, I thought so when I first answered the prime thing, gradually the bound given by Bertrand came to seem more and more necessary. It became a peculiar mixed strategy –  Will Jagy Jun 20 at 4:26

4 Answers 4

up vote 7 down vote accepted

Let $x$ be our target sum. Pick an $i$ such that $a_k < x/2$ for all $k \ge i$. Take elements from the sequence starting at $a_i$ until their sum is greater than $x/2$. We can't overshoot $x$ (because the terms we're looking at are less than $x/2$), and we're guaranteed to have enough elements of enough magnitude to reach $x/2$. Repeat the procedure with a target of $x-whateversumwegot$ and keep repeating to build a subsequence with a sum of $x$.

share|improve this answer
    
Good. i understand this. Just leave the greedy idea out of things. –  Will Jagy Jun 20 at 4:38

Let $x$ be the desired real number, and let $i_1$ be the smallest positive integer such that $x > a_{i_1}$ (we know such an integer exists because $a_i \to 0$). Now let $i_2$ be the smallest positive integer greater than $i_1$ such that $x - a_{i_1} > a_{i_2}$. Continuing in this way, we obtain a subsequence $(a_{i_j})_{j=1}^{\infty}$ and the sequence of partial sums $(S_k)_{k=1}^{\infty}$ is strictly increasing and is bounded above by $x$, so $S_k \to y \leq x$.

Suppose $y < x$ and set $\varepsilon = x - y$. Let $N$ be the smallest positive integer such that $a_N < \varepsilon$ and let $J$ be the largest positive integer such that $i_J < N$ (so $N \leq i_{J+1}$). As $i_{J+1}$ is the smallest positive integer greater than $i_J$ such that $x - a_{i_1} - \dots - a_{i_J} > a_{i_{J+1}}$ and $x - a_{i_1} - \dots - a_{i_J} > x - y = \varepsilon > a_N$, we must have $N = i_{J+1}$. Now note that $x - a_{i_1} - \dots - a_{i_J} - a_{i_{J+1}} > x - y = \varepsilon$, so $i_{J+2} = N+1$, and likewise $i_{J+M} = N+M-1$. But then

$$y = \lim_{k\to\infty}\sum_{j=1}^ka_{i_j} = \sum_{j=1}^Ja_{i_j} + \lim_{k\to\infty}\sum_{j=J+1}^ka_{i_j} = \sum_{j=1}^Ja_{i_j} + \lim_{k\to\infty}\sum_{i=N}^ka_i$$

which is a contradiction as the series diverges (because $\sum\limits_{i=1}^{\infty}a_i = \infty$).

share|improve this answer

I'd say certainly so. Denote $S_{n,m} = \sum_{i=n}^m a_i$. Fix $L \in \mathbb{R}_+$ the desired limit. Set $R_0 = L$. Given $R_i$ for $i \geq 0$ first pick $N_i$ the least integer with $a_{N_i} < R_i$, and $M_i$ to be the minimal integer $M_i \geq N_i$ with $S_{N_i,M_i} < R_i < S_{N_i,M_i + 1}$. Then set $R_{i+1} = R_i - S_{N_i,M_i}$. Note that $N_{i+1} > M_i$, and that $L = \sum_i S_{N_i,M_i}$. Obviously there's a bit of verification.

On a philosophical level this is very similar to the alternating case, however here we don't allow overshoot as we have culling rather than negative terms.

share|improve this answer

The key is that the conditions guarantee that, given $\varepsilon>0$, we can find a subsequence $\{b_n\}$ with $0<b_n<\varepsilon$ and $\sum b_n=\infty$.

So, given $r>0$, choose $a_{n_1},\ldots,a_{n_{k_1}}$ with $0<a_{n_j}<1/2$ and $$r-1/2\leq a_{n_1}+\cdots+a_{n_{k_1}}<r.$$

Next we choose $a_{n_k+1},\ldots,a_{n_{k_2}}$ with $0<a_{n_j}<1/3$ and $$r-1/3\leq a_{n_1}+\cdots+a_{n_{k_2}}<r$$ (maybe none are needed). Repeating this, we eventually will have $a_{n_1},\ldots,a_{n_{k_m}}$ such that $$ r-1/m<a_{n_1}+\cdots a_{n_{k_m}}<r. $$

share|improve this answer

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.