Maybe I am missing something because it seems quite simple. Let $f(n)$ be the least $k$ such that $T^k(n) = 1$. We need to show that $f(n) < \infty$ for all $n$. We use strong induction. We have $f(1) = 0$ and the relations $f(2k) = 1 + f(k)$ and $f(2k + 1) = 1 + f(2k + 2) = 2 + f(k + 1)$ complete the induction. Now, $c_{k + 2}$ is the number of $n$ such that $f(n) = k + 2$. If $n = 2m$, then, we need to have $k + 2 = f(n) = 1 + f(m) \Longleftrightarrow f(m) = k + 1$ and the number of such $m$ is of course $c_{k + 1}$. Similarly, if $n = 2m - 1$, we need to have $k + 2 = f(n) = 2 + f(m) \Longleftrightarrow f(m) = k$ and the number of such $m$ is $c_k$, whence $c_{k + 2} = c_{k + 1} + c_k$ as required.

Goutham wrote: Maybe I am missing something because it seems quite simple. Let $f(n)$ be the least $k$ such that $T^k(n) = 1$. We need to show that $f(n) < \infty$ for all $n$. We use strong induction. We have $f(1) = 0$ and the relations $f(2k) = 1 + f(k)$ and $f(2k + 1) = 1 + f(2k + 2) = 2 + f(k + 1)$ complete the induction. Now, $c_{k + 2}$ is the number of $n$ such that $f(n) = k + 2$. If $n = 2m$, then, we need to have $k + 2 = f(n) = 1 + f(m) \Longleftrightarrow f(m) = k + 1$ and the number of such $m$ is of course $c_{k + 1}$. Similarly, if $n = 2m - 1$, we need to have $k + 2 = f(n) = 2 + f(m) \Longleftrightarrow f(m) = k$ and the number of such $m$ is $c_k$, whence $c_{k + 2} = c_{k + 1} + c_k$ as required. No Goutham, even I used the same reasoning and this was perhaps one of the easy questions on the paper today.

My solution was a bit different. ( the above is simpler): For first part, I showed that applying T twice strictly decreases n for n>2, and so done. For the second I did casework, but it was a long solution.

I'd like to know if my solution to 2 is correct. Basically, it runs something like this: if f^k(n)=1 has a odd solutions and b even solutions, f^k+1(n)=1 has b odd solutions and a+b even solutions.. therefore, the recursion is just 2a+3b = 2a+3b which is true.. anyone did this?

very similar to Collatz conjecture

Well for part (a) just write base $2$ representation of the number $n$. Now by definition of $T(n)$ if the last digit of $n$ has $0$, then the action of $T$ removes that $0$, if it has a $1$ then it adds one which again brings $0$, note that this way the number of digits are decreasing as we keep applying $T$........so we will reach the number $10$ after some moves, thus its easy to note such an $k$ exist....... And for part (b) the solution that Goutham suggested is the best...... Also we get that $k = 2a_n - a_o + n = a_0 + 3n$, where $n = \sum_{0 \le i \le n}{2^{a_i}}$, well and general solutions are $(a_n = \frac{k}{2} - m, n = 2m + a_0)$. Now this can be used to prove the recursion thing......(lazy to type...)

TheOneYouWant wrote: I'd like to know if my solution to 2 is correct. Basically, it runs something like this: if f^k(n)=1 has a odd solutions and b even solutions, f^k+1(n)=1 has b odd solutions and a+b even solutions.. therefore, the recursion is just 2a+3b = 2a+3b which is true.. anyone did this? I also did in the same way but also included another proof in case it went wrong

