f(f(n))=3n

For discussing Olympiad Level Algebra (and Inequality) problems
User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:
f(f(n))=3n

Unread post by Phlembac Adib Hasan » Sat Apr 06, 2013 7:08 pm

Find all strictly increasing functions $f: \mathbb N \to \mathbb N$ such that for all positive integer $n$, $f(f(n))=3n$.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

User avatar
SANZEED
Posts:550
Joined:Wed Dec 28, 2011 6:45 pm
Location:Mymensingh, Bangladesh

Re: f(f(n))=3n

Unread post by SANZEED » Sat Apr 06, 2013 11:53 pm

(I saw a similar problem in IMO math's functional equation tutorial that asked for the value of $f(2006)$. I have used the same procedure here.)
We claim first that,
:arrow: $f(2\cdot 3^{n})=3^{n+1}$
:arrow: $f(3^{n})=2\cdot 3^{n}$
for $n=0,1,2,....$
We use induction. For $n=0,f(1)$ can't be $1$ otherwise $3=f(f(1))=f(1)=1$ which is impossible. Thus $f(1)>1$. Again $f$ is increasing. Then $1<f(1)<f(f(1))=3\Rightarrow f(1)=2\Rightarrow f(2)=f(f(1))=3$ and the last two deductions completes the base case.
Suppose that for some $n\geq 1,f(3^{n})=2\cdot 3^{n},f(2\cdot 3^{n})=3^{n+1}$. Then,
$f(3^{n+1})=f(f(2\cdot 3^{n}))=2\cdot 3^{n+1},f(2\cdot 3^{n+1})=f(f(3^{n+1}))=3^{n+2}$. Thus our claims are proved by induction.
Now we claim that for $0\leq m\leq 3^{n},m\in \mathbb{N},f(3^{n}+m)=2\cdot 3^{n}+m$. To prove this,note that the number of $t\in \mathbb{N}$ such that $3^{n}<t<2\cdot 3^{n}$ is $3^{n}-1$. Also the number of $t'\in \mathbb{N}$ such that $f(3^{n})=2\cdot 3^{n}<t'<3^{n+1}=f(2\cdot 3^{n})$ is $3^{n}-1$. Since $f$ is increasing we must have
$f(3^{n}+m)=3^{n}+m$. Thus we also have $f(2\cdot 3^{n}+m)=f(f(3^{n}+m))=3(3^{n}+m)$ for
$0\leq m\leq 3^{n}$.
Now let $n_{(3)}=a_{1}a_{2}...a_{k}$ denote the base $3$ representation of $n$. Thus,
$n=a_{1}\cdot 3^{k-1}+a_{2}\cdot 3^{k-2}+...+a_{k}\cdot 3^{0}$. $a_{1}$ has two possible values. So we have two cases:
:idea: If $a_{1}=1$ then by our previous deductions $f(n)=2\cdot 3^{k-1}+a_{2}\cdot 3^{k-2}+...+a_{k}\cdot 3^{0}$ that is,if $n_{(3)}=1a_{2}a_{3}...a_{k}$ then $f(n)_{(3)}=2a_{2}a_{3}...a_{k}$.
:idea: If $a_{1}=2$ then by previous deductions again,
$f(n)=3^{k}+a_{2}\cdot 3^{k-1}+...+a_{k}\cdot 3^{1}+0\cdot 3^{0}$, That is,if $n_{(3)}=2a_{2}...a_{k}$ then
$f(n)_{(3)}=1a_{2}a_{3}...a_{k}0$.

Thus we have the following function as our answer:


$f(n)_{(3)}=(i)2a_{2}a_{3}...a_{k}$ if $n_{(3)}=1a_{2}a_{3}...a_{k}$
$(ii)1a_{2}a_{3}...a_{k}0$ if $n_{(3)}=2a_{2}...a_{k}$
Exhausted after typing this :!:
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$

Post Reply