induction for the collatz conjecture for $n=2^k$

Question

Prove / disprove the following statements regarding the Collatz conjecture T

$(1) \forall n \in \mathbb{N} ((\exists k \in N_{0} \hspace{0.5cm} n=2^k ) \rightarrow T(n)=1)$

$(1) \forall n \in \mathbb{N} ((\exists k \in N_{0} \hspace{0.5cm} n=2^k ) \leftrightarrow T(n)=1)$

$T(n):=\begin{cases} 1 \hspace{0.5cm} if \hspace{0.5cm} n=1, \\ T(\frac{3n+1}{2})\hspace{0.5cm} if \hspace{0.5cm} n>0 \land n=1\hspace{0.1cm}\mathrm{mod}(2) \\ T(\frac{n}{2})\hspace{0.5cm} if \hspace{0.5cm} n>0 \land n=0 \hspace{0.1cm}\mathrm{mod}(2) \end{cases}$

So the second statement can be disproved very fast by taking $n=10 \neq 2^{k}$ , T(10)=T(5)=T(8)=T(4)=T(2)=T(1)

It is clear that the first one is true since $\forall k \in \mathbb{N} T(2^k) = 0\hspace{0.1cm}\mathrm{mod}(2)$ $T(n)=T(2^k)=T(2^{k-1})=...=T(2^{k-k})=T(2^{0})=T(1)$

However I think I can not write it down like this and I need formal argumentation (in the task it is written that induction over $k \in \mathbb{N_0}$ is suggested, and it should be argued why induction over $k \in \mathbb{N_0}$ is allowed)

For arguing why induction over k is allowed could I use the fact of predicate logic that $(1) \forall n \in \mathbb{N} ((\exists k \in N_{0} \hspace{0.5cm} n=2^k ) \rightarrow T(n)=1)$ equals $(1) \forall n \in \mathbb{N} \hspace{0.5cm} \forall k \in N_{0} ( n=2^k \rightarrow T(n)=1)$ ?

Answer 1

Proof by induction that $\forall k \in \mathbb{N}: T^{{(k)}}(2^k) = 1$.

• Base case, for $k=0$: $T^{(0)}(2^0) = T(1) = 1$.
• Induction hypothesis, for $k$: We suppose that $T^{{(k)}}(2^k) = 1$.
• Induction step, for $k+1$ : $T^{(k+1)}(2^{k+1}) = T^{(k)}(T(2^{k+1})) = T^{(k)}(2^k) = 1$ by induction hypothesis.

□