6

My brother recently brought this problem to me, and while I found it quite interesting I cannot figure out how to solve it:

For any positive integer $n$, let $f(n)$ be defined by

$$ f(n) = \begin{cases} 3n+1 & \text{if } n \text{ is odd} \\ \frac{n}{2} & \text{if } n \text{ is even} \end{cases} $$

We say $f^1 = f$ and, inductively, $f^{k+1} = f \circ f^k$, that is, $f^k(n) = \underbrace{f(\dots (f(x))\dots )}_{k \text{ times}}$.

Show that there exists at least one positive integer $n$ such that $f^{40}(n) \gt 2013n$.

Hints are fine, so I can keep thinking about this. I've reached two conclusions. One, it would be nice if we could find some $n$ such that $f^k(n)$ alternates between being odd and being even for succesive $k$'s, because then $f^2(n) = \frac32n+\frac12$; since $(\frac32)^{20} > 2013$, this $n$ would work (I think). Two, it might be easier to prove a more general version of the statement: For every $M > 0$ and $k \in \mathbb{N}$, there exists an $n$ such that $f^k(n) \gt Mn$. Of course, I don't know if this is actually true, so this approach might not work.

Javier
  • 7,298

1 Answers1

6

Hint: Your first idea is on the right track. You want $n$ to be odd. Next, you want $f^2(n)=\frac{3n+1}{2}$ to be odd. What properties must $n$ satisfy for this to be true? Next, you want $f^4(n)=\frac{3(\frac{3n+1}{2})+1}{2}$ to be odd. What properties must $n$ satisfy for this to be true? Do you start to see a pattern?

Ivan Loh
  • 16,955