f(2) = 7, find all integer functions [Taiwan 2014 Quizzes]

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6877 posts

#1 h Jul 18, 2014, 7:37 PM • 12 Y

Y by son7, kirillnaval, mathematicsy, megarnie, Anshul_singh, HamstPan38825, Jufri, itslumi, Adventure10, Sedro, MS_asdfgzxcvb, and 1 other user

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$ .

This post has been edited 1 time. Last edited by v_Enhance, Jul 19, 2014, 7:37 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cobbler

2180 posts

cobbler

#2 h Jul 18, 2014, 10:56 PM • 9 Y

Y by son7, Adventure10, Mango247, MS_asdfgzxcvb, and 5 other users

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}}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6877 posts

v_Enhance

#3 h Jul 19, 2014, 9:41 AM • 4 Y

Y by HamstPan38825, mathematicsy, Adventure10, Assassino9931

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)$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

fclvbfm934

759 posts

fclvbfm934

#4 h Aug 16, 2014, 5:03 AM • 8 Y

Y by kprepaf, Kezer, JasperL, sa2001, missgirl, EulersTurban, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

droid347

2679 posts

droid347

#5 h Aug 22, 2016, 1:55 AM • 5 Y

Y by Generic_Username, Kezer, Korgsberg, sa2001, Adventure10

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}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

anantmudgal09

1980 posts

anantmudgal09

#6 h May 4, 2017, 5:54 PM • 9 Y

Y by Wizard_32, Kalpa, sa2001, kirillnaval, hakN, Beginner2004, Adventure10, Mango247, parola

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

zhcosin

11 posts

zhcosin

#7 h May 5, 2017, 4:41 AM • 2 Y

Y by Adventure10, Mango247

make $g(x)=1+f(x)$ , so we have $g(mn)=g(m)g(n)$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

winnertakeover

1179 posts

winnertakeover

#8 h Aug 29, 2018, 3:37 AM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Grizzy

920 posts

Grizzy

#9 h Oct 3, 2020, 6:33 PM • 3 Y

Y by DrYouKnowWho, centslordm, Mango247

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

brianzjk

1201 posts

brianzjk

#10 h Oct 27, 2020, 12:46 AM • 1 Y

Y by centslordm

incorrect solution

This post has been edited 1 time. Last edited by brianzjk, Nov 6, 2020, 1:58 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

justin1228

301 posts

justin1228

#11 h Dec 16, 2020, 5:02 PM • 2 Y

Y by kirillnaval, endless_abyss

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

IAmTheHazard

5003 posts

IAmTheHazard

#12 h Aug 24, 2021, 3:03 PM • 1 Y

Y by centslordm

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$

This post has been edited 1 time. Last edited by IAmTheHazard, Aug 24, 2021, 3:10 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

circlethm

98 posts

circlethm

#13 h Sep 2, 2021, 3:09 PM

Y by

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.

This post has been edited 1 time. Last edited by circlethm, Sep 2, 2021, 3:12 PM
Reason: Equality is possible

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

DrYouKnowWho

184 posts

DrYouKnowWho

#14 h Sep 18, 2021, 12:42 PM

Y by

\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}

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

DottedCaculator

7357 posts

DottedCaculator

#15 h Sep 18, 2021, 11:42 PM • 1 Y

Y by centslordm

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}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mr.Sharkman

501 posts

Mr.Sharkman

#48 h May 27, 2024, 10:59 PM

Y by

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.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dolphinday

1328 posts

dolphinday

#49 h Jun 15, 2024, 4:30 PM

Y by

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)

This post has been edited 1 time. Last edited by dolphinday, Jun 15, 2024, 4:30 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Jndd

1417 posts

Jndd

#50 h Jul 27, 2024, 7:40 PM • 1 Y

Y by OronSH

$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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Markas

150 posts

Markas

#51 h Aug 20, 2024, 8:05 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

kotmhn

60 posts

kotmhn

#52 h Sep 30, 2024, 10:22 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

