Find all functions $f:\mathbb N\to \mathbb N$ such that $\frac{4f(x)f(y-3)}{f(x)f(y-2)+f(y)f(x-2)}$ is an integer for all $x>2$ and $y>3$.

The following problem is from an online contest that ended today:

Find all functions $f:\mathbb N\to \mathbb N$ such that $$\frac{4f(x)f(y-3)}{f(x)f(y-2)+f(y)f(x-2)}$$ is an integer for all $x>2$ and $y>3$.

I have made the following progress:

Taking $x=y\geq4$, the constraint becomes $$\frac{2f(x-3)}{f(x-2)}$$ which we want to be an integer for all $x\geq4$.

Now one case is that $\frac{2f(x-3)}{f(x-2)}=c$ for all $x\geq4$, where $c$ is a positive integer constant. We consider this case.

Let $\frac{2f(n)}{f(n+1)}=c$ for all $n\geq1$. We have $$f(n+1)=\frac{2f(n)}{c}\implies f(n)=\left(\frac 2 c\right)^{n-1}f(1)$$ If $c>2$, then $f(n)$ can not always be integer. So we have $c=1$ or $c=2$.

If $c=2$, then we have $f(n)=f(1)=k$ for all $n$. Plugging it in the given expression, we have $$\frac{4k^2}{2k^2}=2$$ which is an integer. So $f(n)=k$ works.

If $c=1$, then we have $f(n)=2^{n-1}f(1)=2^{n-1}k$. We can confirm that this function works by plugging in the expression.

But there is other case when $\frac{2f(n)}{f(n+1)}$ is not a constant. I can't find a way to solve this case.

I assume that $\Bbb N$ does not contain zero.

As you have worked out, we have $f(x + 1) \mid 2f(x)$ for all $x$.

This means that the number of odd prime divisors of $f(x)$, counted with multiplicity, never increases. As a result, there is an odd number $m$ such that $f(x) = 2^{v_x}m$ for all sufficiently large $x$ (which I will abbreviate to "for s.l. $x$"). Moreover, we have $v_{x + 1} \leq v_x + 1$ for s.l. $x$.

Now in the original condition, we have $2^{v_x + v_{y - 2}} + 2^{v_y + v_{x - 2}} \mid 2^{v_x + v_{y - 3} + 2}$ for s.l. $x, y$. This is only possible when $v_x + v_{y - 2} = v_y + v_{x - 2}$, i.e. $v_x - v_{x - 2} = v_y - v_{y - 2}$ for s.l. $x, y$. We denote by $k$ this common value.

It follows that $v_x = v_{x + 2} - k = v_{x + 4} - 2k = \cdots = v_{x + 2s} - sk$ for any $s > 0$. But $v_{x + 2s}$ is nonnegative, hence we get $k \geq -\frac{v_x}s$. Taking $s \rightarrow \infty$ shows that $k \geq 0$.

On the other hand, we have $v_x \leq v_{x - 1} + 1 \leq v_{x - 2} + 2$, namely $k \leq 2$. This leaves only three possibilities: $k = 0, 1, 2$.

Case $k = 2$: the only possibility is that $v_x = v_{x - 1} + 1$ for s.l. $x$, namely $f(x) = 2f(x - 1)$. This implies that there exists $r \in \Bbb Q$ such that $f(x) = 2^xr$ for s.l. $x$.

We will prove that $f(x) = 2^xr$ holds for all $x$. Suppose it is not the case. Let $N$ be the largest integer such that $f(N) \neq 2^Nr$. From $f(N + 1)\mid 2f(N)$, we know that $f(N) = c \cdot 2^Nr$ for some $c\in \Bbb N$. Taking $x = N + 2$ and s.l. $y$ in the original condition, we get $1 + c \mid 2$ which forces $c = 1$. This contradicts the assumption that $f(N) \neq 2^Nr$.

Thus in this case we have $f(x) = 2^xr$ for some $r$.

This technique will be repeatedly used below and the details are sometimes omitted.

Case $k = 1$: there are two subcases: either $v_x = v_{x - 1}$ for s.l. even $x$, or $v_x = v_{x - 1}$ for s.l. odd $x$. I will treat the latter case, the previous one being similar.

