Welcome to the fourth match in this year’s Big Math-Off. Take a look at the two interesting bits of maths below, and vote for your favourite.

You can still submit pitches, and anyone can enter: instructions are in the announcement post.

Here are today’s two pitches.

Tom Edgar – Rayleigh cool pairs of sequences

Tom Edgar is a math professor at a small university in Washington State, and is currently the editor of the Mathematics Association of America’s undergraduate magazine Math Horizons. He’s @TedG on Twitter.

An Exercise. Let’s start with a really (or Rayleigh) neat exercise: pick your favorite irrational number larger than $1$ (okay, you can choose numbers that are probably irrational like $e+\pi$ or $e\cdot\pi$, but I assume you will pick $\sqrt{2},e,\pi$ or $\phi$ – just don’t pick a rational number.) Let’s call your number $x$. Then, compute the first few values in the following integer sequence.

\[ \left(\left\lfloor n\cdot x\right\rfloor\right)_{n=1}^{\infty} = \left(\left\lfloor 1\cdot x\right\rfloor,\left\lfloor 2\cdot x\right\rfloor,\left\lfloor 3\cdot x\right\rfloor,\left\lfloor 4\cdot x\right\rfloor,\ldots\right) \]

where $\left\lfloor y\right\rfloor$ is the floor function, or “round-down function,” which outputs the greatest integer less than or equal to the input $y$.

The resulting sequence forms an increasing list of integers, but some integers are missing: aha, a mystery! For instance, when we use $x=\sqrt{7}$, which is irrational since $\sqrt{p}$ is irrational for all primes $p$, we get the sequence

\[ \left(\left\lfloor n\cdot\sqrt{7}\right\rfloor\right){n=1}^{\infty} = ({\color{blue}2,5,7,10,13,15,18,21,23,26,29,31,34,37,\ldots}) \]

It looks like one or two integers are missing between each pair of consecutive entries in the list. But now, here’s the fun part! For the value $x$ you chose, compute the number $z=\frac{x}{x-1}$, which is also an irrational number larger than $1$, and construct the corresponding integer sequence for the value $z$:

\[ \left(\left\lfloor n\cdot z\right\rfloor\right){n=1}^{\infty} = \left(\left\lfloor 1\cdot z\right\rfloor,\left\lfloor 2\cdot z\right\rfloor,\left\lfloor 3\cdot z\right\rfloor,\left\lfloor 4\cdot z\right\rfloor,\ldots\right). \]

For example, when we do this with $x=\sqrt{7}$ so that $z=\frac{\sqrt{7}}{\sqrt{7}-1}$, we get the integer sequence

\[ \left(\left\lfloor n\cdot\frac{\sqrt{7}}{\sqrt{7}-1}\right\rfloor\right)_{n=1}^{\infty} = ({\color{orange}1,3,4,6,8,9,11,12,14,16,17,19,20,22,\ldots}). \]

Do you see what’s happened? Are you amazed? To make things just a bit clearer, let’s weave together the previous two integer sequences in increasing order:

\[ \color{orange}1,\color{blue} 2, \color{orange}3, 4, \color{blue}5, \color{orange}6, \color{blue}7,\color{orange} 8, 9, \color{blue}10, \color{orange} 11, 12, \color{blue}13, \color{orange}14, \color{blue}15, \color{orange}16, 17, \color{blue}18,\color{orange} 19, 20, \color{blue}21,\color{orange} 22, \color{blue}23,\color{orange} 24, \ldots \]

Every natural number appears once and only once! The choice of $x=\sqrt{7}$ is not special; this partitioning property will happen for any choice of irrational $x$ (the first linked video shows it happen for $x=\sqrt{2}$ and $x=e$). If you haven’t tried it yet, pick your favorite irrational and give it a go; you can use the commands

print([floor(n*pi) for n in [1..20]])

print([floor(n*pi/(pi-1)) for n in [1..20]])

in Sage to get the two sequences when $x=\pi$.

Beatty Sequences and Rayleigh’s Theorem. The sequences defined above, those of the form $a(n) = \left\lfloor nt\right\rfloor$ for fixed $t$, are known as Beatty sequences (due to a problem posed by Thomas Beatty in the American Mathematical Monthly in 1926). The associated theorem, stated below, is sometimes called Beatty’s theorem, but it was previously discovered by Lord Rayleigh, and as such is more appropriately known as Rayleigh’s theorem.

Theorem. Let $x>1$ be an irrational number, and let $z=\frac{x}{x-1}$. The two integer sequences $a(n)= \left\lfloor nx\right\rfloor$ and $b(n)=\left\lfloor nz\right\rfloor$ partition the natural numbers.

In other words, every natural number is either of the form $\left\lfloor nx\right\rfloor$ or $\left\lfloor \frac{mx}{x-1}\right\rfloor$, but no positive integer is of both forms; the two sequences are complementary (they may also be complimentary like those in figure 1).

Intrigued? Explore what happens when $x$ is instead a rational number larger than $1$: are some numbers missing from the lists, or are there numbers that appear in both lists?

A full proof of Rayleigh’s Theorem can be found in many places (see [2] or even Wikipedia), but we might as well include the basic building blocks for readers who want to construct a proof themselves. The key is to make sure the sequences have no integers in common (no collisions) and that every integer appears in one sequence (no whiffs).

