MathDB

P3

Part of 2016 India National Olympiad

Problems(1)

Everything comes to 1 eventually

Source: INMO 2016 Problem 3

1/17/2016
Let N\mathbb{N} denote the set of natural numbers. Define a function T:N→NT:\mathbb{N}\rightarrow\mathbb{N} by T(2k)=kT(2k)=k and T(2k+1)=2k+2T(2k+1)=2k+2. We write T2(n)=T(T(n))T^2(n)=T(T(n)) and in general Tk(n)=Tk−1(T(n))T^k(n)=T^{k-1}(T(n)) for any k>1k>1.
(i) Show that for each n∈Nn\in\mathbb{N}, there exists kk such that Tk(n)=1T^k(n)=1.
(ii) For k∈Nk\in\mathbb{N}, let ckc_k denote the number of elements in the set {n:Tk(n)=1}\{n: T^k(n)=1\}. Prove that ck+2=ck+1+ckc_{k+2}=c_{k+1}+c_k, for k≥1k\ge 1.
number theorynumber theory proposedfunction