Showing $\sum 1/a_i<2$: is my proof correct?

Question

I am attempting a problem I found in a book, the book contains mostly fairly tricky problems so I am not sure whether what I've done works or not. If not, I would appreciate a hint instead of a solution (the book has solutions at the end, which I'd rather not check for now).

Problem Let $A=\{a_0, \dots \, a_n\}\subseteq\mathbb{N}_{>0}$ such that $\sum_{i\in S} a_i$ is distinct for all $S\subseteq \{0,\dots, n\}$. Show that $\sum_A 1/a_i<2$.

Some ideas: The natural approach is to bound by $\sum_0^n 2^{-i}$. WLOG $a_{i+1}>a_i$. Note that by the pigeonhole principle, $\sum_0^{j} a_i\geqslant 2^{j+1}-1$ for all $0\leqslant j\leqslant n$. To this effect, write $a_i=2^{i}+\epsilon_i c_i$ where $c_i\geqslant 0$ and $\epsilon_i=\pm 1$ (in other words, the 'deviation' from the powers of $2$). In particular, $\epsilon_i c_i<0$ implies $\epsilon_j c_j>0$ for some $j<i$.

Let $q= \min\{i\geqslant 0:\;\epsilon_i c_i>0 \}$. Now if $\epsilon_{i+1} c_{i+1}<0$ then I think we are in luck, because we can define $p+1=\min\{i>q:\; \epsilon_i c_i\geqslant 0\}$, so that: $$c_q\geqslant c_{q+1}\dots+ c_p$$ we can then compare the $\sum_q^p 1/a_i$ to $\sum_q^p 2^{-i}:$

$$\begin{aligned}\sum_q^p \left(\frac{1}{2^{i}}-\frac{1}{a_i}\right) &=\sum_q^p \left(\frac{1}{2^{i}}-\frac{1}{2^{i}+\epsilon_i c_i}\right) \\ &=\left(\frac{1}{2^{q}}-\frac{1}{2^{q}+c_q}\right)+\sum_{q+1}^p\left(\frac{1}{2^i}-\frac{1}{2^i-c_i}\right)\\&\geqslant \left(\frac{1}{2^q}-\frac{1}{2^q+\sum_{q+1}^p c_i}\right)+\sum_{q+1}^p\left(\frac{1}{2^i}-\frac{1}{2^i-c_i}\right) \\ & = \frac{\sum_{q+1}^p c_i}{2^q(2^q+\sum_{q+1}^p c_i)}-\sum_{q+1}^p\frac{c_i}{2^i(2^i -c_i)}\\ &=\frac{1}{2^q}\sum_{q+1}^p c_i\left(\frac{1}{2^q+\sum_{q+1}^p c_i}-\frac{1}{2^{i-q}(2^i- c_i)}\right)\\ &>0\end{aligned}$$ because $2^q+\sum_{q+1}^p c_i\leqslant 2^q+c_q<2^i-c_i=2^{i-q}(2^i-c_i)$ for $q<i$ (in other words $a_q<a_i$). In theory I think if the issues below can be fixed, then each 'block' of '$\epsilon_i c_i>0$ then $\epsilon_ic_i \leqslant 0$' could be treated the same.

Issues:

• the first glaring one is that is all relies on $\epsilon_{i+1}c_{i+1}<0$, whereas in theory we could have many terms increase faster than powers of $2$ before (possibly) slowing down, and then it seems harder to compare a series of $2^i+c_i$ to a series of $2^j-c_j$.

• I think the 'leftover' from $c_q-\sum_{q+1}^p c_i$ would also need to be taken into account for terms $i>p$ etc. This also applies to the case $p=q$.

As mentioned, I would really appreciate a hint over a solution. Many thanks for reading.

[Edit: replaced $[n]$ with $\{0,\dots,n\}$ for clarity]

Answer 1

I am not sure about your proof, but I suggest a different aproach (using your idea to compare with the sum of the inverses of the powers of $2$): try to proof a stronger result, that is $$\sum_{i=0}^n \frac{1}{a_i} \le \sum_{i=0}^n \frac{1}{2^i} = 2-\frac{1}{2^{n+1}}$$ under the same hypothesis.

Assume as you did that $a_0<a_1<a_2<\cdots <a_n$.

As you said, one can easily show that $$S_j:=\sum_{i=0}^j a_i \ge \sum_{i=0}^j 2^i=2^{j+1}-1=: D_j$$ for all $0\le j\le n$.

Moreover, one has $a_i2^i<a_{i+1}2^{i+1}$ obviously.

Now, we will compute $$\sum_{i=0}^n \left(\frac{1}{2^i}-\frac{1}{a_i}\right)= \sum_{i=0}^n \frac{1}{2^ia_i}\left(a_i-2^i\right)=\sum_{i=0}^n \frac{1}{2^ia_i}\left((S_i-S_{i-1})-(D_i-D_{i-1})\right)=$$ $$= \sum_{i=0}^{n-1} \left(\frac{1}{2^ia^i}-\frac{1}{2^{i+1}a_{i+1}}\right)\left(S_i-D_i\right)+\frac{1}{2^na_n}\left(S_n-D_n\right) \ge 0$$ as $S_i-D_i\ge 0$ for all $i\ge 0$ as it is $$\left(\frac{1}{2^ia^i}-\frac{1}{2^{i+1}a_{i+1}}\right)> 0$$

Answer 2

For what it's worth, I will type out (hopefully correctly) the answer given in the book which differs from the other one posted, in case anyone would like to see more than one method!

---

Have $a_{i}<a_{i+1}$. The proof is carried out by induction on the stronger statement that if $\sum_0^k a_i\geqslant \sum_0^k b_i$ for all $k\in [n]$ where $\{b_i\}_0^n$ satisfies $0 <b_i<b_{i+1}$ then $\sum_0^n a_i^{-1}\leqslant \sum_0^n b_i^{-1}$.

The base case is trivial, suppose the assertion holds $\forall k< n$ and take $\{a_i\}^n_0$ with the distinct sum property. Then $\sum_0^k a_i\geqslant 2^{k+1}-1$ by the pigeonhole principle (this is in fact the only use of that property).

• If $\sum_0^k a_i=2^{k+1}-1$ for some $0\leqslant k<n$ then we are done since the sequence can be broken up into two of length $<n$ satisfying the condition. More precisely we would get: $$\sum_{0}^k a_i= \sum_0^k 2^i\qquad \text{and}\qquad\sum_{0}^{n-k-1} a_{i+k+1}\geqslant \sum_0^{n-k-1} 2^{i+k+1}$$ which recombine to $\sum_0^n a_i^{-1}\leqslant \sum_0^n 2^{-i}$ after the hypothesis is applied.
• Otherwise $\sum_0^k a_i>2^{k+1}-1$ for all $k<n$. The clever part is now to define the smallest deviation between both sums: $$\lambda=\min\left\{\sum_0^k a_i-2^i\;\big|\;k<n\right\}$$ One can then define a new sequence $\{a'_i\}_0^n$ where $a_i'=a_i$ for $0<i<n$, $a_0'=a_0-\lambda$ and $a_n'=a_n+\lambda$ Then $\sum_0^k a_i'\geqslant \sum_0^k 2^i$ with equality for some $k$, so by hypothesis $\sum_0^n (a_i')^{-1}\leqslant \sum_0^n 2^{-i}$. Furthermore (by convexity of $x\mapsto x^{-1}$) we have $(a_0-\lambda)^{-1}+(a_n+\lambda)^{-1}>a_0^{-1}+a_n^{-1}$ so $\sum_0^n a_i^{-1}< \sum_0^n 2^{-i}$.