2008 Indonesia MO Problems/Problem 8

Solution 1

Since $f: \mathbb{N}\rightarrow\mathbb{N}$, we know that $f(n)\ge 1$.

Let $m$, $n$ be $1$, $1$, respectively. Then, $f(1) + f(2) = f(1)f(1) + 1$.

Let $m$, $n$ be $1$, $2$, respectively. Then, $f(2) + f(3) = f(1)f(2)+1$

Let $m$, $n$ be $1$, $3$, respectively. Then, $f(3) + f(4) = f(1)f(3)+1$

Let $m$, $n$ be $2$, $2$, respectively. Then, $f(4) + f(4) = f(2)f(2)+1$

From the last 2 equations, we get that $\frac{1}{2}(f(2)^2+1)=f(4)=f(3)(f(1)-1)+1$

Since $f(3) = f(2)(f(1)-1)+1$, substituting, we get

\begin{align*} \frac{1}{2}(f(2)^2+1)&=(f(2)(f(1)-1)+1)(f(1)-1)+1\\ \frac{1}{2}(f(2)^2+1)&=f(2)f(1)^2-f(2)f(1)+f(1)-f(2)f(1)-f(2)-1+1\\ f(2)^2+1&=2f(2)f(1)^2-2f(2)f(1)+2f(1)-2f(2)f(1)-2f(2) \end{align*}

If we take modulo of f(2) on both sides, we get

$$1 \equiv 2f(1) \mod f(2)$$

$$2f(1)-1 \equiv 0 \mod f(2)$$

Because $f(1) + f(2) = f(1)f(1) + 1$, we also know that $f(2) = f(1)f(1)-f(1)+1 = f(1)(f(1)-1)+1$. If $f(1)>1$, then $f(2)>f(1)$.

Suppose $f(1)>1$:

since $f(2)>f(1)$, we have $2f(2)>2f(1)-1>0$. Or that $2>\frac{2f(1)-1}{f(2)}>0$. Thus, $$\frac{2f(1)-1}{f(2)}=1$$ $$2f(1)-1=f(2)=f(1)f(1)-f(1)+1$$ $$f(1)^2-3f(1)+2=0$$ $$(f(1)-2)(f(1)-1)=0$$ Thus, $f(1)=1$ or $f(1)=2$.

case 1: $f(1)=1$

Let $m=1$, and $n$ be an arbitrary integer $\ge 1$. Then, $$f(n) + f(n+1) = f(1)f(n) + 1$$ $$f(n) + f(n+1) = f(n) + 1$$ $$f(n+1) = 1$$ Thus, $f(n) = 1$.

case 2: $f(1)=2$

Let $m=1$, and $n$ be an arbitrary integer $\ge 1$. Then, $$f(n) + f(n+1) = f(1)f(n) + 1$$ $$f(n) + f(n+1) = 2f(n) + 1$$ $$f(n+1) = f(n)+1$$ This forms a linear line where $f(1)=2$ Thus, $f(n)=n+1$

Upon verification for $f(n) = 1$, we get $$f(mn)+f(m+n)=f(m)f(n)+1$$ $$1+1=1+1$$

Upon verification for $f(n) = n+1$, we get $$f(mn)+f(m+n)=f(m)f(n)+1$$ $$mn+1+m+n+1=(m+1)(n+1)+1$$ $$mn+m+n+2=mn+m+n+2$$

Thus, both equations, $f(n) = 1$ and $f(n) = n+1$ are valid