Nice one: Part 1. Consider the set $S=\{T^k(n) : k \in \mathbb{N}\}$. Now, $S$ is a subset of $\mathbb{N}$ and so by the well-ordering principle $S$ must have a least element, say $l$. Assume for the sake of contradiction that $l \not= 1$. Now, if $l$ is even then $T(l)=\frac{l}{2} < l$ and if $l$ is odd then $T(T(l))=\frac{l+1}{2} <l$ in both cases leading to a contradiction. Hence, $l=1$. Part 2. Instead of ending at $1$ let's start from $1$. Indeed, starting from $1$ either double the current number or subtract $1$ with doubling first.and then doing as we please. However, we make sure that no two $-1$s are consecutive. We prove that no two sequences lead to the same number after the same number of moves. Indeed, if they did then our construction shows that the constructed sequence is just the reverse of $(n,T(n),...,T^k(n)...)$ and since this sequence is uniquely determined we see that no two of the generated elements could be the same. Now, $c_k$ is just the number of different numbers obtained after $k$ moves. Since by our established bijection, any number obtained is of the form $\times 2, \times 2, -1,\times 2,...$ with no two $-1$'s consecutive we have the evident Fibonacci Recursion $c_{k+2}=c_{k+1}+c_k$.

For part (b), I used induction, considering separately the number of odd and even number of elements in $A_k = \{n:T^k (n) = 1\}$.

for part I used concept of binary representation of a number and as the number is kept even at all times( I mean made to be even as when it is odd a 1 is added making it even), and when divided by 2 there is a continuous shift of the binary representation towards right and at one point everything will become 1

anantmudgal09 wrote: Nice one: Part 2 Instead of ending at $1$ let's start from $1$. Indeed, starting from $1$ either double the current number or subtract $1$ with doubling first.and then doing as we please. However, we make sure that no two $-1$s are consecutive. We prove that no two sequences lead to the same number after the same number of moves. Indeed, if they did then our construction shows that the constructed sequence is just the reverse of $(n,T(n),...,T^k(n)...)$ and since this sequence is uniquely determined we see that no two of the generated elements could be the same. Now, $c_k$ is just the number of different numbers obtained after $k$ moves. Since by our established bijection, any number obtained is of the form $\times 2, \times 2, -1,\times 2,...$ with no two $-1$'s consecutive we have the evident Fibonacci Recursion $c_{k+2}=c_{k+1}+c_k$. . Nice transformation anant.

Hope Good For below one

Where can I find these type of problems freinds

