INMO 2016 Problem 3

Let $\mathbb{N}$ denote the set of all natural numbers. Define a function $T: \mathbb{N} \rightarrow \mathbb{N}$ by $T(2 k)=k$ and $T(2 k+1)=2 k+2$. We write $T^{2}(n)=T(T(n))$ and in general $T^{k}(n)=T^{k-1}(T(n))$ for any $k>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 $\left\{n: T^{k}(n)=1\right\}$. Prove that $c_{k+2}=c_{k+1}+c_{k}$, for $k \geq 1$.