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

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.

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!