If $f$ is a bijection of ${\mathbb N}$ then there exist infinitely many triples $a<b<c$ with $f(b)={f(a)+f(c)\over2}$.

Let $$f$$ be a bijection from the set of nonnegative integers to itself. Show that there exist infinitely many triples of nonnegative integers $$(a,b,c)$$ with $$f(a) + f(c) = 2f(b)$$ and $$a < b < c$$.

Hello everybody. I hope you are all doing well. The question you see above is a question I could not solve. :( Any help would be appreciated. Here's what I though of:

A.P. stands for Arithmetic Progression

We just want to show that there exist infinitely many integers such that $$f(a), f(b), f(c)$$ are in A.P. $$a < b< c$$. Since $$f$$ is a bijection, it makes our work easier.

Suppose otherwise. There exist no $$a, b, c$$ with the conditions required. That is, there exists no $$f(a), f(b), f(c), a < b < c$$ such that they are in A.P.

Hence, $$f(0), f(1), f(k)$$ where is $$k$$ is a non-negative integer, can never be in A.P. Let $$f(0) = l$$ and $$f(1) = m$$. Also let $$d = m - l$$. Note that since $$f$$ is a bijection, $$f(k) \neq l, m$$ and $$l \neq m$$. Also assume $$f(k) = p \neq m \neq l$$ $$f(0) = l$$$$f(1) = m$$We consider $$f(1) > f(0)$$. OK now since $$f(0), f(1), f(k)$$ can not be in AP, we have $$p - m \neq m-l$$. That is there exists no $$k$$ in non negative integers when $$m, l, p$$ are in AP, which is absurd iterating $$k$$ from $$2$$.

Let me give you an example to make it clearer.

Let $$f(0) = 5$$ and $$f(1) = 20$$. The difference is $$15$$. Clearly, $$35$$ would satisfy our conditions. Since $$f$$ is bijection, there should be some number $$k$$ such that $$f(k) = 35$$. That is $$f(0), f(1), f(k)$$ are in AP. Of course $$k$$ is greater that $$0, 1$$ because it is not $$0,1$$ and an integer.

It only works for $$f(1) > f(0)$$ but I thought that the whole set of nonnegative integers must have a pairing, not just $$0$$ and $$1$$. In addition, while something like $$f(0) = 10$$ and $$f(1) = 5$$ might not work, there are is an infinite number of other pairs that will work.

Please help. I would be glad to have my "solution" being corrected. Please also inform if this question is a duplicate as it seems as a very common question but I could not find this anywhere on the internet.

Thank You.

EDIT: As pointed out by Martin R (thank you), this has an answer for one such triplet. It is here: Solve this problem on functions

• The existence of one such triple is demonstrated here: math.stackexchange.com/questions/1749558/…. – Martin R Sep 6 at 12:21
• Thank you Martin. That definitely helps. BTW how did you search this problem up? (because the title is really weird "Solve this problem on functions") Thanks – Vasu090 Sep 6 at 12:23
• With Approach0. See also math.meta.stackexchange.com/q/24978/42969. – Martin R Sep 6 at 12:25
• Thank you so much. I did not know about it. :) – Vasu090 Sep 6 at 12:27
• I think it is Approach0 (with zero), not Approacho. – GEdgar Sep 6 at 12:38

The map $$g:=f^{-1}$$ is a bijection of $${\mathbb N}_{\geq0}$$ as well. For a pair $$(y,h)$$ such that $$g(y-h) put $$a:=g(y-h)$$, $$b:=g(y)$$, $$c:=g(y+h)$$. Then $$a and $$f(a)+f(c)=(y-h)+(y+h)=2y=2 f(b)\ .$$ Claim. There are infinitely many pairs $$(y,h)$$ satisfying $$(1)$$.
Proof. Define the function $$s(y):=\max\bigl\{k\bigm| [0..k]\subset g\bigl([0..y]\bigr)\bigr\}\qquad\bigl(y\geq f(0)\bigr)\ .$$ The function $$y\mapsto s(y)$$ is weakly increasing to $$\infty$$, but may make jumps $$>1$$. There are infinitely many $$y$$ with $$s(y-1). Consider such a $$y$$, and put $$s(y-1)=:k-1$$. Then $$s(y)\geq k$$. Since $$k\notin g\bigl([0..(y-1)]\bigr)$$ and $$[0..k]\subset g\bigl([0..y]\bigr)$$ it follows that $$g(y)=k$$. Furthermore $$g(y+h)>k=g(y)$$ for all $$h>0$$. On the other hand, there are many $$h>0$$ for which $$g(y-h). It follows that the $$y$$ we are considering can be supplemented with an $$h>0$$ such that $$(1)$$ holds.