Does there exist a function $f : \mathbb{Z}^+ \to \mathbb{Z}^+$ such that $f(f(n))+f(n+1)=2n$, $\forall n \in \mathbb{Z}^+$ ?

My attempt :

Substitute $n=1$, $f(f(1))+f(2)=2$ so $f(f(1))=f(2)=1$

Substitute $n=2$, $f(f(2))+f(3)=4$ so $f(1)+f(3)=4$

Substitute $n=3$, $f(f(3))+f(4)=6$

Assume that there exists $k >1$ such that $f(k) \geq k$,

then $f(f(k-1))+f(k)=2k$, we have $f(f(k-1))<k$


2 Answers 2


Yes there exists such a function.
Let's define $g(x)$ as follows:

$$ g(n) = \left\{ \begin{array}{lcc} \ \ \ n \ \ \ \ \ \ \ , & \mbox{ if } n \mbox{ is odd } , \\ \\ n-1 \ \ \ , & \mbox{ if } n \mbox{ is even } . \end{array} \right.$$

One can check easilly that $g(n)$ satisfies the relation $g(g(n))+g(n+1)=2n$, $\forall n \in \mathbb{N}$ .


For a positive integer $n$, let $P(n)$ denote the condition that $f\big(f(n)\big)+f(n+1)=2n$. The condition $P(1)$ implies that $f(2)=1$. Therefore, $P(2)$ leads to $f(1)\in\{1,2,3\}$. Hence, there are only three functions satisfying the condition, and they are listed below.

If $f(1)=1$, then $P(2)$ gives $f(3)=3$. Then, $P(3)$ gives $f(4)=3$. By induction on the positive integer $k$, we can easily see that $$f(2k-1)=2k-1\text{ and }f(2k)=2k-1$$ for every $k=1,2,3,\ldots$. In other words, $$f(n)=2\,\left\lfloor\frac{n}{2}\right\rfloor+1$$ for all $n\in\mathbb{Z}_{>0}$.

If $f(1)=2$, then $P(2)$ implies $f(3)=2$. Then, $P(3)$, $P(4)$, and $P(5)$ lead to $f(4)=5$, $f(5)=4$, and $f(6)=5$. It can be proven again by induction that $$f(3k-2)=3k-1\,,\,\,f(3k-1)=3k-2\,,\text{ and }f(3k)=3k-1$$ for all $k=1,2,3,\ldots$. In other words, $$f(n)=3\,\left\lceil\frac{n}{3}\right\rceil-1-\left\lfloor\frac{n\mod 3}{2}\right\rfloor$$ for $n=1,2,3,\ldots$.

If $f(1)=3$, then $P(1)$ gives $f(3)=1$. Then, $P(3)$, $P(4)$, and $P(5)$ yield $f(4)=5$, $f(5)=4$, and $f(6)=5$, respectively. We claim that, for all positive integers $k$, $$f(3k+1)=3k+2\,,\,\,f(3k+2)=3k+1\,,\text{ and }f(3k+3)=3k+2\,.$$ However, this claim can be easily verified by induction on $k$. Thus, $$f(n)=3\,\left\lceil\frac{n}{3}\right\rceil-1-\left\lfloor\frac{n\mod 3}{2}\right\rfloor$$ for $n=4,5,6,\ldots$, with $f(1)=3$, $f(2)=1$, and $f(3)=1$.

  • $\begingroup$ I got it. Thank you for your thorough solution. $\endgroup$
    – carat
    Sep 2, 2017 at 11:57
  • 1
    $\begingroup$ The $f(1)=3$ case does not look right: looks like a copy of the solution for $f(1)=2$. Indeed, I think one solution is $f(1)=3$, $f(2)=1$, $f(3)=1$, $f(4)=3$, $f(4m+k)=4m+f(k)$. $\endgroup$ Sep 2, 2017 at 14:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.