Let $f : \mathbb Z_{\geq 0} \to \mathbb Z_{\geq 0}$ be a function satisfying $f(1)=1$ and $$f\Biggl(f(x+1) + f\Bigl( x + f(x)\Bigr)\Biggr) = x+2$$ Then what is $f(10)$?

My teacher gave me this problem and I'm quite not sure how to solve this and looking for help here

  • 3
    @TonyMa How do you get $f(2)=2$? I thought I had shown that as well, but I lost the thread. If I plug $x=0$ in to the OP's functional equation I get $f(f(1)+f(f(0)))=f(1+f(f(0)))=2$ but how do we proceed from there? – lulu Feb 21 at 2:02
  • 1
    Can I know, $f(\dots)=x+2$ is forall $x\in\mathbb R$ or forall $x\in\mathbb Z$ or something? – Tony Ma Feb 21 at 3:03
  • 1
    If you find a solution, or if your teacher provides one, please come back and post it here. I really can't see anyway to attack the problem as it stands...if there is a clever trick, I'd like to see it. – lulu Feb 21 at 10:56
  • 2
    Well, if you are so inclined, post it below. The crowd here will check it out. – lulu Feb 22 at 15:27
  • 1
    Corresponding AoPS forum artofproblemsolving.com/community/c6h1607504. It clarifies that domain and codomain are $\mathbb{N}$. – Sil May 27 at 11:27

This is (a tad) trickier than it looks. Consider the function $\mathrm f:\Bbb N\mapsto\Bbb N$ given by $$\mathrm f(n)=\lfloor n\beta\rfloor+1,$$ where $\beta=\dfrac{\sqrt 5-1}2$ satisfies $\beta^2+\beta=1$.

Clearly $\mathrm f(1)=1$.

Claim: $\mathrm f(n+\mathrm f(n))=n+1$ for all $n\in\Bbb N$.

Since $\beta$ is irrational, $$n\beta<\lfloor n\beta\rfloor+1<n\beta+1,\quad\textrm{so that}\quad n\beta<\mathrm f(n)<n\beta+1.$$ Similarly $$(n+\mathrm f(n))\beta<\mathrm f(n+\mathrm f(n))<(n+\mathrm f(n))\beta+1.$$ Thus $$(n+n\beta)\beta<(n+\mathrm f(n))\beta<\mathrm f(n+\mathrm f(n))<(n+\mathrm f(n))\beta+1<(n+n\beta+1)\beta+1.$$

Since $(n+n\beta)\beta=n$ and $\beta<1$, this yields $$n<\mathrm f(n+\mathrm f(n))<n+2.$$ Therefore $\mathrm f(n+\mathrm f(n))=n+1$, proving the claim.

Replacing $n$ with $n+1$ in this, we see that $\mathrm f(n+1+\mathrm f(n+1))=n+2$, and replacing the first $n+1$ in the last identity with $\mathrm f(n+\mathrm f(n))$ finally gives $$\mathrm f(\mathrm f(n+\mathrm f(n))+\mathrm f(n+1))=n+2,$$ which means that $\mathrm f(n)$ satisfies the functional equation (and also the initial condition.)

(In no way does the above prove the uniqueness of this solution, but maybe someone else can have a go at that.)

The first few values of $\mathrm f(n)$ are seen in this table: $$\begin{array}{|c|*12{c|}} \hline n&1&2&3&4&5&6&7&8&9&10&11&12\\ \hline \mathrm f(n)&1&2&2&3&4&4&5&5&6&7&7&8\\ \hline \end{array}$$ Thus $\mathrm f(10)=7$.

Other interesting properties of $\mathrm f(n)$ are:

  • $\mathrm f(\mathrm f(n))+\mathrm f(n+1)=n+2$,
  • $\mathrm f(n+1)=\mathrm f(n)$ or $\mathrm f(n+1)=\mathrm f(n)+1$ for all $n$,
  • if $\mathrm g:\Bbb N\mapsto\Bbb N$ is defined by $\mathrm g(1)=1$ and $$\mathrm g(n+1)=\begin{cases}\mathrm f(n), & \textrm{if }\mathrm f(n+1)=\mathrm f(n);\\ \mathrm f(n)+n+1, & \textrm{if }\mathrm f(n+1)=\mathrm f(n)+1,\end{cases}$$ then $\mathrm g:\Bbb N\mapsto\Bbb N$ is a bijection, with $\mathrm g(\mathrm g(n))=n$ and for which $\mathrm g(1)+\mathrm g(2)+\dots+\mathrm g(n)$ is divisible by $n$ for all $n$.
  • Nice! Can we similarly show uniqueness? – asdf Aug 10 at 10:37

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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