Determine all $f:\mathbb{Z}^+ \rightarrow \mathbb{Z}^+$ such that $f(m)\geq m$ and $f(m+n) \mid f(m)+f(n)$ for all $m,n\in \mathbb{Z}^+$
Problem
Source: Romania TST 2016 Day 5 Problem 2
Tags: function, algebra, number theory, functional equation
04.06.2016 19:15
Oh..so all I wrote was completely nonsense Thanks @below
04.06.2016 22:35
Tintarn wrote: So $f(m+1) \le f(m)+1$ and hence $m \le f(m) \le m+a$ for all $m$ where $a=f(1)-1$. Let $m+n > a$. Assume that $f(m+n) \ne f(m)+f(n)$. Then $2f(m+n) \le f(m)+f(n)$ and hence $2(m+n) \le m+n+2a$. Absurd! Hence we have $f(m+n)=f(m)+f(n)$ for all $m,n$ with $m+n>a$. In particular, with $n=1$ we have $f(m)=f(a)+(m-a)f(1)$ for all $m \ge a$ inductively and hence $ma \le a+af(1)-f(a)$ for all $m$ and hence $a=0$. But then $\boxed{f(m)=m}$ for all $m$ which is indeed a solution. Sorry, but the answer is $f(m)=mc$ for all $m\in \mathbb{Z}^+$ where $c\in \mathbb{Z}^+$.
02.10.2016 18:09
Any solution?
03.10.2016 15:45
Right, same mistake
03.10.2016 15:48
cazanova19921 wrote: For $m=1$, we get $f(n+1) \mid f(n)+1$ $\forall n \in \mathbb{Z}^+$, so $f(n+1) \le f(n)+1$ $\forall n \in \mathbb{Z}^+$. this implies $n \leq f(n) \leq n + c-1$ $\forall n \geq 2$ where $c=f(1)$. Conclusion, $\forall n \in \mathbb{Z}^+$, $f(n)=nc$ where $c \in \mathbb{Z}^+$. Since you know that e.g. $f(n)=2n$ is a solution, how could it be that $f(n) \le n+c$ for some constant $c$? In fact, you made the same mistake I did above, when writing $f(n+1) \mid f(n)+1$ instead of the correct $f(n+1) \mid f(n)+f(1)$...
17.10.2016 04:50
Lemma: Let $l=\inf_{n \geq 1} \frac{f(n)}{n}$ ($l$ exists because $\forall n \geq 1,$ $\frac{f(n)}{n} \geq 1$). Then $ \underset{n \to \infty}{\lim}\frac{f(n)}{n}=l$. Proof: $\forall m,n \geq 1$, $f(m+n) \leq f(m)+f(n)$, by induction, $\forall m,n \geq 1$, $f(mn) \leq mf(n)$. Let $\epsilon > 0$. By definition of $l$, there exist $m \geq 1$ such that $l \leq \frac{f(m)}{m} \leq l+ \frac{\epsilon}{2}$. Let $n \geq 1$, write $n = qm +r$ where $0 \leq r<m$, we have: $l \leq \frac{f(n)}{n} = \frac{f(qm+r)}{n} \leq \frac{f(qm)+f(r)}{n} \leq \frac{qf(m)+f(r)}{n} \leq \frac{(l+\frac{\epsilon}{2})qm}{n}+\frac{d}{n} \leq l+\frac{\epsilon}{2}+\frac{d}{n}$ where $d=\underset{0 \leq i<m}{\max}f(i)$. But $\frac{d}{n} \underset{n \to \infty}{\longrightarrow} 0$, So there exist $N > 1$, s.t. $\forall n \geq N$, $\frac{d}{n}<\frac{\epsilon}{2}$. Therefore, $\forall n>N$, $l \leq \frac{f(n)}{n} \leq l + \epsilon$. Done. Using the lemma, there exist $n_0 \geq 1$ s.t. $\forall n \geq n_0$, $|f(n) - ln| < \frac{n}{2}$. Take $n, m \geq n_0$: $|f(m+n)-f(m)-f(n)| \leq |f(m+n)-l(m+n)|+|f(m)-lm|+|f(n)-ln| < m+n$, hence $|\frac{f(m)+f(n)}{f(m+n)}-1|<\frac{m+n}{f(m+n)} \leq 1$, it follows that $f(m+n)=f(m)+f(n)$. By induction, $\forall m \geq n_0$ and $\forall n\geq 1$, $f(mn)=nf(m)$. Tending $n \to \infty$, we get $\forall m \geq n_0$, $f(m)=ml$ (so $l$ is an integer!). Let $n \geq 1$, and $m \geq n_0$, we have $(m+n)l \mid f(n)+ml$, so $(m+n)l \mid f(n)-nl$ and we can easely deduce that $f(n)=nl$.
02.08.2017 17:57
A rather different solution: Let $f(1)=c$ Since: $f(n+1)|f(n)+f(1)$, implies: $f(n+1)\leq f(n)+c$ and from an easy induction shows that: $f(n)\leq nc$ for all $n$. From: $f(2n)|2f(n)$, suggest that we should build a sequence here: Denote the sequence: $(n_k)_{k=1}^{+\infty}$ such that: $n_0=n; n_{k+1}=2n_k$, an explicitly form is: $n_k=2^kn$, which tends to infinity. Since: $f(n_{k+1})|2f(n_k)$, this means, there also exists a positive integer sequence: $(t_k)$ such that: $2f(n_k)=t_kf(n_{k+1})$. Multiple side by side from $k=0$ to and arbitrary number $m$: $2^{m+1}f(n)=t_0t_1...t_m f(n_{m+1})=t_0t_1...t_m f(2^{m+1}n)\geq t_0t_1...t_m .2^{m+1}n$ And since: $f(n)\leq cn$, this implies: $c\geq t_0t_1...t_m$ forall $m$, since the right-hand side is product of positive integer, thus, there must exist $N$ such that forall $m>N$, $t_m=1$, or we can say that: $f(n_{m+1})=2f(n_m)$ forall $m>N$ Now, consider any fixed $k$, we shall prove the CLAIM: $f(k+1)=f(k)+c$ Since the above sequence tends to infinity: Taking an index $m>N$ and sufficient large (for later use). We have: $f(2n_m)=2f(n_m)$ and: $f(4n_m)=2f(2n_m)$, for convenient, set: $n=n_m$, that means: $f(2n)=2f(n)$ and: $f(4n)=2f(2n)$ Since: $f(2n)|f(n+j)+f(n-j)$ (Just for $j=1$ and $j=k$) Hence: $2f(n)|f(n+j)+f(n-j)$ or: $f(n)|f(n+j)+f(n-j)$ Since: $f(n)|f(n-j)+f(j)$, thus: $f(n)|f(n+j)-f(j)$ Since our $n$ is sufficient large, this implies: $f(n)\leq f(n+j)-f(j)$ But since: $f(n+j)|f(n)+f(j)$, implies: $f(n+j)\leq f(n)+f(j)$. Hence: $f(n+j)=f(n)+f(j)$, or: $f(n+1)=f(n)+c$ and: $f(n+k)=n+k$ Since we have the equivalence property with $2n$, we also have, with the same process: $f(2n+k+1)=f(2n)+f(k+1)=2f(n)+f(k+1)$ Finally, we are ready to prove that claim: $f(2n+k+1)|f(n+k)+f(n+1)=2f(n)+f(k)+c$, or: $2f(n)+f(k+1)|2f(n)+f(k)+c$, implies: $2f(n)+f(k+1)|f(k)+c-f(k+1)$, and once again, since $n$ is sufficient large, we must have: $f(k)+c=f(k+1)$ Thus, by an easy induction, we have: $f(n)=cn$, which is indeed a solution for all positive integer $c$
24.01.2022 22:03
Nice problem! My answer is $f(x)=xc$ with $c$ a fixed positive integer. Let: $P(x,y): f(m+n) \mid f(m)+f(n)$ Basically it is to prove the following lemma: Lemma:There are infinite positive integers $n$ such that $f(2n)=2f(n)$ Proof: Suppose the lemma isn't true, then: $$P(2^{k}n,2^{k}n): f(2^{k+1}n) \mid 2f(2^{k}n)$$So for $n$ sufficiently large $f(2^{k+1}n) \leq f(2^{k}n)$ for all $k$ positive integer, so: $$f(2^{k+1}n) \leq f(n) \implies 2^{k+1}n \leq f(n)$$That isn't true for a large $k$, contradiction! $\square$ Corollary: For all positive integer $x$: $f(2x)=2f(x)$ Proof: Let $r$ a large integer such $f(2r)=2f(r)$ then let $x$ a fixed positive integer: $$P(r,x): f(r+x) \mid f(r)+f(x) \implies 2f(r+x)\mid 2f(r)+2f(x)$$$$P(2r,2x): f(2r+2x) \mid f(2r) +f(2x) \implies 2f(r+x) \mid f(2r+2x) \mid 2f(r) +f(2x)$$Combining both: $$ 2f(r+x) \mid 2f(x)-f(2x) $$But $r+x \leq f(r+x)$ so $2f(x)-f(2x)$ have divisors very "bigs" so $2f(x)=f(2x)$ $\square$ Finally it's enough to prove that: Claim: If exists a positive integer $k$ such that $f(kx)=kf(x)$ for all $x$. Then $f((k+1)x)=(k+1)f(x)$ for all $x$. Proof: It's very similar to the above, first we need to prove that exists infinite positive integers $n$ such that $f((k+1)n)=(k+1)f(n)$ this is because suppose that there are no infinities $n$ ,so: $$P(kn,n): f((k+1)n)\mid f(kn)+f(n) \implies f((k+1)n) \mid (k+1)f(n)$$So for $n$ sufficiently large: $$\frac{f((k+1)n)}{(k+1)n} \leq \frac{1}{2}\frac{f(n)}{n} \implies \frac{f((k+1)^{r}n)}{(k+1)^{r}n} \leq \frac{1}{2^r}\frac{f(n)}{n} \implies 1 \leq \frac{1}{2^r}\frac{f(n)}{n} $$And the last part isn't true for $r$ sufficiently large. Contradiction! Then exists infinites $n$ such that $f((k+1)n)=(k+1)f(n)$ Let $q$ an arbitrary positive integer, then: $$P(n,q): f(n+q) \mid f(n)+ f(q) \implies (k+1)f(n+q) \mid (k+1)f(n)+ (k+1)f(q)$$$$P((k+1)n,(k+1)q): f((k+1)(n+q)) \mid f((k+1)n)+f(q(k+1)) \implies (k+1)f(n+q) \mid (k+1)f(n)+f(q(k+1))$$Combining both: $$(k+1)f(n+q) \mid f(q(k+1))-(k+1)f(q)$$But $(k+1)f(n+q)$ is unbounded when $n$ varies so $f(q(k+1))-(k+1)f(q)=0$ for any $q$, so we are done. $\square$ This gives us the answer because the claim is true when $k=2$ so it's true for any $k$, then $f(k)=f(1)k$
13.04.2022 11:50
The condition $f(m) \ge m$ implies that $f$ is unbounded. Now ignore $f(m) \ge m$, and use the fact that $f$ is unbounded instead. Denote $g(T)$ by the smallest positive integer $j$ that satisfies $$f(j) \ge T > \max(\{f(1), f(2), f(3), \dots, f(j - 1)\}),$$where we define $\max(\varnothing) = 0$. For every positive integer $T$, the value of $g(T)$ is well-defined since $f$ is unbounded (Intuitively, $g(T)$ is the first time the function $f$ exceeds $T$ in value). The function $g$ must also satisfies $g(x) \ge g(y)$ whenever $x \ge y$, and surely $g$ is also unbounded. Let $C = f(1)$. For each $k \in \mathbb{N}$, define $N_k$ using the following algorithm: Start with $N_k = (2k+1)C$. If $g(N_k) \le k$, increment the value of $N_k$. Repeat this step. The algorithm will end because $g$ is unbounded, so $g(N_k)$ eventually will be greater than $k$. Now, define $m_k = g(N_k)$. We have the following estimate: $$ f(m_k) \ge N_k \ge (2k+1)C.$$ Claim 01. $f(i) + f(m_k - i) = f(m_k)$ for each $1 \le i < m_k$. Proof. By definition of $m_k$, $f(i) + f(m_k - i) < f(m_k) + f(m_k) = 2f(m_k)$. Since $f(i) + f(m_k-i)$ is a multiple of $f(m_k)$, so $f(i) + f(m_k - i) = f(m_k)$. $\square$ Claim 02. $f(m_k - t) = f(m_k) - tC$ for every $t \in \{0, 1, 2, \dots, k \}$. Proof. By the construction of $m_k$, we have $m_k = g(N_k) > k$. Therefore, $m_k - k \in \mathbb{N}$. We are going to prove the claim using induction on $t$. The base case $t=0$ is obvious. Now, let's assume $f(m_k - t) = f(m_k) - tC$ for $t = i$. Consider the following: \[ f(m_k - i) | f(m_k - (i + 1)) + f(1). \]If $\frac{f(m_k - (i + 1)) + f(1)}{f(m_k - i)} \ge 2$, then $f(m_k - (i + 1)) \ge 2f(m_k - i) - C = 2(f(m_k) - Ci) - C \ge f(m_k)$, a contradiction (The last inequality is the consequence of $f(m_k) \ge (2k+1)C \ge (2i+1)C$). Therefore, $\frac{f(m_k - (i + 1)) + f(1)}{f(m_k - i)} = 1$, i.e. $f(m_k - (i + 1)) = f(m_k - i) - f(1) = f(m_k) - (i + 1)C$. $\square$ Combining both claims, we obtain $f(i) = f(m_k) - f(m_k - i) = f(m_k) - (f(m_k) - Ci) = Ci$ for every $i \in \{1, 2, \dots, k\}$. Since $k$ can be arbitrarily large, therefore $f(n) = Cn$ for every $n \in \mathbb{N}$. $\blacksquare$
14.04.2022 16:38
Different solution: Let $P(m,n)$ denote the assertion that $f(m+n)|f(m)+f(n)$. From $P(m,n)$, we get that $f(m+n)\le f(m)+f(n)$, and by induction $f(m+kn)\le f(m)+kf(n)$. $P(n,n): f(2n)|2f(n)$, so $\frac{f(2n)}{2n}\le \frac{f(n)}{n}\implies \frac{f(2^k)}{2^k}\le \frac{f(2^{k-1})}{2^{k-1}}$. Since $\frac{f(2^k)}{2^k}$ cannot keep getting smaller by at least a factor of 2, hence it is eventually constant, i.e. $f(2^{k+r})=2^kf(2^r)$ for some $r$ and all $k\ge 0$. Take $r$ to be minimal. Note $$2^kf(2^r)=f(2^{k+r})\le f(2^r)+f(2^r(2^k-1))\le\cdots\le 2^kf(2^r)$$Thus equality must hold everywhere so $f(2^r(2^k-i))=(2^k-i)f(2^r)$ for all $i<2^k$. Since $k$ can be anything, $f(n2^r)=nf(2^r)$ for all $n$. Now $f(m+n2^r)|f(m)+nf(2^r)$ and $f(m+2^r)+(n-1)f(2^r)$. If $f(m+2^r)-f(m)-f(2^r)\ne 0$, then $|m+n2^r|\le f(m+n2^r)\le |f(m+2^r)-f(m)-f(2^r)|$, contradiction since the LHS is unbounded. Hence $f(m+2^r)=f(m)+f(2^r)$ for all $m$. If $r=0$ then we are done, $f$ is linear and $f(m)=cm$, which works. Else $P(2^{r-1},n2^{r}-2^{r-1}): nf(2^r)|2f(2^{r-1})+(n-1)f(2^r)$, so it divides $2f(2^{r-1})-f(2^r)$. Since the LHS is unbounded, $2f(2^{r-1})=f(2^r)$, which contradicts the minimality of $r$.