13

Find all functions $f$ such that $f:\mathbb{N}\rightarrow\ \mathbb{N}$ and $f(f(n))+f(n+1)=n+2$

Let us plug in $n=1$

$f(f(1))+f(2)=3$

Since the function is from $\mathbb{N}$ to $\mathbb{N}$, $f(2)$ can only take the values $1,2$. Now we divide the problem into cases.

Case-1: $f(f(1))=2,f(2)=1$

We can assume that $f(1)=c$ for the time being. Then plugging in $n=3$ and using $f(2)=1$ gives $$f(3)=4-c$$ and again since the range of the function is positive integers,then $4-c$ has to be positive and hence $c$ belongs to {$1,2,3$}. Now, $$f(1)=c$$$$\implies f(f(1))=f(c)$$$$\implies 2=f(c)$$ by the assumption that $f(f(1))=2$ . Now,since $c$ can only take the values $1,2,3$,we start treating cases. If $c=1$,$$f(c)=2$$$$\implies f(1)=2$$ but we know from the deinition of $c$ that $f(1)=c=1$,a contradiction.If $c=2$,then $2=f(c)=f(2)$ but $f(2)=1$ by assumption. Finally,if $c=3$ $$2=f(c)=f(3)$$ but $$f(3)=4-c=4-3=1$$ which is once again a contradiction. Therefore there are no such functions in this case.

Case-2: $f(f(1))=1,f(2)=2$

Again assuming $f(1)=c$ and using $f(n)\le n$ along with plugging $n=c-1$ will give us that $f(1)=1$ and then it is easy to prove that such a function exists by recursion. I can only give a "sort of recursive" way to define the function. Here it goes $$f:\mathbb{N}\rightarrow \mathbb{N}$$$$f(1)=1$$$$f(n)=n+1-f(f(n-1))$$

But this case is harder to deal with.Some help will be appreciated.

rah4927
  • 3,864
  • Also,the first few values starting from n=1 are $1,2,2,3,4,4,5,5,6,7,7,8,9,9,10$. I have tried proving that the function is non-decreasing,but have failed.It is perhaps too much to say the values don't follow any pattern,but I cannot see any pattern that will help me find a closed form expression.It might also help to prove that the function is surjective(onto). – rah4927 Jan 09 '15 at 17:52
  • 2
    OEIS is your friend! OIES A019446 $a(n) = \left\lceil \frac{n}{\phi} \right\rceil$ where $\phi = \frac{1+\sqrt{5}}{2}$ is the golden ration matches your sequence (at least up to $n = 100$). – achille hui Jan 09 '15 at 18:27
  • 2
    Since you are asked to "find all functions $f$", isn't it sufficient to show that there is only one such function, and it is uniquely determined by the given recursion? (The fact that the recursion works follows from $f(n)\le n$, which is easily proved via induction.) –  Jan 09 '15 at 18:27
  • @Rahul,yes it is.But I am extremely curious how we could have come up with the achille hui's OEIS solution above. – rah4927 Jan 09 '15 at 18:32
  • @achille,interesting.I suppose the presence of a floor or ceiling was expected,given the nature of the values.Any ideas how we could have come up with it?Thanks for the OEIS link btw. – rah4927 Jan 09 '15 at 18:34
  • @Rahul,btw,induction is an overkill.Just note that $f(n+1)=n+2-f(f(n))\le n+2-1=n+1$. – rah4927 Jan 09 '15 at 18:37
  • @rah4927 No idea. However, one of the ref there does mention this sequence is a solution of your last recurrence relation. (by Benoit Cloitre, Nov 06 2002) – achille hui Jan 09 '15 at 18:40
  • Problem 11651 of the American Mathematical Monthly is closely related to your problem (see the solution here). Also, see this paper. – Matemáticos Chibchas Jan 09 '15 at 18:56
  • As noted, we get for all $n>1$:$$(i);f(n) = n+1 -f(f(n-1))\le n+1 - 1 = n$$Since $f(f(1))+f(2)=3$, there must be some $n\in\mathbb{N}$ such that $f(n) > 1$. For that $n$, we get:$$ (ii);f(n+1) = n + 2 -f(f(n))\ge n+2-f(n) \ge 2$$ So that $f(n+1)$ is also $>1$. We conclude that if $f(n) > 1$ holds for some $n$, the it also holds for all integers greater that $n$. This implies that $f(1)=1$, since otherwise, we would have both $f(2)\ge2$, and $f(f(1))\ge2$ - a contradiction. Note that $(ii)$ may be rewritten as:$$f(n)+f(n+1) \ge n+2$$However, by $(i)$ we also have:$$f(n)+f(n+1)\le2n+1$$ – SomeStrangeUser Jan 09 '15 at 20:07
  • @achillehui,I don't know if there is a proper way to figure out the closed form expression of the function.Any ideas how we can prove that the closed form expression does follow the recurrence? – rah4927 Jan 12 '15 at 15:50
  • @rah4927 I have added an answer which shows $\left\lceil \frac{n}{\phi}\right\rceil$ is a solution of the functional equation. – achille hui Jan 12 '15 at 17:45

