3
$\begingroup$

Let N={1,2,3,…}. Determine if there exists a strictly increasing function $f:N→N$ such that

  1. $f(1)=2$

  2. $f(f(n))=f(n)+n$ for all n."

Here is the solution I came up with

We can see $f(1)=2$

$f(2)=3$

$f(3)=5$

Basically if $a_n$ is the $(n+2)^{th}$ term in the Fibonacci sequence starting from 1,1,2,3,5..

then I claim

$f(a_n)=a_{n+1}$

This can easily be proved by induction as follows

Assume $f(a_n)=a_{n+1}$

Then $f(a_{n+1})=f(a_{n})+a_n=a_{n+2}$

Now clearly $a_{n+1}-a_n<a_{n+2}-a_{n+1}$

So all numbers between $a_n$ and $a_{n+1}$ can be assigned any arbitrary value between $a_{n+2}$ and $a_{n+1}$ in increasing order and hence many such functions may exist

I wanted to know if my solution is correct because it looks rather simple and this is an IMO problem

$\endgroup$
7
  • 2
    $\begingroup$ In the step "so all numbers.. can be assigned arbitrary value..." how do you make sure the assignment satisfies condition 2? $\endgroup$ Commented Sep 28, 2023 at 8:07
  • 3
    $\begingroup$ Remember that $f(f(n))=f(n)+n$ must hold true for all numbers, so $f(f(4))=f(4)+4$, for example. So you can't just assign arbitrary values. $\endgroup$ Commented Sep 28, 2023 at 8:15
  • $\begingroup$ @MichalAdamaszek thank you now I see my mistake However can I still prove that there will be values that satisfy condition 2 so that such a function may exist without finding such a function $\endgroup$ Commented Sep 28, 2023 at 8:57
  • 1
    $\begingroup$ I don't have any hint. You were asking "is it possible to prove that an object exists without constructing it explicitly". The answer is in general yes. I don't have any clue how you would do it in this specific example. Have a look around, this functional equation was answered a few times on this page. $\endgroup$ Commented Sep 28, 2023 at 9:02
  • 1
    $\begingroup$ Note that if you follow your suggested strategy greedily, then you will assign $f(4)=6$ as first available and then necessarily $f(6)=f(4)+4=10$; after this, $f(7)=9$ as first available and then necessarily $f(9)=9+7=16$, $f(16)=16+9=25$, $f(25)=25+16=41$; after this, $f(11)=14$ as first available, and then $f(14)=14+11=25$, $f(25)=25+14=39$ -- oops! $\endgroup$ Commented Sep 28, 2023 at 9:25

1 Answer 1

0
$\begingroup$

In the step "assigning arbitrary values" the condition $f(f(n))=f(n)+n$ may not hold.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .