The square root of 2 is 1.41421356237… Multiply this successively by 1, by 2, by 3, and so on, writing down each result without its fractional part: 1 2 4 5 7 8 9 11 12... Beneath this, make a list of the numbers that are missing from the first sequence: 3 6 10 13 17 20 23 27 30...

The difference between the upper and lower numbers in these pairs is 2, 4, 6, 8, …

  • From Roland Sprague, Recreations in Mathematics, 1963. (via Futility Closet)

At first glance, this looks like witchcraft - but the proof is one of the nicest mathematical things I’ve seen recently, so I thought I’d share it.

Preamble

Before we go anywhere, let’s just be clear about what we’re working with, and what we’re trying to prove. With a little sleight of hand, we’re going to show that every positive integer is in exactly one of the sequences shown.

The first sequence is $\lfloor k \sqrt{2} \rfloor$, for $k = 1, 2, 3, …$.

The second is $\lfloor m \left( 2 + \sqrt{2}\right)\rfloor$, for $m = 1, 2, 3, …$.

To show that every positive integer is in exactly one of the sequences, we need to show two things: that no number is in both sequences, and that every number is in at least one sequence. The plan is to do that by contradiction: we suppose the opposite in each case, and show that it doesn’t work.

To show: no number is in both sequences

To show no number is in both sequences, we assume there is a number - call it $j$ - that is in both sequences, and show that something goes wrong.

We have that $j = \lfloor k \sqrt{2} \rfloor$ for some integer $k$, and $j = \lfloor m \left( 2 + \sqrt{2}\right)\rfloor$ for some integer $m$.

Equivalently, we have $ j \lt k\sqrt{2} \lt j+1 $ and $ j \lt m\left(2 + \sqrt{2}\right) \lt j+1 $. ((Note that the inequalities are strict, because both $\sqrt{2}$ and $2+\sqrt{2}$ are irrational.))

Divide both inequalities by the multiplier in the middle:

$ \frac{j}{\sqrt{2}} \lt k \lt \frac{j+1}{\sqrt{2}}$ and $\frac{j}{2+\sqrt{2}} \lt m \lt \frac{j+1}{2+\sqrt{2}}$.

Add these together, and we have:

$ j \left(\frac{1}{\sqrt{2}} + \frac{1}{2+\sqrt{2}}\right) \lt k + m \lt \left(j+1\right)\left(\frac{1}{\sqrt{2}} + \frac{1}{2+\sqrt{2}}\right)$.

No, wait up, it’s ok! $\frac{1}{\sqrt{2}} + \frac{1}{2+\sqrt{2}} = \frac{(2+\sqrt{2})+\sqrt{2}}{2+2\sqrt{2}} = 1$.

So, $j \lt k+m \lt j+1$ - which can’t possibly be true, because there’s no integer between $j$ and $j+1$. We’ve hit a contradiction, so our assumption - that there’s a number in both lists - is wrong; therefore, no number is in both sequence.

Aside

Oh yeah, that thing about $\frac{1}{\sqrt{2}} + \frac{1}{2+\sqrt{2}} = 1$? That’s the nugget of the proof, and what makes the whole thing work. In fact, if $a$ is irrational and $\frac{1}{a} + \frac{1}{b} = 1$, then $\lfloor ka \rfloor$ for $j=1,2,3,…$ and $\lfloor mb \rfloor$ for $m = 1,2,3,…$ form disjoint sequences - these are Beatty sequences, and can be used to win Wythoff’s game.

To show: every number is in at least one sequence

Back to the proof! The next bit is similar in flavour to the last.

To show every number is in at least one sequence, we assume there is a number - call it $j$ - that is in neither sequence, and show that something goes wrong.

For $j$ to be in neither sequence, there would need to be integers $k$ and $m$ such that:

  1. $k\sqrt{2} \lt j$

  2. $j + 1 \lt (k+1)\sqrt{2}$

  3. $m \left(2 + \sqrt{2}\right) \lt j$

  4. $j+1 \lt \left(m+1\right)\left(2+\sqrt{2}\right)$.

Similarly to before, divide each inequality by the multiplier:

  1. $k \lt \frac{j}{\sqrt{2}}$

  2. $\frac{j+1}{\sqrt{2}} \lt k+1$

  3. $m \lt \frac{j}{2+\sqrt{2}}$

  4. $\frac{j+1}{2+\sqrt{2}} \lt m+1$

Adding the first and third gives $k + m \lt j$; adding the second and fourth gives $j+1 \lt k+m+2$, or $j \lt k+m+1$. Similarly to before, there’s no integer between $k+m$ and $k+m+1$, so we have a contradiction. Therefore, every number is in at least one of the sequences.

Conclusion

Every integer is in at least one sequence; no integer is in both sequences; therefore, each number is in exactly one sequence. $\blacksquare$.

* Special thanks to @outofthenorm2, @robertjlow and @nextlevelmaths for discussions about this problem.