Question 70
Let $\mathbb{N}$ denote the set of all natural numbers. Define a function $T: \mathbb{N} \to \mathbb{N}$ by $T(2k) = k$ and $T(2k + 1) = 2k + 2$. We write $T^2(n) = T(T(n))$ and in general $T^k(n) = T^{k-1}(T(n))$ for any $k \gt 1$.
(i) Show that for each $n \in \mathbb{N}$, there exists $k$ such that $T^k(n) = 1$.
(ii) For $k \in \mathbb{N}$, let $c_k$ denote the number of elements in the set $\{n : T^k(n) = 1\}$. Prove that $c_{k+2} = c_{k+1} + c_k$, for $k \ge 1$.
(i) Show that for each $n \in \mathbb{N}$, there exists $k$ such that $T^k(n) = 1$.
(ii) For $k \in \mathbb{N}$, let $c_k$ denote the number of elements in the set $\{n : T^k(n) = 1\}$. Prove that $c_{k+2} = c_{k+1} + c_k$, for $k \ge 1$.