Sums of Function over Subsets of Natural Numbers

In this post we analysed sums of the form

$S_{k}(n) = 1^{k} + \cdots + n^{k}.$

We will generalise this to sums of the form

$S_{f}(n) := f(1) + \cdots + f(n)$

for suitable functions $f: \mathbb{N} \to \mathbb{N}$ .

Theorem. For $n \in \mathbb{N}$ , define $[n] := \{1, \dots, n\}$ . Suppose that $f: \mathbb{N} \to \mathbb{N}$ satisfies

$\displaystyle \sum_{j \in [n]} f(j) < 2^{n} - 1$

for some $n \in \mathbb{N}$ . Then there exist disjoint non-empty subsets $A, B \subseteq [n]$ such that

$\displaystyle \sum_{j \in A} f(j) = \sum_{j \in B} f(j)$ .

First Proof. Each non-empty subset $T \subseteq [n]$ corresponds to a sum

$\displaystyle S_{f}(T) := \sum_{j \in T} f(j) \in [S_{f}(n)]$ .

Since $S_{f}(T) \le S_{f}(n) < 2^{n} - 1$ —the total number of non-empty subsets $T \subseteq [n]$ —there must be two non-empty subsets $A, B \subseteq [n]$ with $S_{f}(A) = S_{f}(B)$ . Excluding the common elements from both sides gives the desired claim. $\square$

Second Proof. We consider expressions of the form

$S(c_{1}, \dots, c_{n}) := c_{1} f(1) + \cdots + c_{n} f(n)$ ,

where $c_{i} \in \{\pm 1\}$ for each $i$ . Then $S$ takes $2^{n}$ possible values in $[-S_{f}(n), S_{f}(n)]$ , which are all congruent modulo $2$ . Hence, the number of distinct values that $S$ takes is at most

$\displaystyle \left \lceil \frac{2 S_{f}(n) + 1}{2} \right \rceil = S_{f}(n) + 1$ .

Since this is less than $2^{n}$ , we can find $c_{j}, c_{j}' \in \{\pm 1\}$ for $j \in [n]$ such that

$\displaystyle \sum_{j=1}^{n} c_{j} f(j) = \sum_{j=1}^{n} c_{j}' f(j) \Leftrightarrow \sum_{j=1}^{n} (c_{j} - c_{j}') f(j) = 0$

with $c_{j} \neq c_{j}'$ for some $j$ .

Note that $c_{j} - c_{j}' \in \{0, \pm 2\}$ for all $j$ . Let $A = \{j: c_{j} - c_{j}' = 2\}$ and $B=\{j: c_{j} - c_{j}' = -2\}$ . Then $A$ and $B$ are non-empty and disjoint, $A \cup B \subseteq \{1, \dots, n\}$ , and