# Sequence : $f(f(n))+f(n+1)=2n$

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$

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$.

• I got it. Thank you for your thorough solution. Sep 2, 2017 at 11:57
• 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)$. Sep 2, 2017 at 14:54