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 map $g:=f^{-1}$ is a bijection of ${\mathbb N}_{\geq0}$ as well. For a pair $(y,h)$ such that $$g(y-h)<g(y)<g(y+h)\tag{1}$$ put $a:=g(y-h)$, $b:=g(y)$, $c:=g(y+h)$. Then $a<b<c$ 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)<s(y)$. 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)<k=g(y)$. It follows that the $y$ we are considering can be supplemented with an $h>0$ such that $(1)$ holds.