Thus we have $v_x = v_{x - 1}$ for s.l. odd $x$ and $v_x = v_{x - 1} + 1$ for s.l. even $x$. This means that there exists $r \in \Bbb Q$ such that $f(x) = 2^{\lfloor \frac x 2\rfloor}r$ for s.l. $x$.

We can again show that $f(x) = 2^{\lfloor \frac x 2\rfloor}r$ for all $x$, by taking $N$ to be the largest integer that doesn't satisfy this identity.

For the subcase that $v_x = v_{x - 1}$ for s.l. even $x$, we get similarly $f(x) = 2^{\lceil \frac x 2\rceil}r$.

Case $k = 0$: there are three subcases:

i. $v_x = v_{x - 1}$ for s.l. $x$;
ii. $v_x = v_{x - 1} + 1$ for s.l. even $x$ and $v_x = v_{x - 1} - 1$ for s.l. odd $x$;
iii. $v_x = v_{x - 1} - 1$ for s.l. even $x$ and $v_x = v_{x - 1} + 1$ for s.l. odd $x$.

In (ii) and (iii), the same argument as above (considering largest $N$ for which the formula is not valid) shows that the function $f$ is an alternating sequence $r, 2r, r, 2r, \dots$ or $2r, r, 2r, r, \dots$.

It remains to consider (i). In this case, there exists $r$ such that $f(x) = r$ for s.l. $x$. Let $N$ be the largest integer such that $f(N) \neq r$.

We will show by induction that, there exists a sequence of nonnegative integers $w_n$ such that

• $f(x) = 3^{w_x}r$ for all $x$;
• $w_x = 0$ for all $x > N$;
• $w_x - w_{x + 1} \in \{0, 1\}$ and $w_x - w_{x + 2} \in \{0, 1\}$. In other words, the sequence $(w_n)_n$ decreases by $0$ or $1$ at each step, and does not have two consecutive decreases by $1$.

The claim is clearly true for all $x > N$. Suppose it is true for all $x > M$ and let us prove it for $x = M$.

Taking s.l. $y$ in the original condition, we have $f(x) + f(x - 2) \mid 4f(x)$ for all $x$.

Taking $x = M + 2$, we get $t + f(M) \mid 4t$ where $t = f(M + 2)$.

By induction hypothesis, we have either $f(M + 1) = t$ or $f(M + 1) = 3t$.

If $f(M + 1) = t$, then we have $f(M) = \frac t2 c$ for some $c \in \Bbb N$. This implies $c = 2$ or $c = 6$, i.e. $f(M) = t$ or $f(M) = 3t$.

If $f(M + 1) = 3t$, then we have $f(M) = \frac{3t}2c$ for some $t \in \Bbb N$. This implies $c = 2$, i.e. $f(M) = 3t$.

We have thus proved our claim.

Conversely, let $(w_x)$ be a sequence of integers such that

• $w_x = 0$ for s.l. $x$;
• $w_x - w_{x + 1} \in \{0, 1\}$ and $w_x - w_{x + 2} \in \{0, 1\}$;

and we define $f(x) = 3^{w_x}r$. Let us verify that this function $f$ satisfies the original condition.

Since we have $f(y - 2) \mid f(y - 3)$, it suffices to show that $$\frac{4f(x)f(y - 2)}{f(x)f(y - 2) + f(y)f(x - 2)} \in \Bbb Z.$$ Since both $f(x)/f(x - 2)$ and $f(y)/f(y - 2)$ belong to $\{1, 3\}$, there are only four cases and a direct check shows that the quotient is an integer in all four cases.

In conclusion, $f$ is one of the following functions:

• $f(x) = 2^x r$;
• $f(x) = 2^{\lfloor\frac x2\rfloor} r$;
• $f(x) = 2^{\lceil\frac x 2\rceil} r$;
• $f(x) = 2^{x \mod 2} r$;
• $f(x) = 2^{(x + 1) \mod 2}r$;
• $f(x) = 3^{w_x}r$ for some sequence of integers $w$ such that $w_x - w_{x + 1}, w_x - w_{x + 2} \in \{0, 1\}$ for all $x$, and $w_x = 0$ for all sufficiently large $x$.