6

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

Bart Michels
  • 26,355
dionxj8
  • 79
  • By substituting $x=0$ into second equation, $f(2)=2$. Sub. $x=1$, $f(4)=4. I am thinking how to continue from here. – Tony Ma Feb 21 '18 at 01:57
  • 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 '18 at 02:02
  • @lulu, Oh sorry I think I get wrong. I should really take a paper to solve seriously. Thx so much. – Tony Ma Feb 21 '18 at 02:05
  • @TonyMa Oh, no worries. Like I said, I also thought I had shown that but I no longer believe what I wrote. – lulu Feb 21 '18 at 02:05
  • Are you sure you aren't also given $f(0)$? As the problem stands, I can't think of any way to get started. Of course, I might be missing something. – lulu Feb 21 '18 at 02:14
  • I'm thinking the same. –  Feb 21 '18 at 02:15
  • Can I know the domain of $f$? I think it maybe( just maybe) easier if I know $f$ is defined on $\mathbb Z$, or even just knowing $f(10)$ is defined. – Tony Ma Feb 21 '18 at 02:27
  • 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 '18 at 03:03
  • @lulu no.. the problem only gives f(1)=1.. – dionxj8 Feb 21 '18 at 06:51
  • 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 '18 at 10:56
  • @lulu I already got a solution from my teacher's former student but I think it's wrong.... – dionxj8 Feb 22 '18 at 15:20
  • 2
    Well, if you are so inclined, post it below. The crowd here will check it out. – lulu Feb 22 '18 at 15:27
  • 1
    Corresponding AoPS forum https://artofproblemsolving.com/community/c6h1607504. It clarifies that domain and codomain are $\mathbb{N}$. – Sil May 27 '18 at 11:27

1 Answers1

2

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$.
urgrue
  • 131