A question about "binary numbers in arbitrary bases" Here's a problem that I had come up with some time ago:

Let a "binary number in base $n$" refer to a natural number whose representation in base $n$ consists of only $0$'s and $1$'s.
  Prove that every natural number can be expressed as the sum of a binary number in base $3$, a binary number in base $4$, and a binary number in base $5$.

I eventually managed to prove it (which will for the time being be left as an exercise to the reader as I seem to have deleted the only copy of it that I had). But the discoveries in that proof eventually gave rise to another question:

Given some collection of numbers $a_1, a_2, a_3, \ldots, a_n\ (a_k \ge 2)$ so that $\displaystyle \sum_{k=1}^n \frac{1}{a_k-1} \geq 1$, every natural number can be expressed as the sum of binary numbers $b_1, b_2, b_3, \ldots, b_n$ so that for all $1 \le k \le n$, $b_k$ is in base $a_k$.

Is this true? If so, can you prove it?
 A: 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$.