N3bula

288 posts

N3bula

#53 h Oct 6, 2024, 2:46 AM

Y by

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bjump

1033 posts

bjump

#54 h Nov 9, 2024, 6:01 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Ilikeminecraft

658 posts

Ilikeminecraft

#55 h Jan 26, 2025, 7:24 PM

Y by

Take $n = 1, n = 0,$ to get $f(1) = 0, f(0) = -1.$ Let $f(x) = g(x) - 1.$ This gives $g(mn) = g(m)g(n),$ and $g(0) = 0, g(1) = 1, g(2) = 8.$

By induction, $f(2^k) = 2^{3k}.$ By the strictly increasing condition, $x^m \leq 2^n\iff g(x)^m \leq 2^{3n}.$ Let $h(x) = \ln g(x).$ Then, $m \ln x < \ln 2$ if and only if $mh(x) < 3n \ln 2.$ Thus, $\ln x < \frac nm \ln 2\iff h(x) < 3 \frac nm \ln 2.$ Since rationals are dense in the reals and this is an iff statement, we require $h(x) = 3\ln x\implies g(x) = x^3\implies f(x) = x^3 - 1.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

eg4334

636 posts

eg4334

#56 h Mar 5, 2025, 2:29 AM

Y by

Let $g(x)=f(x)+1$ , which translates into $g(mn)=g(m)g(n)$ . We have $g(2)=8$ and clearly $g(1)=1$ and $g(0)=0$ from the strictly increasing condition. Now the multiplicity translates to $g(2^n)=8^n$ . The key claim is that $g(p)=p^3$ . We assume FTSOC that there exists a prime $p$ where this is not true. Now the two inequalities must be equivalent: $2^a > p^b$ and $f(2^a) > f(p^b) \implies 8^a > g(p)^b$ . Now we have $\frac{a}{b} > \frac{\log{p}}{\log{2}}, \frac{a}{b} > \frac{\log{g(p)}}{\log{8}}$ . This gives a contradiction by choosing a sufficient $a, b$ by density of rational numbers. Hence by multiplicity $g(x)=x^3$ and $f(x) = \boxed{x^3-1}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Marcus_Zhang

980 posts

Marcus_Zhang

#57 h Mar 14, 2025, 8:20 PM

Y by

Attempt 2.

@below: Thanks for pointing that out. Fixed.

This post has been edited 3 times. Last edited by Marcus_Zhang, Mar 15, 2025, 3:06 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Burmf

32 posts

Burmf

#58 h Mar 14, 2025, 10:40 PM

Y by

Marcus_Zhang wrote:

Let $a = e^x$ and $b = e^y$ . Notice that we now have $g(e^{x+y}) = g(e^{x})g(e^{y})$ . Writing $h(x) = g(e^{x})$ we find that $h(x+y) = h(x) + h(y)$ .

Since $a$ and $b$ are positive integers, the function $h$ is neither continous nor it is like $Q$ or $Z$ . So you can't assume that $h$ is linear. One simple counterexample is $g(p) = 1$ for $p > 2$ primes and $g(2) = 8$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Maximilian113

575 posts

Maximilian113

#59 h Mar 17, 2025, 10:55 PM

Y by

Let $g(x)=f(x)+1,$ therefore $g(x)$ is multiplicative. Note that $g(2)=8,$ and we can easily get $g(1)=1, g(0)=0.$

Now, we claim that $g(x)=x^3.$ For the sake of a contradiction, assume that there is some prime $p$ such that $g(p) \neq p^3.$ Then $2^a>p^b \iff f(2^a)>f(p^b) \implies \frac{a}{b} > \frac{\log p}{\log 2}, \frac{a}{b} \iff \frac{\log g(p)}{\log 8}.$ But by density of rational numbers, this is not true for all $a, b.$ Therefore $g(p)=p^3$ for all primes $p$ and by the Fundamental Theorem of Arithmetic $g(x)=x^3$ for all $x.$ This solution clearly works.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lpieleanu

