<s>[INST] Number of Collatz steps for Mersenne numbers I noticed that for all $k \in \mathbb{N} \geq 1$ the following is true (I tested up to $2^{5000}$):

$\text{Collatz_Steps}(2^{2k+1} - 1) + 1 = \text{Collatz_Steps}(2^{2k+2} - 1)$

Where $\text{Collatz_Steps}$ is the number of steps required to reach $1$.
Is there a proof for this?
 [/INST] Proof sketch:
For a number $2^n-1,$ the first $2n$ steps are the $3x+1$ step and the $x/2$ step in alternating order, until you reach $3^n-1.$
$3^n-1$ is even, so the next step is the $x/2$ step again. We have
$$
\frac{3^n-1}{2} = \sum_{j=0}^{n-1} 3^j
$$
which is odd if $n$ is odd and even if $n$ is even. So for odd $n,$ you get 
$$
3\,\cdot \,\frac{3^n-1}{2} +1 = \frac{3^{n+1}-1}{2}
$$
after $2n+2$ steps, while for even $n,$ you get 
$$
\frac{3^n-1}{2}
$$
after $2n+1$ steps.
For $n=2k+1,$ you get $\frac{3^{2k+2}-1}{2}$ after $2(2k+1)+2 = 4k+4$ steps.
For $n=2k+2,$ you get $\frac{3^{2k+2}-1}{2}$ after $2(2k+2)+1 = 4k+5$ steps.
</s>