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?

  • 1
    $\begingroup$ +1, if only for the parenthetical remark! (Actually, it looks like an interesting question.) $\endgroup$ – Brian M. Scott Mar 19 '13 at 3:47
  • $\begingroup$ You can't make 4 by adding three elements chosen (with replacement) from $\{ 0, 1 \}$, and every other binary number in base 5 is bigger than 4. Did you mean to allow negative numbers in the sum? $\endgroup$ – Hurkyl Mar 19 '13 at 3:51
  • $\begingroup$ @Hurkyl 4 = 10 in base 4 + 0 in base 3 + 0 in base 5. $\endgroup$ – Joe Z. Mar 19 '13 at 3:52
  • 3
    $\begingroup$ One number per base. Perhaps that was confusing. $\endgroup$ – Joe Z. Mar 19 '13 at 3:52

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$.

  • $\begingroup$ I thought that too, but realized I had no actual proof. $\endgroup$ – Joe Z. Mar 19 '13 at 13:07
  • $\begingroup$ @JoeZeng Do you recall any specific gaps in the argument? $\endgroup$ – Erick Wong Mar 19 '13 at 17:25
  • $\begingroup$ Unfortunately not. I was thinking, what happens when there is a specific gap in the available results? Does that ever happen? If the gap was small enough, would it eventually be covered over so that there is a maximum un-representable number? $\endgroup$ – Joe Z. Mar 19 '13 at 20:23
  • $\begingroup$ @JoeZeng Let me add some details to turn this into a proof (or expose any missing pieces). $\endgroup$ – Erick Wong Mar 19 '13 at 21:54
  • $\begingroup$ Great! Accepted for that. $\endgroup$ – Joe Z. Mar 20 '13 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.