# Is it true that this function $f(n)=n^{13}$?

Assume strictly monotone increasing function; such that $$f:N^{+}\to N^{+}$$, $$h$$ for all $$n\in N^{+}$$, $$f(f(f(n)))=f(f(n))\cdot f(n)\cdot n^{2015}$$

Prove or disprove:$$f(n)=n^{13}$$

Put $$n=1,f(1)=m$$ $$f(f(m))=mf(m)$$ Put $$n=m$$, $$f(f(f(m)))=f(f(m))f(m)m^{2015}\Longrightarrow f(mf(m))=m^{2016}(f(m))^2$$ What about following?

• It seems likely to me that this is from some contest. I added the relevant tag because that will attract users who have a lot of experience with this kind of problems. Jun 3, 2015 at 7:08
• @abandon, $f(n)=n^{13}$ is a solution - just substitute and check it. We need prove that there are no other solutions? Jun 3, 2015 at 10:06
• Where is this question from? A Chinese competition? Jun 5, 2015 at 20:57
• Why people are reluctant to prove statements by assuming they're true I'll never know... Jun 7, 2015 at 0:59
• Well, the strictly increasing bit definitely matters - otherwise, we can just construct $f$ piecemeal by, at each step, choosing the smallest $n$ we've not yet defined $f(n)$ for, and defining $f(n)$ to be, say, the $n^{th}$ prime and $f(f(n))$ to be some arbitrary number factoring into only the first $n$ primes, and then use the equation for all higher iterates. Using prime factorizations, you can find that the trajectories $f^{k}(n)$ never intersect under this process, so it works indefinitely. This $f$ is probably not strictly increasing though. Jun 7, 2015 at 2:31

Let us denote by $f^{[k]}(n)$ the $k$th iterate of $f$. I cannot prove the claim, but I can prove that for all integers $n>1$ we have $$\lim_{k\to\infty}\frac{\log f^{[k+1]}(n)}{\log f^{[k]}(n)}=13.$$ This is some kind of asymptotic evidence in favor of $f(n)=n^{13}$ being the only solution - alas, anything but conclusive.

This is seen as follows. We first prove that for all $k\ge3$ we have $$f^{[k]}(n)=f^{}(n)^{A_k} f(n)^{B_k} n^{C_k}\qquad(*)$$ for the sequence of vectors of positive integer determined by the recurrence relations $$\left(\begin{array}{r} A_2\\B_2\\C_2\end{array}\right)=\left(\begin{array}{r} 1\\0\\0\end{array}\right),\qquad \left(\begin{array}{r} A_{k+1}\\B_{k+1}\\C_{k+1}\end{array}\right)=M\left(\begin{array}{r} A_k\\B_k\\C_k\end{array}\right),$$ where $M$ is the $3\times3$ matrix $$M=\left(\begin{array}{crr} 1&1&0\\1&0&1\\2015&0&0\end{array}\right).$$ The proof follows from the given functional equation of $f$ by induction on $k$. The case $k=3$ is exactly the functional equation. The inductive step follows from the induction hypothesis by substituting $f(n)$ in place of $n$ and again applying the given functional equation.

The eigenvalues of $M$ are $\lambda_1=13$ and $\lambda_{2,3}=-6+i\sqrt{119}$. The key is that of these $\lambda_1$ has the largest absolute value. Furthermore, if we write the vector $$(A_2,B_2,C_2)^T=x_1e_1+x_2e_2+x_3e_3$$ in terms of unit eigenvectors $e_1,e_2,e_3$ belonging to the respective eigenvalues, we see that $x_1\neq0$.

For any $k\ge3$ we then have $$(A_k,B_k,C_k)^T=\lambda_1^{k-2}x_1e_1+\lambda_2^{k-2}x_2e_2+\lambda_3^{k-2}x_3e_3.$$ For very large values of $k$ the first component dominates, and consequently $$\lim_{k\to\infty}\frac{A_{k+1}}{A_k}=\lim_{k\to\infty}\frac{B_{k+1}}{B_k}=\lim_{k\to\infty}\frac{C_{k+1}}{C_k}=13.$$ It takes a while to see these limits if you calculate them. For some numerical support I fired up my Mathematica. The entrywise ratios of $M^{129}$ and $M^{128}$ are all in the interval $(12.9,13.2)$.

The claim follows from this by taking logarithms from $(*)$.

I don't know if this helps. It does seem to me that we should concentrate on large values of $n$ and asymptotics first. If only we could prove that $f$ must be a homomorphism of multiplicative monoids. Then it being strictly increasing would force it to a power function, and we know the exponent. If we know that $f$ is a power function the exponent can be determined without resorting to the above asymptotic gymnastics.

• Used exponential model is not single and gives a simple proof. Jan 28, 2020 at 4:34

Re-arranging:

$h(n) = \dfrac{f(f(f(n)))}{f(f(n))\cdot f(n)} = n^{2015}$