3004 posts

lpieleanu

#60 h Mar 27, 2025, 3:23 PM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Ilikeminecraft

658 posts

Ilikeminecraft

#61 h Apr 25, 2025, 8:02 AM

Y by

$m = 0$ tells us that $f(0) = -1.$ $m = 1$ tells us that $f(1) = 0.$ Define $g(x) = f(x) + 1.$ Thus, we have that $g(mn) = g(m)g(n).$ Hence, we have that $g(0) = 0, g(1) = 1, g(2) = 8.$ We have that $g(2^n) = 8^n$ by induction. Now, we have that $x^m < 2^n$ if and only if $g(x)^m < 8^n,$ since $g$ is strictly increasing. Now, we take logarithm of both sides to get that $\log_2(x) < \frac nm, \log_8(g(x)) < \frac nm.$ However, note that between every real number, there is a rational number, and thus it follows that $\log_2(x) = \log_8(g(x)) \implies g(x) = x^3 \implies f(x) = x^3 - 1.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MathIQ.

46 posts

MathIQ.

#62 h May 18, 2025, 8:29 PM

Y by

Solution:

We are looking for increasing functions $f: \mathbb{N}_0 \to \mathbb{Z}$ satisfying $f(2) = 7$ and $f(mn) = f(m) + f(n) + f(m)f(n)$ for all nonnegative integers $m$ and $n$ .

The functional equation can be rewritten as $f(mn) + 1 = (f(m) + 1)(f(n) + 1)$ .
Let $g(n) = f(n) + 1$ . Then the equation becomes $g(mn) = g(m)g(n)$ .
Also, since $f$ is increasing, $m < n \implies f(m) \le f(n) \implies g(m) \le g(n)$ .
We are given $f(2) = 7$ , so $g(2) = f(2) + 1 = 7 + 1 = 8$ .
The domain is nonnegative integers, so we need to consider $n=0$ .
$g(0 \cdot m) = g(0) = g(0)g(m)$ .
If there exists $m$ such that $g(m) \neq 1$ , then $g(0) = 0$ .
$f(0) = g(0) - 1 = 0 - 1 = -1$ .

Consider $n=1$ .
$g(1 \cdot m) = g(m) = g(1)g(m)$ .
If there exists $m$ such that $g(m) \neq 0$ , then $g(1) = 1$ .
$f(1) = g(1) - 1 = 1 - 1 = 0$ .

Since $f$ is increasing, for $0 < 1 < 2$ , we have $f(0) \le f(1) \le f(2)$ , so $-1 \le 0 \le 7$ , which is true.

Now consider $g(mn) = g(m)g(n)$ for $m, n \in \mathbb{N}_0$ .
We have $g(0) = 0, g(1) = 1, g(2) = 8$ .
For $n > 0$ , $g(n) = n^k$ for some constant $k$ .
$g(2) = 2^k = 8 \implies k = 3$ .
So $g(n) = n^3$ for $n > 0$ .
$f(n) = g(n) - 1 = n^3 - 1$ for $n > 0$ .
Also, $f(0) = 0^3 - 1 = -1$ , and $f(1) = 1^3 - 1 = 0$ .

Let's check if $f(n) = n^3 - 1$ is increasing for $n \ge 0$ .
For $n_2 > n_1 \ge 0$ , $n_2^3 > n_1^3$ , so $n_2^3 - 1 > n_1^3 - 1$ , which means $f(n_2) > f(n_1)$ .

Check the functional equation:
$f(mn) = (mn)^3 - 1 = m^3 n^3 - 1$ .
$f(m) + f(n) + f(m)f(n) = (m^3 - 1) + (n^3 - 1) + (m^3 - 1)(n^3 - 1)$
$= m^3 - 1 + n^3 - 1 + m^3 n^3 - m^3 - n^3 + 1 = m^3 n^3 - 1$ .
The functional equation is satisfied.

Final Answer: The final answer is $\boxed{f(n) = n^3 - 1}$

Z K Y