The orbit of $2^n+1$

Question

Consider the Collatz function, $$T(n)=\frac {n}{2}, \text { if $n$ is even}$$ and $$ T(n)=\frac {3n+1}{2}, \text { if $n$ is odd}$$

Observing the orbit of $2^n+1$, I came up with the following formula.

$$ T^n(2^n+1)= 3^{n/2}+1, \text { if $n$ is even}$$

$$T^n(2^n+1)= 3^{(n+1)/2}+2, \text { if $n$ is odd}$$

I came up with the formula by following the orbit.

$$2^n+1\to 3(2^{n-1})+2 \to 3(2^{n-2})+1\to 3^2(2^{n-3})+2\to 3^2(2^{n-4})+1\to...$$

For example $$T^5(2^5+1)=3^3+2=29$$ which is verified by $$33\to 50\to 25\to 38\to 19 \to 29$$ For larger $n$ this is significant, for example: $$T^{100}(2^{100}+1)= 3^{50}+1$$

$$T^{1000}(2^{1000}+1)= 3^{500}+1$$ Question:

How do we turn this into a formal proof?

Answer 1

By induction.

We have $$2^a3^b+1\to\frac{2^a3^{b+1}+4}2\to2^{a-2}3^{b+1}+1.$$

Then for even $a$, after $a/2$ steps,

$$2^a3^0+1\to2^03^{a/2}+1$$

and for odd $a$, after $(a-1)/2$ steps,

$$2^a3^0+1\to2^13^{(a-1)/2}+1\to\frac{2^13^{(a+1)/2}+4}2=2^03^{(a+1)/2}+2.$$