Suppose $f(n) = n^{k}$:

$\dfrac{n^{k^3}}{n^{k^2 + k}} = n^{2015}$

$k^3 - k^2 - k - 2015 = 0$

which has solutions of $\{13, -6 \pm i \sqrt{119} \}$. The complex solutions oscillate, so $k = 13$. Clearly, $h(n)$ is unique and of the form $n^k$, and there's only one mapping from $f$ to $h$, so $f(n$) is unique.

EDIT: Regarding solutions not of the form $n^k$, define $g(n) = f(f(n))$

$f(g(n)) = g(f(n)) = g(n) \cdot f(n) \cdot n^{2015}$

We have to deal with the $n^{2015}$ term as it is of the form $n^k$. Suppose that $f(n) = \dfrac{l(n)}{n^{a}}$ and $g(n) = \dfrac{m(n)}{n^{b}}$ where $a+b = 2015$ and $l$ and $m$ are non-power series solutions by hypothesis:

$\dfrac{l\left(\dfrac{m(n)}{n^b}\right)}{n^a} = \dfrac{m(n)}{n^{b}} \cdot \dfrac{l(n)}{n^{a}} \cdot n^{2015}$

$l\left(\dfrac{m(n)}{n^b}\right) = m(n) \cdot l(n) \cdot n^{2015 - b}$

but $f(g(n)) = g(f(n))$, so

$\dfrac{m(l(n))}{n^b} = m(n) \cdot l(n) \cdot n^{2015 - b}$

$m(l(n)) = l(n) \cdot m(n) \cdot n^{2015}$

Which is what we started with. Therefore, both $f(g(n))$ and $g(f(n))$ must produce $n^{2015}$, but neither $f(n)$ nor $g(n)$ may contain $n^{\pm q}$ by hypothesis and then redundancy.

• What about solutions not in the form $n^k$?
– Teoc
Jun 8, 2015 at 22:32
• I'm afraid I'm joining in Lenin's criticisim.The part about non-monomial solutions is anything but convincing. For starters, what are the functions $l(n)$ and $m(n)$ and the parameters $a,b$. They are not uniquely determined by $f(n)$! Also, I don't see how you jumped to the conclusion that $b=2015$. Are you assuming that $f(n)$ is a polynomial or something? As much as I want to see you find a solution that's a huge gap right there. Jun 11, 2015 at 4:28
• What do you mean by "both $f(g(n))$ and $g(f(n))$ must produce $n^{2015}$"? What do you mean when you say that neither $f(n)$ nor $g(n)$ may contain $n^{\pm q}$? I honestly don't have a clue. Jun 11, 2015 at 16:52
• @user121330, I see the positive contribution of the first part of your answer: You show that among the power maps the 13th power is the unique one satisfying the functional equation. I don't understand why the complex solutions oscilate and I don't understand why this implies $k=13$. I understand that a complex exponent will yield no map from $\Bbb{N}$ to $\Bbb{N}$. From the second part of your answer I understand nothing. What are you proving? What are the assumptions? I recommend restrict yourself to the positive contributions and explain that you show uniqueness in the case of power maps.
– san
Jun 11, 2015 at 21:49
• For example, if $$f(3):=2^{13}+1,\ f(2^{13}+1)=2^{169}+1,\ f(2^{169}+1)=(2^{13}+1)(2^{169}+1)3^{2015},$$ $$f((2^{13}+1)(2^{169}+1)3^{2015})=(2^{13}+1)(2^{169}+1)3^{2015}(2^{169}+1)(2^{13}+1)^{2015},...,$$ what are the functions $l$ and $m$ an 3 or on $2^{13}+1$?
– san
Jun 12, 2015 at 0:37

No, there are many such functions. For convenience (to avoid writing $$\mathbb{N}^+$$ too much) my intervals will only consist of natural numbers, so I'll write $$[a, b]$$ to mean $$\mathbb{N}^+ \cap [a, b]$$ and $$(a, b)$$ to mean $$\mathbb{N}^+ \cap (a, b)$$ below.

Consider any $$f$$ defined as follows: first let $$f(1) = 1$$ and $$f(n) = n^{13}$$ for $$n$$ of the form $$n = 2^{13^k}$$ ($$k \geq 0$$), so clearly $$f$$ satisfies the functional equation for $$n = 1, 2^{13^k}$$. We'll now inductively define $$f$$ on $$A_k = [2^{13^k}, 2^{13^{k+1}}]$$ for each $$k \geq 0$$, so that $$f$$ is strictly increasing on $$A_k$$. Note that since we already have $$f(2^{13^k}) = 2^{13^{k+1}}$$ and $$f(2^{13^{k+1}}) = 2^{13^{k+2}}$$, $$f$$ being strictly increasing will imply $$f^{-1}(A_{k+1}) = A_k$$.

