A strange number base

Aaaages ago, @vingaints tweeted:

This is pretty wild. It feels like what the Basis Representation Theorem is for Integers but for Rational Numbers. Hmm - trying to prove it now. Feels like a tough one. Need to work some examples! https://t.co/tgcy8iaXHa pic.twitter.com/tgcy8iaXHa

— Ving Aints (@vingAints)
September 18, 2018

In case that’s not showing for you, it says:

Any positive rational number acn be expressed in one and only one way in the form

$a_1 + \frac{a_2}{1\cdot2} + \frac{a_3}{1\cdot 2 \cdot 3} + \dots + \frac{a_k}{1\cdot 2 \cdot 3 \dots k}$,

Where $a_1$, $a_2$, … $a_k$ are integers, and $0 \leq a_1$, $0 \leq a_2 \lt 2$, $0 \leq a_3 \lt 3$, … $0 \lt a_k \lt k$.

It’s one of those tweets where I show it to some mathematical friends and they all go ‘ooo!’. So, how would we prove such a thing?

What we need to prove

There are three things we need to prove:

  • There is at least one way to represent each number in this format
  • There is at most one way to represent each number in this format
  • This unique representation terminates

As Ving notes, we can restrict our analysis to the rationals between 0 and 1, given that $a_1$ can be any positive number.

The nugget (a lemma)

I plan to prove, by induction, that the $(n-1)$-term sequence beginning with $a_2$ can represent every rational number of the form $\frac{j}{n!}$, with $0 \leq j \lt n!$. (Note that this is slightly different from the target sequence, which requires the last term be non-zero. We’ll get to that.)

Base case: For $n=2$, we can clearly make $\frac{0}{2}$ and $\frac{1}{2}$.

Inductive step: Suppose all numbers of the form $\frac{j}{k!}$ can be made for some integer $k$ and for $0 \leq j \lt k!$. Let $0 \leq J \lt (k+1)!$. Now, $J = (k+1)j + m$, where $j = \floor{\frac{J}{k+1}}$ and $m = j \pmod{k+1}$ so that $0 \leq j \lt k!$ and $0 \leq m \lt k+1$ - each $J$ can be written uniquely in this form1.

We then have $\frac{J}{(k+1)!} = \frac{j}{k!} + \frac{m}{(k+1)!}$, and since we can make any $\frac{j}{k!}$ from a $(k-1)$-term series, we can make $\frac{J}{(k+1)!}$ from a $k$-term series.

Conclusion: Therefore, the proposition is true for $n=2$. If it is true for $n=k$, it is also true for $n=k+1$, so it is true for $n=2,3,4,…$ as required.

Corollary: How many sequences are there of the form $\{a_2, a_3, \dots a_n\}$? Each $a_i$ is a free choice of an integer such that $0 \le a_i \lt i$, of which there are $i$; therefore, there are $2 \times 3 \times 4 \times \dots n = n!$ possible sequences.

Between these $n!$ sequences, all $n!$ fractions of the form $\frac{j}{n!}$ with $0\le j \lt (n! - 1)$ can be made — so by the pigeonhole principle, each sequence corresponds to exactly one fraction.

The proof

To show (1): Any number of the form $\frac{p}{q}$, with $p$ and $q$ integers such that $0\lt p \lt q$, can be written in the form described above in exactly one way2.

Consider $\frac{(q-1)!p}{q!} = \frac{p}{q}$. According to the lemma, this can be written in precisely one way using a $(q-1)$-term sequence, possibly with trailing zeroes.

Since the sequence has at least one non-zero term, it must have a last non-zero term. Truncating the sequence at this last non-zero term gives a unique3 terminating4 representation for $\frac{p}{q}$.

$\blacksquare$


I can’t say that this is an especially practical system of numbers – although it leads5 to a straightforward proof that $e$ is irrational (since, by definition, $e = 1 + 1 + \frac{1}{2!} + \frac{1}{3!} + \dots$, its representation in this form would be ${ 2; 1, 1, 1, 1, \dots }$, which does not terminate - so it is not rational) – but I rather like it.

Does my proof have holes in? Is there a neater way? Let me know in the comments!

* Many thanks to @vingaints for patiently explaining the holes in my proof!
* Edited 2019-05-28 to fix a broken link. Thanks, Barney!

Colin

Colin is a Weymouth maths tutor, author of several Maths For Dummies books and A-level maths guides. He started Flying Colours Maths in 2008. He lives with an espresso pot and nothing to prove.

  1. Ving suggests the Euclidean algorithm to prove this; I would probably appeal to another pigeonhole argument. []
  2. The case where $p=0$ is trivial. []
  3. because the $(q-1)$-term sequence is unique []
  4. because it finishes, duh []
  5. I think – I suspect it might need a bit more work []

Share

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Sign up for the Sum Comfort newsletter and get a free e-book of mathematical quotations.

No spam ever, obviously.

Where do you teach?

I teach in my home in Abbotsbury Road, Weymouth.

It's a 15-minute walk from Weymouth station, and it's on bus routes 3, 8 and X53. On-road parking is available nearby.

On twitter