Generating Functions Are the Chillest Part I
Question: Given any set \(A= \{a_1,...,a_n \} \) of integers such that no two subsets have equal sum, what is the maximum possible value of \( \sum_{i=1}^n \frac{1}{a_i} \)?
Answer: 2. Actually, it’s strictly less than 2.
The brilliant part is the first step, encapsulating our assumption on \( A\) in a generating function. Let \(0 < x < 1\) and note that:
\[ \prod_{i=1}^n (1 + x^{a_i}) < \sum_{n=0}^\infty x^n = \frac{1}{1-x}. \]
Thus taking logarithms and dividing by \( x\) (because both are monotonic and respects the inequality) we see:
\[ -\sum_{i=1}^n \sum_{n=1}^\infty \frac{(-1)^n x^{a_i n-1}}{n} = \sum_{i=1}^n \frac{\log(1+x^{a_i})}{x} < - \frac{\log(1-x)}{x} = \sum_{i=1}^\infty \frac{x^{n-1}}{n} .\]
Now, this looks ugly, but we integrate both sides, because the integral of the right hand side is actually something nice. Well, provided you put the integral inside the sum first, but this is legal thanks to the MCT. We find:
\[- \sum_{i=1}^n \sum_{n=1}^\infty \int_0^1 \frac{(-1)^n x^{a_i n}}{nx} dx < \sum_{i=1}^\infty \int_0^1 \frac{x^{n-1}}{n} dx ,\]
and so (changing \( x^{a_i} = y\) and \(a_i x^{a_i-1} dx = dy\)):
\[- \sum_{i=1}^n \sum_{n=0}^\infty \int_0^1 \frac{(-1)^n y^{ n} }{n y a_i} dy < \sum_{i=1}^\infty \frac{1}{n^2} = \frac{ \pi^2}{6},\]
\[- \sum_{i=1}^n \frac{1}{a_i} \left(\sum_{n=0}^\infty \frac{1 }{(2n)^2} - \sum_{n=0}^\infty \frac{1 }{(2n+1)^2} \right) < \frac{\pi^2}{6} ,\]
\[- \sum_{i=1}^n \frac{1}{a_i} \left(\frac{\pi^2}{24} - \frac{\pi^2}{8} \right) < \frac{\pi^2}{6} ,\]
\[ \sum_{i=1}^n \frac{1}{a_i} < 2 . \blacksquare \]