if $f(mn)+f(m+n-1)=f(m)f(n)$How find $f(n)$

Question

let $f:N^{+}\to Z$,and $f$ is monotonic nondecreasing,and such $$f(m)f(n)=f(mn)+f(m+n-1),f(4)=5$$ Find all $f(n)$

My try: let $$m=2,n=2\Longrightarrow f^2(2)=f(4)+f(3)$$ $$m=1.n=4,f(1)f(4)=f(4)+f(4)\Longrightarrow f(1)=2$$ $$m=2,n=1,f(2)f(1)=f(2)+f(2)\Longrightarrow f(1)=2$$ $$n=1,m=m\Longrightarrow f(m)f(1)=f(m)+f(m)\Longrightarrow f(1)=2$$ $$m=2,n=3,f(2)f(3)=f(6)+f(4)$$ I can't find $f(2)$,

since $$2=f(1)\le f(2)\le f(3)\le f(4)=5$$,then we must $$f(2)=3,f(3)=4$$. but for $n\ge 6$,I can't find it.

and I found $$f(n)=n+1$$ is such it.because $$f(m)f(n)=(m+1)(n+1)=(mn+1)+m+n=f(mn)+f(m+n-1)$$

But I can't prove it.

Thank you

Answer 1

My main idea is to supply a definition of $f(0)$ which is well defined by $$ f(m)f(n)=f(mn)+f(m+n-1)\qquad(1) $$ Now, you have two conditions that $f(1)=2$(you had proof it) and $f(4)=5$. Set $n=0$ in $(1)$, we have: $$ f(0)+f(m-1)=f(m)f(0)\qquad(2) $$ Then, set $m=2,3,4$, we have the following system: $$ f(0)+2=f(2)f(0)\\ f(0)+f(2)=f(3)f(0)\\ f(0)+f(3)=5f(0) $$ There is only one real solution of it, that is $f(0)=1$, $f(2)=3$, $f(3)=4$. Then, we guess that $f(n)=n+1$ and we will prove it by mathematical induction:

Proposition: Under (1), $f(n)=n+1$ for $n\in N$.

Proof:

1.n=0, $f(0)=1$, the proposition is right. 2.If proposition is valid for any $k\in N$, then for $k+1$, from $(2)$, we have: $$ 1+f(k)=f(k+1)\\ f(k+1)=k $$ That is, it is also valid for $k+1$.

Q.E.D. In summary, we have $f(n)=n+1$.

---

I can prove the conclusion by another way. Firstly, from @Mark Bennet's work, we have $f(1)=2$, $f(2)=3$, $f(3)=4$, $f(4)=5$. We can claim:

For any $n\in N^+$, we have: i) $f(2n)=2n+1$ and ii) $f(2n+1)=2n+2$.

The proof also given by mathematical induction.

1. For $n=1,2,3,4$, the conclusion had been got.

2. Assuming the proposition is valid for $k\in N^+$, we have the following deduction:

Set $n=2$ and $n=4$ in $(1)$, we have: $$ f(2m)+f(m+1)=3f(m)\qquad(3)\\ f(4m)+f(m+3)=5f(m)\qquad(4) $$ So $f(2k+2)=3f(k+1)-f(k+2)$. When $k>2$, $f(k+1)$ and $f(k+2)$ is known under the assumption that proposition is valid for $k$. So it easy to obtain that $f(2k+2)=2k+3$. That is, i) is valid.

From $(3)$ and $(4)$, we have: $$ 5f(m)-f(m+3)=f(4m)=f(2\times2m)=3f(2m)-f(2m+1)=3(3f(m)-f(m+1))-f(2m+1) $$ Render it in a neat form, we have: $$ 4f(m)-3f(m+1)-f(2m+1)+f(m+3)=0 $$ Similarly, when $k>3$, $f(m+1)$, $f(m+2)$ and $f(m+4)$ are all known. Then from $f(2k+3)=4f(k+1)-3f(k+2)+f(k+4)$ we can easily to check that ii) is also valid. Then we get the desired result.

I would like to point out that this proposition do not include the case that $n=1$, but this case is trivial to prove.

Answer 2

HINT: You haven't used the monotonic nondecreasing condition yet.

You have $f(1)=2$ and $f(4)=5$ so $2\le f(2)\le f(3)\le 5$

If you have values up to $f(2n)$ you can use the approach you have for $f(6)$ to find $f(2n+2)$, and then use the monotonic property to find $f(2n+1)$.

Answer 3

Here's a proof that the only solution is $f(n)=n+1$. If we remove the assumption that $f(4)=5$, we also get the constant functions $f(n)=0$ and $f(n)=2$, but no more I think (although I haven't checked that in detail).

Assume there exists a number $a$ such that $f(a)=f(a+1)$. Then $$ f(na)+f(n+a-1)=f(n)f(a)=f(n)f(a+1)=f(na+n)+f(n+a) $$ and since $f(na)\le f(na+n)$ and $f(n+a-1)\le f(n+a)$, this implies that $f(n+a)=f(n+a-1)$ and $f(na+n)=f(na)$ for all $n$. Plugging $n=1,2,\ldots$ into $f(n+a)=f(n+a-1)$ then gives us that $f(a+n)=f(a)$ for all $n$: i.e. $f(n)$ is constant for $n\ge a$. However, if this is the case, we can use the converse result: that $$ f(n)f(a)=f(na)+f(n+a-1)=f((n+1)a)+f((n+1)+a-1)=f(n+1)f(a) $$ which implies $f(n)=f(n+1)$ for all $n$ (given that $f(a)\ge f(1)>0$). So, this means $f$ is constant, which gives the equation $f^2=2f$ which has solutions $f=0$ and $f=2$, neither of which satisfy $f(4)=5$.

So, now we know $f$ is strictly increasing. Since $f(1)=2$ and $f(4)=5$, and we can verify that $f(n)=n+1$ is a solution, we assume there is a smallest number $A$ for which $f(A)>A+1$. Then, since $f$ is strictly increasing, $f(n)>n+1$ for all $n\ge A$. However, if we pick $n$ so that $2n=A$ or $A+1$, we get $$ f(2n)=f(2)f(n)-f(n+1)=3(n+1)-(n+2)=2n+1 $$ since $2,n<A$ as $A>4$. So there can be no such $A$ and $f(n)=n+1$ for all $n$.