Proof: The sum of any three single-digit numbers is at most two digits long

August 21, 2011

Here comes another trivial proof (the base must be at least 2 for the obvious reason):

Suppose x, y, z are single-digit numbers in base b ≥ 2. By the definition, $0\le x\le b-1$, $0\le y\le b-1$, and $0\le z\le b-1$. Thus, the sum $x+y+z$ has the property $0\le x+y+z\le b-1+b-1+b-1=3b-3$.

Case 1, $x+y+z<b$ #

In this case, the sum can be expressed in single digit.

Case 2, $b\le x+y+z\le 3b-3$ #

Let $d_1=\lfloor \frac{x+y+z}{b}\rfloor$ and $d_0=x+y+z-d_{1}b$. Then $0\le \frac{x+y+z}{b}\le 3-\frac{3}{b}$ and $0\le \lfloor \frac{x+y+z}{b}\rfloor \le 3-\lfloor \frac{3}{b}\rfloor$. Because b ≥ 2, $\lfloor \frac{3}{b}\rfloor =0$. It follows that $0\le \lfloor \frac{x+y+z}{b}\rfloor \le 3$ and $0\le d_1\le 3$.

Using the property of the ceiling function:

$$0\le x+y+z-\frac{x+y+z}{b}b\le x+y+z-\lfloor \frac{x+y+z}{b}\rfloor b$$ $$\frac{x+y+z}{b}-1<\lfloor \frac{x+y+z}{b}\rfloor$$

It follows that $\frac{x+y+z}{b}b-b<\lfloor \frac{x+y+z}{b}\rfloor b$ or that $x+y+z-b<\lfloor \frac{x+y+z}{b}\rfloor b$. Now multiply −1 to both sides to get $-(x+y+z)+b>-\lfloor \frac{x+y+z}{b}\rfloor b$ and $b>x+y+z-\lfloor \frac{x+y+z}{b}\rfloor b$. Since $x+y+z$ are integers, $x+y+z-\lfloor \frac{x+y+z}{b}\rfloor b\le b-1$. Thus, $0\le x+y+z-\lfloor \frac{x+y+z}{b}\rfloor b\le b-1$ and $0\le d_0\le b-1$.

Given the above, the sum x + y + z can be expressed as $x+y+z=d_{1}b+d_0$ where $0\le d_1\le 3$ and $0\le d_0\le b-1$. Hence $x+y+z$ can be expressed in two digits.

Thus in both cases, the sum of three numbers x, y, z can be at most two digits long. Q.E.D.

• Number Theory,
• Mathematics,
• Proof