# Can every positive real be written as the sum of a subsequence of dot dot dot

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

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

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

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

-

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.

-

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

-