Find all increasing functions $f$ from the nonnegative integers to the integers satisfying $f(2)=7$ and \[ f(mn) = f(m) + f(n) + f(m)f(n) \] for all nonnegative integers $m$ and $n$.
Problem
Source:
Tags: function, logarithms, integration, Taiwan
19.07.2014 01:56
Adding 1 to both sides gives $f(mn)+1=f(m)+f(n)+f(m)f(n)+1=(f(m)+1)(f(n)+1)$. Define $g(x)=f(x)+1$, thus $g(mn)=g(m)g(n)$. Note that $g(x)=x^3$ for $x\in \{0,1,2\}$. Taking logs of both sides yields $\ln g(mn)=\ln g(m)g(n)=\ln g(m)+\ln g(n)$. Define $h(x)=\log g(x)$, $\therefore h(mn)=h(m)+h(n)$. Trivial solution is $h(x)=0\ \forall x\in \mathbb{N}$, but this doesn't satisfy the condition. I know the rest is wrong, but I g2g so I might as well post it since it seems to give the right answer. Assume that $h(x)$ is differentiable $x>0$, thus differentiating wrt $x$ we obtain $nh'(mn)=h'(m)$, which for $m=1$ becomes $h'(n)=\tfrac{h'(1)}{n}$ or $h(n)=\int \tfrac{h'(1)}{n}\ dn = h'(1)\ln |n|+C$ $\implies g(n)=e^{h'(1)\ln |n|+C}=|n|^{h'(1)}e^C=n^{h'(1)}e^C$ since $n\ge 0$ by definition. Putting $n=1$ yields $g(1)=e^C$ or $1=e^C\iff C=0$. Putting $n=2$ yields $g(2)=2^{h'(1)}$ or $8=2^{h'(1)}\iff h'(1)=3$. It follows that $g(n)=n^3\ \forall n\in \mathbb{N}\implies \boxed{f(n)=n^3-1\ \forall n\in \mathbb{N}}$.
19.07.2014 12:41
Oops I seem to have left out the condition that $f$ is increasing. Sorry about that... Can a mod please edit that in? [EDIT: never mind, computer obtained] Without the increasing condition I think the solution family is just to pick a value for each $f(p)$.
16.08.2014 08:03
Let $g(x) = f(x)+1$, so we have $g(mn) = g(m)g(n)$ for all non-negative $m,n$, and $g(2) = 8$. Substitute $m = 0$ and we get $g(0) = g(0)g(n)$ which tells us that $g(0) = 0$. Letting $m = 1$ we get $g(n) = g(1)g(n)$ so $g(1) = 1$. It is also easy to see that $g(2^n) = 2^{3n}$. Since $g$ is completely multiplicative, we only have to define $g$ over the set of prime numbers. I will now show that $g(p) = p^3$ for all primes $p$. Here, we have to use that increasing condition. Let $a=g(p)$ and given a certain integer $s$, let $r$ be an integer such that suppose $2^r < p^s < 2^{r+1}$, which means $r = \lfloor s\log_2{p} \rfloor$. Because $g$ is increasing, we know that $g(2^r) = 2^{3r} < g(p)^s$ which means that \[g(p) > 2^{\frac{3r}{s}} = 2^{\frac{3(s\log_2{p} - \{ s\log_2{p} \})}{s}} = \frac{p^3}{\sqrt[s]{2^{3 \{ s\log_2{p} \}}}}\] Clearly, if we make $s$ arbitrarily large, we can get as close to $p^3$ as we want; specifically, we can get it so that $\frac{p^3}{\sqrt[s]{2^{3\{ s\log_2{p} \}}}} > p^3 - 1$ for sure, which means that $g(p) \ge p^3$. Through a similar argument, we can get an upper bound on $g(p)$ as tight as we want to $p^3$, getting $g(p) < p^3 + 1$, telling us that $g(p) \le p^3 \Rightarrow g(p) = p^3$. So now that we have defined $g(p) = p^3$ for all primes $p$, it becomes evident that $g(n) = n^3$ for all $n \in \mathbb{Z}_0^+$, which implies that $f(n) = n^3 - 1$ is the only possible solution. It is quite easy to test this: \[m^3n^3 - 1 = m^3 - 1 + n^3 - 1 + (m^3-1)(n^3-1)\] which is clearly true if you just expand it.
22.08.2016 04:55
First, we define $g(x)=f(x)+1$. After adding 1 to both sides, the statement becomes $g(mn)=g(m)g(n)$, and $m=0\implies g(0)=0$ or $g(n)=1$ for all $x$, the latter of which is a contradiction to $f$ increasing (because $g$ is increasing as well). Then, $m=1\implies g(n)=g(n)g(1)$ so take some $n$ such that $g(n)\neq 0$ (which must exist because $g$ is increasing) and we get $g(1)=1$. This, together with the condition, implies $g$ is totally multiplicative and is thus defined by its values on the primes. We will now show that $g(p)=p^3$ for all primes $p$. Assume not; first we will assume $g(p)>p^3$ and produce a contradiction. If there exist $k, p$ such that $2^k>p^n$ but yet $g(2^k)<g(p^n)$, then we contradict $f$ increasing. Because $f$ is totally multiplicative, $f(a^b)=f(a)^b$ so the second inequality becomes $g(2)^k=8^k<g(p)^n$. Taking the log base 2 of both inequalities, we want to find $n,k$ where $k>n\log_2 p, 3k<n\log_ 2 g(p)$ so it suffices to find $n,k$ where \[\log_2 p^3 <\frac{3k}{n}<\log_2 g(p).\]However, a rational $\frac{a}{b}$ must exist between these two values because the rationals are dense in the reals, and we can take $k=a, n=3b$ to finish. We can repeat the same argument with the reverse inequalities to show that $g(p)<p^3$ yields a contradiction, so we must have $g(p)=p^3$ for all primes and thus $g(x)=x^3$ for all integer $x$. Therefore, the only solution is $f(x)=x^3-1$ and we can check that this works to finish: \[\begin{aligned} f(m) + f(n) + f(m)f(n)&=m^3-1+n^3-1+(m^3-1)(n^3-1)\\ &=(mn)^3+1-m^3-n^3+m^3+n^3-2\\ &=(mn)^3-1\\ &=f(mn).\end{aligned}\]
04.05.2017 20:54
Posting as I like this idea a lot! v_Enhance wrote: Find all increasing functions $f$ from the nonnegative integers to the integers satisfying $f(2)=7$ and \[ f(mn) = f(m) + f(n) + f(m)f(n) \]for all nonnegative integers $m$ and $n$. Set $g(x)=f(x)+1$ and obtain $g(2)=8$ and $g$ is multiplicative, monotone increasing. Let $p$ be a prime and pick $x, y$ as positive integers such that $$p^x>2^y \iff \frac{y}{x} <\log_2 p \Longrightarrow g(p)^x=g(p^x) \ge g(2^y)=g(2)^y=2^{3y} \Longrightarrow g(p)>2^{3\frac{y}{x}}.$$Since rationals are dense in $\mathbb{R}$ we can take the LHS as close to $p^3$ as we want, so in fact, $g(p) \ge p^3$. A similar argument with upper bounds yields $g(p)=p^3$ thus $g(n)=n^3$ for all $n>1$. It's clear to see $g(1)=1$ and $g(0)=0$ so $g(n)=n^3$ for all $n$, consequently $f(n)=n^3-1$ for all $n$.
05.05.2017 07:41
make $g(x)=1+f(x)$, so we have $g(mn)=g(m)g(n)$
29.08.2018 06:37
Slightly different... Write $g(m) = f(m)+1$. Then we have $g(2)=8$ and $g(mn)=g(m)g(n)$. Note $g(0)=g(0)^2$ and $g(1)=g(1)^2$, and since $g(0)<g(1)$, we have $g(0)=0$ and $g(1)=1$. Now fix and $m$ and assume WLOG that $m$ is not a power of 2. Note that $$g\left(2^{\lfloor \log_2 m^k \rfloor}\right) < g(m^k) < g\left(2^{\lfloor \log_2 m^k \rfloor + 1}\right)$$Invoking multiplicity, $$g(2)^{\lfloor k\log_2 m \rfloor} < g(m)^k < g(2)^{\lfloor k\log_2 m \rfloor + 1}.$$Hence, $$g(2)^{(\lfloor k\log_2 m \rfloor)/k} < g(m) < g(2)^{(\lfloor k\log_2 m \rfloor + 1)/k}.$$It's obvious that $g(m)=g(2)^{\log_2 m}=m^3$ satisfies the inequality. Now we claim there is only one integer between the two bounds and that will finish the problem. It suffices to show that we may pick some $k$ such that $8^{(\lfloor k\log_2 m \rfloor + 1)/k} - 8^{(\lfloor k\log_2 m \rfloor)/k} < 1$. Note that $$8^{(\lfloor k\log_2 m \rfloor)/k}\left( 8^{1/k}-1\right) < m^3(8^{1/k}-1)$$Clearly, we may choose some $k$ such that $8^{1/k} \le \frac{1}{m^3}+1$, and this $k$ satisfies the required bounds. Hence, $g(m)=m^3$, and we have $f(m)=m^3-1$, and it is easy to check this satisfies the original constraints.
03.10.2020 21:33
27.10.2020 03:46
16.12.2020 20:02
This was a pretty hard problem. I did not solve it entirely myself and got quite a few hints. We claim that the only solutions are $f(x)=2^{3k}-1$ Using Simon's favorite Factoring Trick, we have: $$[f(m)+1][f(n)+1]=f(mn)+1$$Let $g=f+1$. Then $g$ is completely multiplicative. Claim:$g(2^k)=8^k$ Proof: $g(2^k)=\underbrace {g(2) \cdot g(2) \ldots \cdot g(2) }_\text {k times}=g(2)^k=2^{3k=8^k}$ Now, we bound $g$ on prime powers. Let $ g(p)=q$ for a prime $p$, and $g(p^k)=q^k$. Then notice that we have for some $a$ and $b$, $g(2^a) \le g(p^k) \le g(2^b)$ since $g$ is strictly increasing. Let us take $a= \lfloor {klog_2p} \rfloor$ and $b= \lceil {klog_2p} \rceil$. This yields $$8^{\lfloor {klog_2p} \rfloor} \le q^k \le 8^{\lceil {klog_2p} \rceil}$$Taking log base 2, $$ 3{\lfloor {klog_2p} \rfloor} \le log_2 q^k \le 3{\lceil {klog_2p} \rceil}$$and thus: $${\lfloor {klog_2p} \rfloor} \le k log_2 \sqrt[3]{q} \le {\lceil {klog_2p} \rceil}$$Using trivial but useful inequalities (basic properties of floor and ceiling function), we have that: $$ klog_2-1 \le k log_2 \sqrt[3]{q} \le klog_2p+1$$and thus, $$ log_2-1/k \le log_2 \sqrt[3]{q} \le log_2p+1/k$$Now taking $lim_{k \rightarrow \infty}$, we can conclude that $\sqrt[3]{q}=p \implies q=p^3$, as desired.
24.08.2021 18:03
The answer is $f(x)=x^3-1$, which clearly works. Now we show nothing else works. Add $1$ to both sides to get $$f(mn)+1=f(m)f(n)+f(m)+f(n)+1=(f(m)+1)(f(n)+1).$$Then define $g: \mathbb{Z}_{\geq 0} \to \mathbb{Z}$ such that $g(x)=f(x)+1$. The equation then becomes $g(mn)=g(m)g(n)$. We also have $g(2)=8$ and $g$ is strictly increasing. Now, we have to show that $g(x)=x^3$ is the only solution to this functional equation. First, putting $m=0,n=2$ gives $g(0)=8g(0)$, hence $g(0)=0$. Also, putting in $m=n=1$ gives $g(1)=1$ since $g$ is strictly increasing. Hence, for positive integers $x$, $g(x)$ is positive. Further, note that from $g(2)=2^3$ and $g(mn)=g(m)g(n)$, we find that $g(2^k)=2^{3k}$, where $k$ is a positive integer. Now suppose $g(x)>x^3$, where $x>2$, and let $g(x)=(ax)^3$ where $a>1$ is real. We can easily see that $g(x^k)=(ax)^{3k}$. Now pick some $k$ such that $a^{3k}>8$, and choose $y$ such that $2^{y-1}<x^k<2^y$. Since $g$ is strictly increasing, it follows that $$g(x^k)<g(2^y) \iff (ax)^{3k}<2^{3y},$$but we also have $(ax)^{3k}>8(x^k)^3>8(2^{y-1})^3=2^{3y}$, which is a contradiction. Similarly, if $g(x)<x^3$, letting $g(x)=(ax)^3$ for $0<x<1$ and picking $y$ such that $2^y<x^k<2^{y+1}$ and $a^k<\tfrac{1}{8}$ yields a contradiction. It follows that $g(x)=x^3$ for all nonnegative integers $x$, which is the desired result. $\blacksquare$
02.09.2021 18:09
Solution. Let $g(x) = f(x) + 1$. Then $g$ has to be increasing and satisfy $$ g(mn) = g(m)g(n). $$ Lemma (Erdős). If $g: \mathbb{N} \rightarrow \mathbb{R}$ is totally multiplicative and increasing then $g(n) = n^{\alpha}$, for some $\alpha$. Proof. Suppose that $f(2) = 2^{\alpha}$, and take $n > 2$ such that $f(n) = n^{\beta}$. Then for any $\ell \in \mathbb{N}$, we can write $$ 2^a \leq n^{\ell} \leq 2^{a + 1}, $$for $a = \lfloor \log_2(n) \ell \rfloor$. Since $f$ is increasing, evaluating the function at each of the above must still satisfy the inequality $$ \begin{aligned} 2^{\alpha a} \leq n^{\beta \ell} &\leq 2^{\alpha(a + 1)} \\ \implies \lfloor \log_2(n) \ell\rfloor \leq \frac{\beta}{\alpha} \log_2(n) \ell &\leq \lceil \log_2(n) \ell\rceil. \end{aligned} $$This implies the inequality $$ \log_2(n) \ell \left|\frac{\beta}{\alpha} - 1\right| \leq 1. $$But this has to hold for all $\ell \in \mathbb{N}$, and thus we must have $\beta = \alpha$, and we're done. Since $g(n) = n^{\alpha}$ for some $\alpha$, and $g(2) = 8 = 2^3$, we must have $g(n) = n^{3}$, and thus $f(n) = n^{3} - 1$, which clearly works.
18.09.2021 15:42
\walkthrough Answer: $f(n) \equiv n^3-1$ \begin{walk} \ii Add $1$ to both sides and factorize \ii Introduce $g(m) = f(m)+1$, notice that $g$ is thus completely multiplicative. \ii Notice that $g(m^k) = g(m)^k$ for all $m,k\in \mathbb{N}$ \ii Use the strcitly increasing condition on the fact that $g(2^{\lfloor \log_2p^k\rfloor})<g(p^k)$ \ii Show that the previous step implies $\frac{\lfloor k\log_2p\rfloor\cdot 3}{k}<\log_2g(p)$ \ii Repeat similarly for $g(p^l)<g(2^{\lceil \log_2p^l\rceil})$ \ii Notice that we would arrive with the following, which holds for all positive integers $k,l$: \[3(\log_2p-\frac{1}{k})<\frac{3\lfloor k\log_2p\rfloor}{k}<\log_2g(p)<\frac{3\lceil l\log_2p\rceil}{l}<3(\log_2p+\frac{1}{l})\]\ii Notice that by varying $k,l$, we can make $\log_2g(p)$ arbitrarily close to $\log_2p^3$, which is what we wanted. \end{walk}
19.09.2021 02:42
Let $g(x)=f(x)+1$. Then, $g(mn)=g(m)g(n)$ and $g(2)=8$. We claim that $g(x)=x^3$. Since $g$ is multiplicative, it suffices to show $g(p)=p^3$ for all primes. Suppose that $g(p)\neq p^3$. Then, $g(2^k)=8^k$ and $g(p^k)=g(p)^k$. Therefore, $2^i<p^j$ if and only if $8^i<g(p)^j$, so $i\log2<j\log p$ if and only if $i\log8<j\log(g(p))$. This is equivalent to $\frac{3i\log2}j<\log(p^3)$ if and only if $\frac{3i\log2}j<\log(g(p))$. Since $g(p)\neq p^3$, this means that $\log(g(p))\neq3\log p$. However, there exists integer $i$ and $j$ such that $\frac{3i\log2}j$ is between $\log(p^3)$ and $\log(g(p))$, which is a contradiction. Therefore, we must have $g(p)=p^3$ for all primes $p$, so $g(x)=x^3$, which satisfies the conditions. Therefore, the only function $f$ that satisfies the original equation is $\boxed{f(x)=x^3-1}$.
22.09.2021 17:19
IAmTheHazard wrote: The answer is $f(x)=x^3-1$, which clearly works. Now we show nothing else works. Add $1$ to both sides to get $$f(mn)+1=f(m)f(n)+f(m)+f(n)+1=(f(m)+1)(f(n)+1).$$Then define $g: \mathbb{Z}_{\geq 0} \to \mathbb{Z}$ such that $g(x)=f(x)+1$. The equation then becomes $g(mn)=g(m)g(n)$. We also have $g(2)=8$ and $g$ is strictly increasing. Now, we have to show that $g(x)=x^3$ is the only solution to this functional equation. First, putting $m=0,n=2$ gives $g(0)=8g(0)$, hence $g(0)=0$. Also, putting in $m=n=1$ gives $g(1)=1$ since $g$ is strictly increasing. Hence, for positive integers $x$, $g(x)$ is positive. Further, note that from $g(2)=2^3$ and $g(mn)=g(m)g(n)$, we find that $g(2^k)=2^{3k}$, where $k$ is a positive integer. Now suppose $g(x)>x^3$, where $x>2$, and let $g(x)=(ax)^3$ where $a>1$ is real. We can easily see that $g(x^k)=(ax)^{3k}$. Now pick some $k$ such that $a^{3k}>8$, and choose $y$ such that $2^{y-1}<x^k<2^y$. Since $g$ is strictly increasing, it follows that $$g(x^k)<g(2^y) \iff (ax)^{3k}<2^{3y},$$but we also have $(ax)^{3k}>8(x^k)^3>8(2^{y-1})^3=2^{3y}$, which is a contradiction. Similarly, if $g(x)<x^3$, letting $g(x)=(ax)^3$ for $0<x<1$ and picking $y$ such that $2^y<x^k<2^{y+1}$ and $a^k<\tfrac{1}{8}$ yields a contradiction. It follows that $g(x)=x^3$ for all nonnegative integers $x$, which is the desired result. $\blacksquare$ Can you actually take $g(x) = (ax)^3$? Recalling that $g$ is from Non negative integers to integers
24.10.2021 16:02
Solved with some help from TheProblemIsSolved (In particular, he told me to look at the $f(2)=3$ case). I hope this works. Start by defining a new function $g(x)=f(x)+1$ for all nonnegative integers $x$. We have, $$g(mn)=g(m)g(n)$$for all nonnegative integers $m,n$. Note that $g(x)>0 \forall x \geq 1$ I claim that $g(x)=x^3 \forall x$. Notice that $g(0)=0^3, g(1)=1^3$. Since $g$ is completely multiplicative, it suffices to prove that $g(p)=p^3$ for all primes $p$. Note that $f(p^k)=f(p)^k$ by induction. As a result, $f(2^k)=2^{3k}$ for all naturals $k$. Claim : $g(p) \geq p^3$ Proof. Note that $g(p)^k>g(2^{\lfloor k\log_{2}{p} \rfloor})=8^{\lfloor k\log_{2}{p} \rfloor}$ for all naturals $k$, that is $g(p)>8^{\frac{\lfloor k\log_{2}{p} \rfloor}{k}}$. I claim that there exists a $k$ satisfying $8^{\frac{\lfloor k\log_{2}{p} \rfloor}{k}}>p^3-1$. This rearranges to $\lfloor k\log_{2}{p} \rfloor>k\log_2{(p^3-1)^{\frac{1}{3}}}$ which is true for large enough $k$ $\square$ Claim : $g(p) \leq p^3$ Proof. FTSOC assume that $g(p) \geq p^3+1$ for some $p$. We have $g(2)^k=8^k>(p^3+1)^{\lfloor k \log_p{2} \rfloor}$ or that $8>(p^3+1)^{\frac{\lfloor k \log_p{2} \rfloor}{k}}$ for all $k$. Now I claim that I can find large enough $k$ satisyfing the reverse inequality. Indeed, we want to find a $k$ satisfying $8<(p^3+1)^{\frac{\lfloor k \log_p{2} \rfloor}{k}} \iff \log_p{2}-\frac{\{\log_p{2}\}}{k}>\log_{p^3+1}{8} \iff \log_p{2}-\log_{p^3+1}{8} > \frac{\{\log_p{2}\}}{k}$ which is true for large $k$ since the LHS is positive $\square$ The above two claims finish the problem $\blacksquare$
23.05.2022 22:44
Define $g(x) = f(x) + 1$ and we get $g(mn) = g(m)g(n)$ with $g$ strictly increasing. By induction, we have $g(m^k) = g(m)^k$ and $g(2^k) = 2^{3k}$. Take a prime $p$ and a very large $l$ (will specify later) so that $$2^{k-1} < p^l< 2^k, \; \; g(2^{k-1}) < g(p^l) < g(2^k) \iff 2^{3k-3} < g(p)^l < 2^{3k}$$For $g(p) \le p^3$, take $l \ge 7p^3 \Longrightarrow (p^3 + 1)^l > 8p^{3l} \ge 2^{3k}$ which is a contradiction. For $g(p) \ge p^3,$ note that $(p-1)^{3l} < \frac{p^{3l}}{8}$ for $l$ sufficiently large. However, $(p-1)^{3l} < \frac{p^{3l}}{8} < 2^{3k-3}$, another contradiction. Therefore, $g(p) = p^3$ and $f(x) = x^3 - 1$ as desired.
24.05.2022 01:39
hydo2332 wrote: IAmTheHazard wrote: The answer is $f(x)=x^3-1$, which clearly works. Now we show nothing else works. Add $1$ to both sides to get $$f(mn)+1=f(m)f(n)+f(m)+f(n)+1=(f(m)+1)(f(n)+1).$$Then define $g: \mathbb{Z}_{\geq 0} \to \mathbb{Z}$ such that $g(x)=f(x)+1$. The equation then becomes $g(mn)=g(m)g(n)$. We also have $g(2)=8$ and $g$ is strictly increasing. Now, we have to show that $g(x)=x^3$ is the only solution to this functional equation. First, putting $m=0,n=2$ gives $g(0)=8g(0)$, hence $g(0)=0$. Also, putting in $m=n=1$ gives $g(1)=1$ since $g$ is strictly increasing. Hence, for positive integers $x$, $g(x)$ is positive. Further, note that from $g(2)=2^3$ and $g(mn)=g(m)g(n)$, we find that $g(2^k)=2^{3k}$, where $k$ is a positive integer. Now suppose $g(x)>x^3$, where $x>2$, and let $g(x)=(ax)^3$ where $a>1$ is real. We can easily see that $g(x^k)=(ax)^{3k}$. Now pick some $k$ such that $a^{3k}>8$, and choose $y$ such that $2^{y-1}<x^k<2^y$. Since $g$ is strictly increasing, it follows that $$g(x^k)<g(2^y) \iff (ax)^{3k}<2^{3y},$$but we also have $(ax)^{3k}>8(x^k)^3>8(2^{y-1})^3=2^{3y}$, which is a contradiction. Similarly, if $g(x)<x^3$, letting $g(x)=(ax)^3$ for $0<x<1$ and picking $y$ such that $2^y<x^k<2^{y+1}$ and $a^k<\tfrac{1}{8}$ yields a contradiction. It follows that $g(x)=x^3$ for all nonnegative integers $x$, which is the desired result. $\blacksquare$ Can you actually take $g(x) = (ax)^3$? Recalling that $g$ is from Non negative integers to integers We aren't setting $g(x)=(ax)^3$ all the time. Here, $x$ is a constant, not a variable, so we're essentially finding some $x$ with $g(x)>x^3$ and defining $a=\sqrt[3]{g(x)}/x$
07.07.2022 18:20
v_Enhance wrote: Find all increasing functions $f$ from the nonnegative integers to the integers satisfying $f(2)=7$ and \[ f(mn) = f(m) + f(n) + f(m)f(n) \]for all nonnegative integers $m$ and $n$. Setting $g(x)=f(x)+1$ we see that $g$ is multiplicative. By this paper we get $g(x)=x^k.$ Note that $g(2)=2^3$ thus $g(x)=x^3.$ (this obviously works)
16.12.2023 03:26
Define $g(x)=f(x)+1$. Our equation can be rewritten as $g(mn)= g(m) \cdot g(n)$. Claim: $g(x) = x^3$. We can first quickly see that $g(0)=0$, so $g$ is always nonnegative. Assume there exists a value of $k$ such that $g(k) \ne k^3$. Then either $g(k) \leq k^3-1$ or $g(k) \ge k^3+1$. We take care of the former first; the latter is entirely analogous. Clearly there must exist a rational number $\frac ab$ such that $k^3-1 < 2^{a/b} < k^3$. Noting that $g(2)=8$ and $g$ is strictly increasing, we have \[g(k)^{3b} = g(k^{3b}) > g(2^a) = 8^a \implies g(k) > 2^{a/b},\] contradiction. ${\color{blue} \Box}$ Hence our only solution for $f$ is $\boxed{f(x) = x^3-1}$, which evidently works.
23.12.2023 18:15
24.12.2023 23:25
lol Let $g(x) = f(x) + 1$, then $g(mn) = g(m)g(n)$ also if $n^x > 2^y$ then $g(n)=g(n^x)^{\frac{1}{x}}>2^{\frac{3y}{x}}$ forcing $g(n) \geq n^3$ similarly we get $g(n) \leq n^3$. Hence we're done.
31.12.2023 17:06
The solution is $f(x) = x^3 - 1$. Define $g\colon \mathbb Z_{\ge 0} \rightarrow \mathbb{Z}$ such that $g(x) = f(x) + 1$. Note that $g$ is strictly increasing. We are also given that $g(2) = 8$. Now note that $f(mn) = f(m) + f(n) + f(m)f(n) \implies f(mn) + 1 = (f(m)+1)(f(n)+1) \implies g(mn) = g(m)g(n)$ and so, $g$ is multiplicative. We show that $g(k) = k^3$. FTSOC assume that $g(k) \neq k^3$. If $g(k) > k^3$, then $g(k) \ge k^3 + 1$. Now we have that, \begin{align*} (k^3 + 1)^n \le g(k)^n = g(k^n) &< g(2^{\left\lfloor \log_2 k^n \right\rfloor + 1})\\ &=g(2)^{\left\lfloor \log_2 k^n \right\rfloor + 1}\\ &=2^{3(\left\lfloor \log_2 k^n \right\rfloor + 1)}\\ &\le 2^{3(\log_2 k^n + 1)} .\end{align*} Now we have that $(k^3 + 1)^n < 2^{3n\log_2 k} \cdot 8 \implies (k^3 + 1) < 8^{\log_2 k}\cdot 8^{1/n} \implies k^3 + 1 < k^3 \cdot 8^{1/n} \implies 1 + \dfrac{1}{k^3} < 8^{1/n}$. Now taking the limit of $n$ to $+\infty$, we get that $1+ \dfrac{1}{k^3} \le 1$ which is a contradiction. Similarly if $g(k) < k^3$, then $g(k) \le k^3 - 1$. Now we have that, \begin{align*} (k^3 - 1)^n \ge g(k)^n = g(k^n) &> g(2^{\left\lceil \log_2 k^n \right\rceil - 1})\\ &=g(2)^{\left\lceil \log_2 k^n \right\rceil - 1}\\ &=2^{3(\left\lceil \log_2 k^n \right\rceil - 1)}\\ &\ge 2^{3(\log_2 k^n - 1)} .\end{align*} Now we have that $(k^3 - 1)^n > 2^{3n\log_2 k} \cdot \frac{1}{8} \implies (k^3 - 1) > 8^{\log_2 k}\cdot 8^{-1/n} \implies k^3 - 1 > k^3 \cdot 8^{-1/n} \implies 1 - \dfrac{1}{k^3} > 8^{-1/n}$. Now taking the limit of $n$ to $+\infty$, we get that $1- \dfrac{1}{k^3} \ge 1$ which is a contradiction. Thus combining these two, we get that $g(k) = k^3$ which further implies that $f(k) = k^3 -1$.
16.01.2024 07:17
Note that $f(n)=n^3-1$ works, we prove it's the only solution. Bash to get $f\left(2^k\right)=2^{3k}-1$ and similarly $f\left(a^n\right)=(f(a)+1)^n-1$. We analyze this last equation. Note that if $f(a)\geq a^3$, then $f\left(a^n\right)=(a^3+1)^n-1$. Choosing suitable integers $n,k$ such that \[a^3+1 > 8^{\frac nk}> a^3\]we find that $2^k>a^n$ and also \[f\left(a^n\right)\geq (a^3+1)^n-1\geq 2^{3k}-1=f(2^k)\]which contradicts $f$ being strictly increasing. We can do a similar thing for if $f(a)\leq a^3-2$, which finishes.
06.02.2024 20:52
Obviously, $f(x)=x^3-1$ is a solution and we want to prove its uniqueness. Define $g: \mathbb{Z}_{\geq 0} \to \mathbb{Z}$ such that $g(x)=f(x)+1$. The equation then becomes $g(mn)=g(m)g(n)$. We know that $g$ is strictly increasing since $f$ is strictly increasing. Now the problem is trivial by Erdos theorem. $$\mathbb{Q.E.D.}$$
11.03.2024 20:34
The answer is $f(x) = x^3 - 1$, which works. We now show this is the only solution. Let $g \equiv f + 1$. Note that $g(mn) = f(m) + f(n) + f(m)f(n) + 1 = (f(m) + 1)(f(n) + 1) = g(m)g(n)$ for all $n$. Using this identity over and over, we have $g(2^k) = 2^{3k}$ and $g(a^k) = (g(a))^k$ for all nonnegative $a, k$. Now, suppose for the sake of contradiction there exists $a$ such that $g(a) \neq a^3$. We have either $g(a) \ge a^3 + 1$ or $g(a) \le a^3 - 1$; we will show the former is impossible, and the proof for the latter will be similar. Since the rationals are dense in $\mathbb{R}$, there exists integers $a, b$ such that $a^3 + 1 > 2^{a/b} > a^3$. Then from the second inequality, we have $2^a > a^{3b}$, and also $$g(a^{3b}) \ge (a^3 + 1)^{3b} > 2^{3a} = g(2^a),$$which contradicts the fact that $g$ is strictly increasing. So $g(a) = a^3$ for all $a$, which implies that $f(a) = a^3 - 1$.
25.04.2024 18:40
Add $1$ to both sides and let $g(x)=f(x)+1.$ Thus, $g(x)g(y)=g(xy).$ Note that $g(1)=1$ and $g(2^k)=2^{3k}$ by repeatedly multiplying by $g(2),$ which is $=2^3.$ Claim : $g(x)=x^3.$ Note that this means \begin{align*} x^m < 2^n &\iff g(x)^m < 8^n \\ \log_2 x < \frac{n}{m} &\iff \log_8 g(x) < \frac{n}{m}. \end{align*}As rationals are dense in $\mathbb R,$ note that if $\log_2 x \neq \log_8 g(x)$ it would mean there is a $\frac{n}{m}$ such that $\log_2 x <\frac{n}{m}< \log_8 g(x).$ Thus, $\log_2 x = \log_8 g(x),$ so $g(x)=x^3$ and $f(x)=\boxed{x^3-1}.\blacksquare$
28.05.2024 01:59
Let $f(m)+1 = g(m).$ Then, the condition is equivalent to having $g(mn) = g(m)g(n).$ Now, we see that $g(2) = 8.$ Now, notice that, by the density of the rational numbers, since $g(x)^{m} < 8^{n}$ if and only if $x^{m} < 2^{n},$ we need to have that $g(x) = x^{a}$ for some $a.$ So, $g(x) = x^{3},$ and thus $f(x) = x^{3}-1.$
15.06.2024 19:30
Add $1$ on both sides to get $f(mn) + 1 = (f(m) + 1)(f(n) + 1)$. Then let $g(x) = f(x) + 1$ to get $g(mn) = g(m)g(n)$. Then it is well known that the solutions to $g(mn) = g(m)g(n)$(from $\mathbb R \to \mathbb R)$ are i. $g \equiv 0$, ii. $g(x) \equiv e^{h(\log |x|)}$ with $f(0) = 0$, and iii. $g(x) \equiv \textit{sign}(x) e^{h(\log |x|)}$ where $\textit{sign}(x) \in \{1,0,-1\}$. where $h$ is an additive function. However since this problem is over $\mathbb Z$ we get that $h$ is linear and thus $f(x) = x^k$ for some $k$. This is because the second and third equations are equivalent(since we're dealing with nonnegatives) and the first equation can't be true since $g(2) = 8$. Hence we have $g(2) = 2^k \implies k = 3$ so $g(x) = x^3 \implies f(x) = x^3 - 1$. (storage)
27.07.2024 22:40
$f(x)=x^3-1$ is the answer, and it is easy to check that this satisfies our equation. Let $g(n)=f(n)+1$, so we have \[g(mn)=f(mn)+1=1+f(m)+f(n)+f(m)f(n)=(f(m)+1)(f(n)+1)=g(m)g(n).\]Then, $g(2n)=g(2)g(n)=8n$, which gives $g(2^kn)=2^{3k}g(n)$. Since $g(2)=g(2)g(1)$, we get $g(1)=1$, which then gives us $g(2^k)=2^{3k}g(1)=2^{3k}$. Suppose there is some $a$ such that $g(a)\neq a^3$, so let $g(a)=a^3+c$. Suppose $c\geq 1$. Then, let $2^{k-1}\leq a^n<2^k$ for some integer $n$. Then, we would have $2^k\leq 2a^n<2^{k+1}$, giving $a^n<2^k\leq 2a^n$. Thus, singe $g$ is strictly increasing, we must have \[(a^3+c)^n=g(a)^n=g(a^n)<g(2^k)=(2^k)^3\leq (2a^n)^3,\]which then gives us \[a^3+c<8^{\frac1n}a^3.\]Clearly, when we choose $n$ to be sufficiently large, $8^{\frac1n}a^3$ becomes arbitrarily close to $a^3$, meaning this inequality is false. Now, suppose $g(a)=a^3+c$ where $c\leq -1$. Again, for some $n,$ we can bound some $2^k$ such that $\frac{a^n}{2} \leq 2^k < a^n$. Then, since $g$ is strictly increasing, we have \[\left(\frac{a^n}{2}\right)^{3} \leq (2^k)^3 = g(2^k) < g(a^n)=g(a)^n=(a^3+c)^n,\]which gives us \[\frac{a^3}{8^{\frac1n}}<a^3+c.\]Then, once we take $n$ to be sufficiently large, this inequality must be false. Therefore, we must have $g(x)=x^3$ for all $x$, giving $f(x)=x^3-1$, as desired.
20.08.2024 23:05
Firstly we should add +1 to both sides and we get $f(mn) + 1 = (f(m) + 1)(f(n) + 1)$. Let $g(x) = f(x) + 1$. Plugging in the equation we got, we have $g(mn) = g(m)g(n)$ and g is multiplicative. We have that $g(2) = f(2) + 1 = 8$. Now $g(4) = g(2)g(2) = 8^2$ and every time we multiply by g(2) $\Rightarrow$ $g(2^k) = g(2)^k = 8^k$. Also g is multiplicative, monotone increasing. Now let p be a prime and pick positive integers x and y, such that $p^x>2^y \iff \frac{y}{x} < \log_2 p$ $\Rightarrow$ $g(p)^x = g(p^x) \ge g(2^y) = g(2)^y = 2^{3y}$ $\Rightarrow$ $g(p) > 2^{3\frac{y}{x}}$. Since rationals are dense in R we can take LHS closest to $p^3$ $\Rightarrow$ $g(p) \ge p^3$. Similarly, we can get an upper bound on $g(p)$ closest to $p^3$ and we get $g(p) < p^3 + 1$, which gives us that $g(p) \le p^3 \Rightarrow g(p) = p^3$. So now we have $g(p) = p^3$ for all primes p, we get that $g(x) = x^3$ for all $x \in Z_0^+$ since g is multiplicative, from which we have that $f(x)=x^3-1$ is the only possible solution. Lastly we should check that this works and $f(m) + f(n) + f(m)f(n) = m^3-1+n^3-1+(m^3-1)(n^3-1) = (mn)^3+1-m^3-n^3+m^3+n^3-2 = (mn)^3-1 = f(mn)$, which is obviously true so we are ready.
30.09.2024 13:22
cusofay wrote: Now the problem is trivial by Erdos theorem. Could you tell me what erdos theorem is? i am unable to find anything by that name that can be applied here.
06.10.2024 05:46
Add $1$ to both sides, $f(mn)+1=(f(m)+1)(f(n)+1)$, let $g(n)=f(n)+1$, thus we get that $g(mn)=g(m)g(n)$. This function is defined on the primes. Suppose there is a prime such that $g(p)>p^3$, thus we get by taking large enough powers of $2$ and $p$ we can get a contradiction to the strictly increasing, a similar arguement works for when $g(p)<p^3$, thus we get $g(p)=p^3$ for all $p$, so we get $f(n)=n^3-1$.
09.11.2024 21:01
Define $g(x)=f(x)+1$ then the equation becomes $g(mn)=g(m)g(n)$. We get that $g(0)=g(0)g(2)$ so $g(0)=0$, $g(2)=g(1)g(2)$ so $g(1)=1$, and $g(2)=8$. Now note that $g$ is multiplicative so $g(2^n)= 8^n$. Suppose there is a prime $p$ such that $g(p) \neq p^3$ then if we take $m$, $n$ such that $2^{n-1} < p^m < 2^n$ then $8^{n-1} < g(p)^{3m}, p^{3m} < 8^n$ for all $m$, $n$ such that the first inequality is true. However if $m$ is large enough $\tfrac{g(p)^{3m}}{p^{3m}}$ will either be greater than $8$ or less than $\tfrac{1}{8}$ which contradicts $8^{n-1} < g(p)^{3m}, p^{3m} < 8^n$ so $g(p)=p^3$ for all primes $p$. Now due to multiplicativity $g(m)=m^3$ for all $m$, or $f(m)=m^3-1$ and we are finished.