Part (i): At any point of applying $T$ if $n>1$ is the "current" number then let $d= \text{no. of digits in base 2 representation of n}$ When $n$ is even, applying $T$ once reduces $d$ to $d-1$. For odd $n$ applying $T$ twice reduces $d$ to $d-1$. In any case, after applying $T$ at most twice, $d$ reduces by $1$. Hence the result follows. Part(ii): (Here a move is applying $T$ once) In the binary representation of $n$, let $d$ mean the same as above, $a:=\text{no. of consecutive 1's from left}$, $N:=\text{no. of }0's$ Observe that proving the result for odd $n$ suffices. If base 2 representation of $n$ ends with $0111...11$ with say $s$ 1's then applying $T$ s+1 times results this "chunk" to end up with single digit 1. Observe that the left part of this "chunk" remains unchanged. Also observe that $s+1$ is the position of the first 0 from right when counted from right. Suppose the zeroes occur at positions $b_1,b_2,...,b_N$ (when counted from right). Applying the above method repeatedly shows that after $b_N+N-1$ moves we are left with the chunk consisting only of 1's, namely $11...11$ with $a+1$ 1's Terminating this chunk of $a+1$ 1's takes $a+2$ moves. Thus, if $m$ is the smallest number such that $T^m(n)=1$ then, $$m=a+2+d-a+N-1=d+N+1$$This shows that $m$ is independent of $a$ We want $m=k$. By definition of $d$, $d>1$ Thus, $$N=k-d-1$$Since the first 1is fixed in binary representation of $n$ we have $d-1$ places to put $N$ 0's. Thus, $$c_k=\sum_{d=2}^{k-1}\binom{d-1}{k-d-1}=\sum_{i=1}^{k-2}\binom{i}{k-2-i}$$After using some binomial identities, we get $c_{k+2}=c_{k+1}+c_k$ $\blacksquare$

At first of all recall the definition of binary numbers . For any integer $n$ it's binary representation is some thing like $(b_1\cdots b_r)_2$ such that $ b_1\neq 0,b_i \in \{ 0,1\} ,r\ge 0$. As example$5=101_2$. We should prove the statement $\mathbf{(a)}$ by the following claims . Claim (1) $T(11\cdots 1_2)(k \text{digits})=1000\cdots 0_2(k+1\text{digits})$. Proof. Since $111\cdots1_2$ is odd by definition $T(11\cdots 1_2)(k \text{digits})=11\cdots1_2+1_2=10000\cdots 0_2(k+1 times )$. As desired!. Claim (2) $T^r(10\cdots 0_2)=1$. For some natural $r$ . Proof. $10\cdots 0_2$ is actually in form of $2^k,k\in \mathbb{N} $ . So,by induction it is obvious that $T^r(2^k)=1$ for some naturals $r$. Now our concerns is to see the last digts of binary representation of every naturals.They will either $00$ or$01$ or $10$ or $11$. observation (1) $T(b_1\cdots b_k 0_2)=(b_1\cdots b_k 0)_2$. (This is because if we multiply a natural by 2 then there appears one extra 0 at the unit place of the binary representation). observation (2) $T(b_1\cdots b_r 01)=b_1\cdots b_r10$. (This is because we are adding 1 hence the effect in binary representation is as same as add 1 with 9 in decimal representation). Then, $T^2(b_1\cdots b_r 01)=b_1\cdots b_r$. Final observation We always reach to a binary numbers having last digit as $0$ after applying the $T$ operation some finite times.(when ever number of digits in binary representation is $\ge 2$). With the observation and claims we are done!! part (b). 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 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}$.

Solution of part( b )is official solution.But first part is mine . I wrote it only as it is easy and lucid. Though @anatmudgal09 's solution is elegant. For binary representation go here .

Just think what would happen if $T(2k+1)=6k+4$ Anyone who could solve part 1 in this case

Here is a nice solution to (a)... Define the sequence \[a_{n+1} = \frac{a_n + 1}{2^{\nu_2(a_n + 1)}}\]Then observing that \[a_{n+1} = \frac{a_n + 1}{2^{\nu_2(a_n + 1)}} < \frac{a_n + 1}{2} < a_n\]kills it. The collatz conjecture is equivalent to showing that the sequence defined by \[a_{n+1} = \frac{3a_n + 1}{2^{\nu_2(3a_n + 1)}}\]is eventually \(1\) (or equivalently, eventually constant).

1st part

2nd part

the conclusion

We proceed by induction on part (b). Suppose that the following holds for some integer $k$ (and all those preceding it): 1) $c_k = c_{k-1} + c_{k-2}$. 2) There are $c_{k-2}$ even numbers in the set $S_k = \{ n | T^k(n) = 1 \}$. Base case is clear. It is clear that $T^{k+1}(n) = 1 \implies T(n) \in S_k$. Label the even numbers in $S_k$ as $a_1, a_2 \cdots a_{c_{k-1}}$. Then clearly $T(n) \in S_k$ iff $T(n) = 2p$ for $p \in S_k$ or $T(n) = a_i - 1$ for $1 \leq i \leq c_{k-1}$. Since $|S_k| = c_k$, we see that $c_{k+1} = c_k + c_{k-1}$ (the $c_k$ comes from the doubles of all elements in $S_k$ and the $c_{k-1}$ comes from the even numbers in $S_k$, as we assumed by our induction hypothesis that there are $c_{k-1}$ even numbers in $S_k$). Now all that is left to show is there are $c_k$ even numbers in $S_{k+1}$. Since $S_{k+1}$ consists exactly of the doubles of all elements in $S_k$ (total $c_k$ numbers) and $a_1 - 1, a_2 - 1, \cdots a_{c_{k-1} - 1}$ where $a_1, a_2 \cdots a_{c_{k-1}}$ were the even elements in $S_k$. Since $a_1 - 1, a_2 - 1, \cdots a_{c_{k-1}} - 1$ are all odd, there are exactly $c_k$ even numbers in $S_{k+1}$ and we are done by induction.

A different solution for part $1.$ We know that $T(n)$ is surjective meaning that $T$ maps all natural number. So we know that $T $ will always at some time will return a power of $2$ and from $T(2n)=n$ we know that it will eventually becomes $1$.

Part (i) is a simple monovariant, part (ii) can be done by visualising a graph and making a new graph assuming 1 isnt visited before.