First, for $$k = 0, 1$$, let $$f|(2^{13^k}, 2^{13^{k+1}})$$ be any strictly increasing function from $$(2^{13^k}, 2^{13^{k+1}})$$ to $$(2^{13^{k+1}}, 2^{13^{k+2}})$$ (where there is at least one such function since the second set is larger than the first), so clearly $$f$$ is increasing on $$[2^{13^k}, 2^{13^{k+1}}] = A_k$$.

Now let $$k \geq 2$$. Assume we've defined $$f$$ on $$A_0, \dots, A_{k-1}$$, hence on all $$n \leq 2^{13^k}$$. We define $$f$$ on $$A_k$$ in two steps. First, to ensure that $$f$$ satisfies the functional equation, we only need to correctly set the values of $$f(f(f(n)))$$, i.e. to correctly set the values of $$f(a)$$ for $$a$$ in the image of $$f^2$$. Since our $$f$$ will satisfy $$f^{-1}(A_{i+1}) = A_i$$ for each $$i$$, the image of $$f^2$$ in $$A_k$$ will be exactly $$f(f(A_{k-2}))$$; we already know these points since we've defined $$f$$ on $$A_{k-2}$$ and $$A_{k-1}$$. Second, since the definition in the first step will actually guarantee that $$f$$ is strictly increasing on the image of $$f^2$$, to make $$f$$ strictly increasing on all of $$A_k$$ we only need check that that there's enough room to assign $$f$$-values to the remaining points.

Step 1: Defining $$f$$ on $$f(f(A_{k-2}))$$. Write $$f(f(A_{k-2})) = \{a_0, \dots, a_r\}$$ where $$a_0 < a_1 < \cdots < a_r$$, so in particular since $$f(f(2^{13^{k-2}})) = 2^{13^k}$$ and $$f(f(2^{13^{k-1}})) = 2^{13^{k+1}}$$ we have $$a_0 = 2^{13^k}$$ and $$a_r = 2^{13^{k+1}}$$. For each $$a_i$$ we have $$a_i = f(f(m_i))$$ for some $$m_i \in A_{k-2}$$, hence for $$0 < i < r$$ we define $$f(a_i) := f(f(m_i)) f(m_i) m_i^{2015} = a_i f(m_i) m_i^{2015}$$ by necessity (to satisfy the functional equation), where this already holds for $$i = 0, r$$. Note that $$m_0 < m_2 < \cdots < m_r$$ since $$f^2$$ is strictly increasing on $$A_{k-2}$$.

Step 2: Defining $$f$$ on $$A_k \setminus f(f(A_{k-2}))$$. Having now defined all $$f(a_i)$$, we define $$f$$ on each $$(a_i, a_{i+1})$$ to be any strictly increasing function $$(a_i, a_{i+1}) \to (f(a_i), f(a_{i+1}))$$. There is more than one such function since \begin{align*} f(a_{i+1}) - f(a_i) &= a_{i+1} f(m_{i+1}) m_{i+1}^{2015} - a_i f(m_i) m_i^{2015} \\ &> (a_{i+1} - a_i) f(m_i) m_i^{2015} \\ &> a_{i+1} - a_i \end{align*} which means $$|(f(a_i), f(a_{i+1}))| > |(a_i, a_{i+1})|$$. $$f$$ is now defined and strictly increasing on each $$[a_i, a_{i+1}]$$, so it's defined and strictly increasing on $$[a_0, a_r] = A_k$$.

After the induction, we've defined an $$f$$ which is strictly increasing on each $$A_k$$, hence strictly increasing on all of $$\mathbb{N}^+$$. The functional equation holds, since for any $$n \neq 1$$, we have $$n \in A_k$$ for some $$k$$, hence by our definition of $$f$$ at $$f(f(n)) \in A_{k+2}$$, $$f$$ satisfies the functional equation at $$n$$. To conclude, note that for each $$k$$ we made at least one choice (since $$|A_k| > |A_{k-2}|$$, so the set $$A_k \setminus f(f(A_{k-2}))$$ is nonempty). This means there are uncountably many (at least $$|2^{\mathbb{N}}|$$) functions $$f$$ which can be constructed this way, each of which is strictly increasing and satisfies the functional equation.

• Sadly, but these ideas does not lead to additional solutions. I've tried to obtain any solution, and my answer demonstrates that $n^{13}$ is asymptotic solution and why the infinity series of deviations can not exist. Jan 28, 2020 at 3:02
• I've looked over your solution, but it's not clear to me what you mean when you say $n^{13}$ is the "asymptotic solution", and I also don't know what you mean by the "infinity series of deviations" Jan 28, 2020 at 3:06
• The asymptotic is proved clearly, so every additional solution can be considered in the terms of deviations. Every deviation near $n$ requires monotonic correctives near $f(n),$ which can not be provided (see the tables). If $n=2,$ then $2^{13}=8192,$ but solutions of monotonity conditions are bounded with value $45.$ Jan 28, 2020 at 3:30