4

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) ?.

defunct-user
  • 329
  • 1
  • 10
  • Since $f(n) = n$ is a valid function, I think you'd probably need to prove somehow that $f$ must be the identity function. – TrostAft Apr 09 '18 at 13:58
  • Here's a potential idea for induction. Notice that by the second statement, we can say that $f(2) = f(1) + 1$. So then we can define $f(1) = f(2) - 1$. Furthermore, we can say that $f(4) = f(2)+2 = f(1)+3$. So then as far as $f(3)$ goes, we know that $f(2) < f(3) < f(4)$ which tells me that $f(1)+1 < f(3) < f(1)+3$ which implies that $f(3) = f(1)+2$. Maybe using this pattern you can extrapolate? – TrostAft Apr 09 '18 at 14:12
  • I don't think you got my question. I edited the question now. – defunct-user Apr 09 '18 at 14:35
  • Well I was providing a pathway to show that no other function besides the identity may satisfy the above constraints, but now that you mention it, if you did find a function that satisfied the above constraints and had $f(2001) \neq 2001$ that would make no sense question wise.

    I would say that if you're doing this for a competition, there's no reason to proceed further, but if you're just proving this, yes you should show that $f(n) = n$ is the only such function that satisfies these constraints for completeness.

     – TrostAft Apr 09 '18 at 14:40
  • 1
    I see, TrostAft is suggesting to prove via induction that $f(n) = f(1) + n - 1$. Then the third property should imply that $f(n)=n$. –  Apr 09 '18 at 14:46

1 Answers1

3

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.

Ingix
  • 14,494
  • Thanks for the answer, though you answered more than what I needed. I didn't ask how to prove that $f(n) = n$ is the only solution; I asked (this is what I meant, at least) that if there are multiple such functions and $f(n) = n$ is one of them, then can i just evaluate $f(n)$ at $n=2001$ and conclude that $2001$ is the answer. – defunct-user Apr 09 '18 at 15:52
  • 1
    @lil'mathematician No, you can't. Conceivably, the answer could be $f(2001)=2001+f(0)$, for instance. – egreg Apr 09 '18 at 15:59