2 Answers2

4

This answer doesn't attempt to solve following functional equation from first principle.

$$f(n+1) + f(f(n)) = n+2,\quad\text{ for } n \ge 1\tag{*1}$$

Instead, it verify the function $\left\lceil \frac{n}{\phi}\right\rceil$ appeared in OEIS A019446 is a solution of $(*1)$.

For any fixed $n \ge 1$, since $\phi$ is irrational, there exists 3 numbers $\epsilon_1,\epsilon_2,\epsilon_3 \in (0,1)$ such that: $$ \left\lceil \frac{n+1}{\phi} \right\rceil = \frac{n+1}{\phi} + \epsilon_1, \quad \left\lceil \frac{n}{\phi} \right\rceil = \frac{n}{\phi} + \epsilon_2, \quad\text{ and }\quad \left\lceil\frac{1}{\phi}\left\lceil \frac{n}{\phi} \right\rceil\right\rceil = \frac{1}{\phi}\left\lceil \frac{n}{\phi} \right\rceil + \epsilon_3 $$

Substitute this into $(*1)$, this is equivalent to showing:

$$\left( \frac{n+1}{\phi} + \epsilon_1 \right) + \frac{1}{\phi}\left(\frac{n}{\phi} + \epsilon_2\right) + \epsilon_3 \stackrel{?}{=} n + 2 \iff ( \frac{1}{\phi} + \epsilon_1 ) + \frac{\epsilon_2}{\phi} + \epsilon_3 \stackrel{?}{=} 2 $$ There are two possible cases:

  • If $\epsilon_2 < \frac{1}{\phi}$,

$$\frac{n+1}{\phi} > \left\lceil\frac{n}{\phi}\right\rceil \implies \frac{1}{\phi} + \epsilon_1 = \epsilon_2 + 1 \implies \left( \frac{1}{\phi} + \epsilon_1 \right) + \frac{\epsilon_2}{\phi} = \phi \epsilon_2 + 1 \in (1,2) $$

  • If $\epsilon_2 \ge \frac{1}{\phi}$, $$\frac{n+1}{\phi} \le \left\lceil\frac{n}{\phi}\right\rceil \implies \frac{1}{\phi} + \epsilon_1 = \epsilon_2 \implies \left( \frac{1}{\phi} + \epsilon_1 \right) + \frac{\epsilon_2}{\phi} = \phi\epsilon_2 \in [1,\phi) $$

In both cases, since $\epsilon_3 \in (0,1)$, we have $$\left( \frac{1}{\phi} + \epsilon_1 \right) + \frac{\epsilon_2}{\phi} \in [1,2) \implies \left( \frac{1}{\phi} + \epsilon_1 \right) + \frac{\epsilon_2}{\phi} + \epsilon_3 \in (1,3) $$ Since by construction, the LHS of this expression is an integer, it has to be $2$ and hence $(*1)$ is satisfied.

achille hui
  • 122,701
3

So we start by the fact that $f(k) ≤ k$ for any $k$ and we can determine using strong induction on $n$ the value of $f (n)$ : if we have known $f(1),f(2),...,f(k)$ then by setting $n = k + 1$ we compute $f(k + 1)$. (This is already mentioned above)

But this (strong induction) implies that $f$ is defined uniquely

And, as was shown in the first answer, The function $f(x) = [cx]+1 $ where $c = \frac{√5−1}{ 2}$ is a solution, hence it's the only solution.

Community
  • 1
Elaqqad
  • 13,725