5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.