Let $x>1$ be a fixed real number, $z=\frac{x}{x-1}$, $a(n)=\lfloor nx\rfloor$ and $b(n)=\lfloor nz\rfloor$. The first key properties to check are that $\frac{1}{x}+\frac{1}{z}=1$, and that $nx$ and $nz$ are irrational for all positive integers $n$.

No collisions.

If we suppose that $a(n)=y=b(m)$ for some natural numbers $n,m$ and $y$ (so that $y$ would be in both sequences), then we conclude

\[ y< nx< y+1 \text{ and } y<mz < y+1. \]

Dividing the first inequality by $x$ and the second inequality by $y$ and investigating the integer sum $n+m$ allows us to obtain a contradiction.

No whiffs.

If we suppose $a(n)< y$, $a(n+1)\geq y+1$, $b(m)<y$, and $b(m+1)\geq y+1$ for some integers $n,m$ and $y$ (so that $y$ would be missing in both sequences) then

\[ nx< y \hspace{.5in} y+1< (n+1)x \hspace{.5in} mz< y \hspace{.5in} y+1< (m+1)z. \]

This time, use the previous inequalities to show that $y$ (an integer) lies strictly between $n+m$ and $n+m+1$, which is impossible.

A More General Result. It seems quite strange that two sequences generated by floor functions create a set of complementary sequences. You might wonder how easy it is to formulaically or systematically generate complementary integer functions in this way; luckily, many have investigated these objects. Lambek and Moser describe how, given any increasing integer sequence $f(n)$, we can construct two sequences $a(n)$ and $b(n)$ that partition the positive integers. To do this, they define

\[ f^\downarrow(n) = \big|{m\geq 1\mid f(m)<n}\big|, \]

so that $f^\downarrow(n)$ counts the number of outputs of $f$ strictly less than $n$. Computing $f^\downarrow(n)$ can be accomplished by counting the number of outputs on the graph of $f$ lying strictly below the line $y=n$.

For instance, if we let $f(n)=2n$ (the sequence of positive even integers) graphed in figure 2, then $f^\downarrow(5)$ counts the number of dots (outputs) strictly below the red dashed line at $y=5$ so that $f^\downarrow(5) = 2$. Similarly, the diagram on the right in figure 2 shows that $f^\downarrow(10) = 4$; there are $5$ dots below the dashed line at $y=10$.

Amazingly, by the Lambek-Moser theorem, the two sequences $a(n)=f(n)+n$ and $b(n)=f^\downarrow(n)+n$ are complementary. In our example using $f(n)=2n$, we get $a(n) =3n$ and $b(n)$ consists of all the integers congruent to $1$ or $2$ modulo 3 in increasing order.

We can apply the procedure above directly to the function $f(n) = \lfloor nx\rfloor-n$ to prove Rayleigh’s Theorem. Try this more general out for yourself: find the complementary sequences guaranteed by Lambek and Moser when $f(n) = n^2$ or $f(n)=n^3$, or when $f$ is your favorite increasing integer sequence!

Concluding Remarks. Finally, one way to attempt to understand a sequence $(a(n)){n=1}^\infty$ is to study the sequence of first differences, $(a(n)-a(n-1)){n=2}^\infty$. For the Beatty sequence for $x=\sqrt{7}$ that we investigated previously, the sequence of first differences starts

\[ 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2,1,2,\ldots \]

Studying the first differences of Beatty sequences unlocks a large world of mathematical research connected to Sturmian words, Christoffel words, and Euclidean strings. The corresponding sequence when $x=\phi=\frac{\sqrt{5}+1}{2}$ has interesting connections to the Fibonacci numbers and the Beatty sequence for $\phi$ is used in the winning strategy or Wythoff’s game, a variation on Nim (for more on this game, see the wonderful video by James Grime and Katie Steckles, and a follow-up video by James Grime). These relatively unknown sequences unlock the door to many other interesting sequences related to the combinatorics on words.

PS. After recording the videos for this piece, I realized I am saying the name “Rayleigh” incorrectly – my apologies for this.

References

• Samuel Beatty, Nathan Altshiller-Court, Otto Dunkel, A. Pelletier, Frank Irwin, J. L. Riley, Philip Fitch, and D. M. Yost. Problems and Solutions: Problems for Solutions: 3173-3180. Amer. Math. Monthly, 33(3):159, 1926.
• Samuel Beatty, A. Ostrowski, J. Hyslop, and A. C. Aitken. Problems and Solutions: Solutions: 3177. Amer. Math. Monthly, 34(3):159–160, 1927.
• J. Lambek and L. Moser. Inverse and complementary sequences of natural numbers. Amer. Math. Monthly, 61:454–458, 1954.

Fusible Numbers

Christian blogs at The Aperiodical, and collects his other doings at somethingorotherwhatever.com.

This is a puzzle that I’ve always enjoyed, not for the fun of solving it, but because of the unexpectedly deep answer to the question it makes you think of next.

At the end of the video I refer to these slides and this paper by Jeff Erickson and others.

So, which bit of maths made you say “Aha!” the loudest? Vote:

 Loading ...

The poll closes at 9am BST on Sunday the 19th, when the next match starts.

If you’ve been inspired to share your own bit of maths, look at the announcement post for how to send it in. The Big Lock-Down Math-Off will keep running until we run out of pitches or we’re allowed outside again, whichever comes first.