Do I Need To Find All Functions Satisfying A Given Equation In Such Cases?

I am trying to do an exercise from Venkatachala's book on functional equation (specifically exercise 2.5) which is the following:

Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a function such that

• $f(m) < f(n)$ whenever $m < n$;


• $f(2n) = f(n) + n$ for all $n \in \mathbb{N}$; and


• $n$ is a prime number whenever $f(n)$ is a prime number.

Find $f(2001)$.

We can see from sheer inspection that $f(n) = n$ works. Suppose that I manage to prove via induction that $f(n)=n$ works. But is that enough to conclude that $f(2001) = 2001$ (the induction didn't prove that it is the only function) ? Is it necessary to find all functions that satisfy this (I don't think there are more functions that satisfy this by the way) ?.

Answer

As TrostAft noted, the formulation of the problem is slightly unclear. It is not totally trivial that only one function may satisfy the condition, so it is not clear that there is only one possible value for $f(2001)$. So asking for it as if was a unique value is strange.

That said, it is pretty easy to find one function that satisfies it (as you did), so the question would be over if you assume that "Since it asks for one value, it can only be one value, so it must be 2001." So let's do the full work and find all values, which (as is to be expected) comes to finding all functions that satisfy the conditions.

Then you use the following idea, that is in some sense what TrostAft wrote:

For any $n\ge 1$, consider the $n+1$ function values $f(n), f(n+1),\ldots,f(2n-1),f(2n)$. We know $f(n) < f(n+1) <\ldots < f(2n-1) < f(2n) = f(n) + n$ from the first and second conditions.

So those $n+1$ function values (positive integers) come from a set of exactly $n+1$ values ($f(n),f(n)+1,\ldots,f(n)+n$), so they must be exactly those intergers, in that order: $f(n+1)=f(n)+1, f(n+2)=f(n)+2, \ldots, f(2n-1)=f(n)+n-1, f(2n)=f(n)+n$.

So, for each $n$ we get $f(n+1)=f(n)+1$. In other words, any possible $f$ must be of the form $f(n)=n+c$, for some constant c.

Now we need to use that strange third condition to find which values of $c$ are possible. It's easy to see that this is only possible if $c=0$.

Otherwise, for each prime $p > c$, $p-c$ would also be a prime (because $f(p-c)=p$ and the third condition), and that impossible, as the gaps between primes can get arbitrarily high (none of the $(k-1)$ numbers $k!+2, k!+3,\ldots,k!+k$ is prime).

So only $c=0$ is possible and $f(n)=n$ is the only function satisfying the 3 conditions.