Prove that when writing up all even numbers in a column, then chaining $2n+1$ from them, we get all natural numbers exactly once.

Question

Here is the idea: Write up all even numbers in the first column, then get numbers in the second column by taking the number to the left ($n$), and calculating $2n+1$. And keep repeating this.

Here is how it's done: $$\begin{matrix} 0 & 1 & 3 & 7 & 15 & 31 & 63 & \dots \\ 2 & 5 & 11 & 23 & 47 & 95 & 191 & \dots \\ 4 & 9 & 19 & 39 & 79 & 159 & 319 & \dots \\ 6 & 13 & 27 & 55 & 111 & 223 & 447 & \dots \\ 8 & 17 & 35 & 71 & 143 & 287 & 575 & \dots \\ 10 & 21 & 43 & 87 & 175 & 351 & 703 & \dots \\ 12 & 25 & 51 & 103 & 207 & 415 & 831 & \dots \\ 14 & 29 & 59 & 119 & 239 & 479 & 959 & \dots \\ 16 & 33 & 67 & 135 & 271 & 543 & 1087 & \dots \\ 18 & 37 & 75 & 151 & 303 & 607 & 1215 & \dots \\ 20 & 41 & 83 & 167 & 335 & 671 & 1343 & \dots \\ 22 & 45 & 91 & 183 & 367 & 735 & 1471 & \dots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \end{matrix}$$

And this is what it looks like to only write up the first $50$ numbers gotten this way:

$$\begin{matrix} 0 & 1 & 3 & 7 & 15 & 31 & \dots\\ 2 & 5 & 11 & 23 & 47 & \dots & \\ 4 & 9 & 19 & 39 & \dots & & & \\ 6 & 13 & 27 & \dots & & & & \\ 8 & 17 & 35 & \dots & & & & \\ 10 & 21 & 43 & \dots & & & & \\ 12 & 25 & \dots & & & & & \\ 14 & 29 & \dots & & & & & \\ 16 & 33 & \dots & & & & & \\ 18 & 37 & \dots & & & & & \\ 20 & 41 & \dots & & & & & \\ 22 & 45 & \dots & & & & & \\ 24 & 49 & \dots & & & & & \\ 26 & \dots & & & & & & \\ 28 & \dots & & & & & & \\ 30 & \dots & & & & & & \\ 32 & \dots & & & & & & \\ 34 & \dots & & & & & & \\ 36 & \dots & & & & & & \\ 38 & \dots & & & & & & \\ 40 & \dots & & & & & & \\ 42 & \dots & & & & & & \\ 44 & \dots & & & & & & \\ 46 & \dots & & & & & & \\ 48 & \dots & & & & & & \\ 50 & \dots & & & & & & \\ \end{matrix}$$

Question: Do we get all natrual numbers exactly once when writing up all rows this way?

Bonus question: When writing up numbers in order, what curve do we approximate when connecting the end of each row? (What curve do we get closer and closer to by adding more numbers in order to our list?)

$\quad\quad\quad\quad\quad\quad\quad\quad$

My guess is that the red line approximates $\ln(x), x \in [0,1]$.

Answer 1

Well the first column has all even numbers, i.e., those $\equiv 0 \bmod 2$, and not those $\equiv 1 \bmod 2$

the second column has the numbers $\equiv 1\bmod 4$, and the first two columns miss out the ones $\equiv 3 \bmod 4$

Likewise the first three columns miss out only the numbers $\equiv 7 \bmod 8$

Suppose we have the integer $n$ - which column does it appear in? Well if $2^r$ is the greatest power of $2$ which divides $n+1$, then your number will appear in the $(r+1)^{th}$ column.

I've sketched out some ideas from which you might see patterns to explore, and conjectures to prove. Incidentally, your table would be more suggestive if you took it up to $31$ or $63$ and counted the numbers in the different columns.

Answer 2

First, observe that your the entry in the $m$-th row and $n$-column is given by: $m_{m,n}=(2m+1)2^n-1$ for $m,n\geq0$.

From this it is straightforward to show the mapping $(m,n)\to m_{m,n}$ is injective.

Regarding your second question:

$$ (2m+1)2^n-1\leq M\\ \Leftrightarrow n\leq\Big(\log(M+1)-\log(2m+1)\Big)/\log(2) $$

Thus, the red line is given by

$$ n=\Big\lfloor \Big(\log(M+1)-\log(2m+1)\Big)/\log(2)\Big\rfloor $$

So you were kinda right with you assumption!