A question about "binary numbers in arbitrary bases"

Solution 1:

Yes, I think this should follow easily from two very simple lemmas:

Lemma 1: If $S = ( a_1 \le a_2 \le a_3 \le \cdots)$ is a multiset of positive integers, then every natural number can be represented as a sum of distinct elements from $S$ iff for all $k\ge 0$, $$\tag{*}\sum_{i=1}^k {a_i} \ge a_{k+1}-1.$$ Equivalently: for each $m$, the elements of $S$ not exceeding $m$ sum to at least $m$.

Proof. One direction is obvious: if $\sum_{i=1}^k {a_i} < a_{k+1}-1$ for some $k$ then there is no way to represent $a_{k+1}-1$ as a sum of elements of $S$.

In the converse direction, we show by induction that if $S$ satisfies (*), then every nonnegative integer up to $\sum_{i=1}^n a_i$ can be represented as a sum of terms from $S_n := (a_1, a_2, \ldots, a_n)$. The base case $n=1$ is easy because (*) with $k=0$ implies that $a_1 = 1$.

For the induction step, suppose $S_n$ represents every number up to $M$ where $M \ge a_{n+1}-1$. Then it's easy to see that $S_{n+1}$ represents every $0 \le x \le M+a_{n+1}$: if $0 \le x \le M$ this is obvious, while if $x \ge M+1 \ge a_{n+1}$, then $x-a_{n+1}$ is a nonnegative integer not exceeding $M$, which can be represented by $S_n$. Now just add $a_{n+1}$.

This proves the first equivalence. We now observe that (*) is equivalent to the statement that $\sum_{x \in S, x \le m} x \ge m$ for each $m$. If (*) holds then for any $m \in \mathbb N$, let $k$ be the largest integer such that $a_k \le m$. Then the sum of all elements up to $m$ is precisely $\sum_{i=1}^k a_k \ge a_{k+1} - 1 > m-1$, making it at least $m$.

In the other direction, (*) is vacuously true whenever $a_k = a_{k+1}$, so assume that $a_k < a_{k+1}$. Now choose $m=a_{k+1}-1 \ge a_k$, and apply the property that all elements up to $m$ sum to at least $m$.

Lemma 2: Let $b \ge 2$ and $n \in \mathbb N$. The sum of all $b^i$ not exceeding $n$ is at least $\frac{n}{b-1}$.

Proof. This one is very easy. If $r$ is the largest integer such that $b^r \le n$, then $n < b^{r+1}$, hence $n \le b^{r+1}-1 = (b-1)(1 + b + \cdots + b^r)$.

Finally, combining these two lemmas gives the claim in the question: let $S$ be the multiset of all nonnegative powers of all $a_k$. For each $m \in \mathbb N$, the sum of all elements of $S$ up to $m$ is at least $\sum_k \frac{m}{a_k-1} \ge m$.