chaotic_iak wrote: Suppose a function $f : \mathbb{Z}^+ \rightarrow \mathbb{Z}^+$ satisfies $f(f(n)) + f(n+1) = n+2$ for all positive integer $n$. Prove that $f(f(n)+n) = n+1$ for all positive integer $n$. 1) $f(2)=2$ and $f(3)=2$ and $f(4)=3$ =========================== $f(2)=3-f(f(1))$ and so $f(2)\in\{1,2\}$ If $f(2)=1$, then $f(3)=4-f(f(2))=4-f(1)$ implies $f(1)\in\{1,2,3\}$ but then : $f(1)=1$ $\implies$ $1=f(2)=3-f(f(1))=2$, impossible $f(1)=2$ $\implies$ $1=f(2)=3-f(f(1))=3-f(2)=2$, impossible $f(1)=3$ $\implies$ $1=f(2)=3-f(f(1))=3-f(3)$ and so $f(3)=2$, in contradiction with $f(3)=4-f(f(2))=4-f(1)=1$ So $f(2)=2$ $f(3)=4-f(f(2))=2$ $f(4)=5-f(f(3))=5-f(2)=3$ Q.E.D. 2) $f(1)=1$ and $\forall n\ge 2$ : $n\ge f(n)\ge 2$ =============================== $f(n+1)=n+2-f(f(n))\le n+1$ and so $f(n)\le n$ $\forall n\ge 2$ Let then $n\ge 2$ : if $f(n)\ge 2$, we get $f(f(n))\le f(n)\le n$ and so $f(n+1)=n+2-f(f(n))\ge 2$ And since $f(2)\ge 2$, we get $f(n)\ge 2$ $\forall n\ge 2$ But $2=f(2)=3-f(f(1))$ implies $f(f(1))=1$ and so $f(1)<2$ and so $f(1)=1$ Q.E.D. 3) $\forall n\ge 2$ $f(n)\in\{f(n-1),f(n-1)+1\}$ ============================== Suppose $f(k)\in\{f(k-1),f(k-1)+1\}$ $\forall k\in[2,n]$ with $n>ge 2$ If $f(n)=f(n-1)$, then $f(n+1)=n+2-f(f(n))=1+(n+1-f(f(n-1)))=1+f(n)$ If $f(n)=f(n-1)+1$ : since $f(n-1)+1\in[2,n]$, we get $f(f(n-1)+1)\in\{f(f(n-1)),f(f(n-1))+1\}$ and so : If $f(f(n-1)+1)=f(f(n-1))$ : $f(n+1)=n+2-f(f(n))$ $=n+2-f(f(n-1)+1)$ $=n+2-f(f(n-1))$ $=1+f(n)$ If $f(f(n-1)+1)=f(f(n-1))+1$ : $f(n+1)=n+2-f(f(n))$ $=n+2-f(f(n-1)+1)$ $=n+1-f(f(n-1))$ $=f(n)$ And so $f(n+1)\in\{f(n),f(n)+1\}$ And since $f(k)\in\{f(k-1),f(k-1)+1\}$ $\forall k\in[2,2]$, the induction gives the required result. Q.E.D. 4) $f(f(n)+n)=n+1$ $\forall n$ ==================== Simple induction : Property is true for $n=1$ : $f(f(1)+1)=f(2)=2$ If property is true for $n$, then : $f(n+1)\in\{f(n),f(n)+1\}$ If $f(n+1)=f(n)$, then : $f(f(n+1)+n+1)=f(n+1)+n+2-f(f(f(n+1)+n))$ $=f(n+1)+n+2-f(f(f(n)+n))$ $=f(n+1)+n+2-f(n+1)$ $=n+2$ If $f(n+1)=f(n)+1$, then : $f(f(n)+n+1)=f(n)+n+2-f(f(f(n)+n))$ $=f(n)+n+2-f(n+1)=n+1$ $f(f(n+1)+n+1)=f(n+1)+n+2-f(f(f(n+1)+n))$ $=f(n+1)+n+2-f(f(f(n)+n+1))$ $=f(n+1)+n+2-f(n+1)=n+2$ And so $f(f(n+1)+n+1)=n+2$ End of induction And so $\boxed{f(f(n)+n)=n+1}$ $\forall n\in\mathbb Z^+$ Q.E.D. 5)Alternative direct [magic] path ====================== It's possible to show that there is a unique function $f(x)$ matching all requirements and that $\boxed{f(x)=1+\left\lfloor\frac{2x}{1+\sqrt 5}\right\rfloor}$ matches all the requirements and so is this unique function. It remains then casework to show $f(f(n)+n)=n+1$ from the direct expression of $f(x)$ (note : solution based on benimath's solution for a similar problem here : http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2133084#p2133084 )