Problem 1659

(i) For $n = 1$, we have $T(1) = 2$ and $T^2(1) = T(2) = 1$. Hence we may assume that $n > 1$.
Suppose $n > 1$ is even. Then $T(n) = n/2$. We observe that $(n/2) \le n - 1$ for $n > 1$.
Suppose $n > 1$ is odd so that $n \ge 3$. Then $T(n) = n + 1$ and $T^2(n) = (n + 1)/2$. Again we see that $(n + 1)/2 \le (n - 1)$ for $n \ge 3$.
Thus we see that in at most $2(n-1)$ steps $T$ sends $n$ to 1. Hence $k \le 2(n-1)$. (Here $2(n-1)$ is only a bound. In reality, less number of steps will do.)

(ii) We show that $c_n = f_{n+1}$, where $f_n$ is the $n$-th Fibonacci number.
Let $n \in \mathbb{N}$ and let $k \in \mathbb{N}$ be such that $T^k(n) = 1$. Here $n$ can be odd or even. If $n$ is even, it can be either of the form $4d + 2$ or of the form $4d$.
If $n$ is odd, then $1 = T^k(n) = T^{k-1}(n+1)$. (Observe that $k > 1$; otherwise we get $n+1 = 1$ which is impossible since $n \in \mathbb{N}$.) Here $n+1$ is even.
If $n = 4d + 2$, then again $1 = T^k(4d + 2) = T^{k-1}(2d + 1)$. Here $2d + 1 = n/2$ is odd.
Thus each solution of $T^{k-1}(m) = 1$ produces exactly one solution of $T^k(n) = 1$ and $n$ is either odd or of the form $4d + 2$.
If $n = 4d$, we see that $1 = T^k(4d) = T^{k-1}(2d) = T^{k-2}(d)$. This shows that each solution of $T^{k-2}(m) = 1$ produces exactly one solution of $T^k(n) = 1$ of the form $4d$.
Thus the number of solutions of $T^k(n) = 1$ is equal to the number of solutions of $T^{k-1}(m) = 1$ and the number of solutions of $T^{k-2}(l) = 1$ for $k > 2$. This shows that $c_k = c_{k-1} + c_{k-2}$ for $k > 2$. We also observe that 2 is the only number which goes to 1 in one step and 4 is the only number which goes to 1 in two steps. Hence $c_1 = 1$ and $c_2 = 2$. This proves that $c_n = f_{n+1}$ for all $n \in \mathbb{N}$.