# A functional equation in positive integers

This interesting problem comes from Belarus. Post your ideas, comments and solutions!

Problem Let $\mathbb{Z}^{+}$ be the set of positive integers. Does there exist a function $f: \mathbb{Z}^{+}\to \mathbb{Z}^{+}$ such that $f(f(n-1))=f(n+1)-f(n),$ for all $n\geq 2$ ?

Note by Jorge Tipe
5 years, 10 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

En español (aunque es fácil la traducción) :)

Problema Sea $\mathbb{Z}^{+}$ el conjunto de los enteros positivos. ¿Existe una función $f: \mathbb{Z}^{+}\to \mathbb{Z}^{+}$ tal que $f(f(n-1))=f(n+1)-f(n),$ para todo $n\geq 2$ ?

- 5 years, 10 months ago

En français:

Problème Soit $\mathbb Z^+$ l'ensemble des entiers positifs. Est-ce qu'une fonction $f:\mathbb Z^+\rightarrow\mathbb Z^+$ existe pour que: $f(f(n-1))=f(n+1)-f(n),$pour tout $n\ge2$?

- 5 years, 10 months ago

Merci! :)

- 5 years, 10 months ago

- 5 years, 10 months ago

De rien! :)

- 5 years, 10 months ago

$f(f(n-1))=f(n+1)-f(n) , f(f(n-1)) \in Z^+ → f(n+1)>f(n)$ $→ "f"$ es creciente e inyectiva $( f(1)

$f(n+1) = f(n) + f( f(n-1)) → f(n+1)>f(f(n-1)) → f(n-1)< n+1$

Entonces podemos llegar a:

$1 \leq f(1) < 3$

$2 \leq f(2) < 4$

$3 \leq f(3) < 5$

...

$n_0 \leq f(n_0) < n_0+2$

.....

$n \leq f(n) < n+2$

Supongamos que $f(n_0)=n_0 +1 →$ es fácil llegar a que

$f(n_0+1)=n_0+2$ ; $f(n_0+2)=n_0+3$ ; ...$f(n) = n+1$

Reemplazando en el dato: $f(f(n_0))=f(n_0+2)-f(n_0+1)$

$→ n_0 +2 = n_0 +3 - n_0 - 2 → n_0= -1$ (Absurdo)

Entonces no debe existir ningún $n_0$ en el cual $f(n_0)=n_0+1$

Por lo tanto podemos concluir que $f(n) = n$

Reemplanzado en el dato: $f(f(n-1))=f(n+1)-f(n)$ $n-1=n+1-n → n=2$ , donde notamos que no cumple para todo $n≥2$.

Por lo tanto no existe tal función.

- 5 years, 10 months ago

I don't understand spanish but this looks like the basic idea I had for my solution :)

- 5 years, 10 months ago

Is f inverible , because f(n+1)>f(f(n-1)) implies f(n-1)<n+1 only when the inverse of f exists right?

- 5 years, 10 months ago

"f" es estrictamente creciente e inyectiva.

- 5 years, 10 months ago

Pardon me, but I couldnt understand you. Can you kindly post in English?

- 5 years, 10 months ago

Very good argument!!

- 5 years, 10 months ago

Let $\text{deg}(f(n))=d$. We see that $d^2=d$; therefore $d=0,1$. Let us first consider the case $d=0$.

Let $f(n)=c$ for some constant $c$. We see that $c=c-c\implies c=0$; therefore our function is $f(n)=0$. However, the function must satisfy $f:\mathbb{Z}^+\rightarrow \mathbb{Z}^+$. Therefore this case does not work.

Now let's tackle the $d=1$ case.

Let us assume $f(n)=an+b$. We see that \begin{aligned}a(a(n-1)+b)+b=a(n+1)+b-(a(n)+b)&\implies a^2n-a^2+ab+b=an+a+b-an-b\\ &\implies a^2n-a^2+ab+b=a\end{aligned} We match coefficients, and see that $a=0$. Therefore the function is $f(n)=b$. However, this is a degree $0$ function, which we know does not yield any solutions. Therefore there $\boxed{\text{does not exist any functions}}$. $\Box$

In my opinion this problem was fairly easy compared to other #PeruMOTraining problems, which I typically cannot solve. Or I might just be getting smarter.

- 5 years, 10 months ago

$f$ is a function, is not necessarily a polynomial. Thus you can't talk about the degree of $f$.

- 5 years, 10 months ago

Ah, I see. Thanks for pointing out my mistake.

- 5 years, 10 months ago

This is precisely why the question seemed easy =P Although your solution shows that there exist no polynomial functions that satisfy the equation hence our function must be of some other form, i.e. exponential, logarithmic, etc...

- 5 years, 10 months ago

Since $f(n)$ is defined on the positive integers and returns a positive integer for $n \ge 2$, we have that operations contained within our function must always return positive integer values for any positive integer satisfying $n \ge$. We know that the sum/difference of positive integers results a positive integer. The type of function that may add/subtract positive integers are polynomial functions. "Daniel Liu" has already shown that $f(n)$ is not of the form $a_nx^{n}+a_{n-1}x^{n-1}+...+a_0$. Now what other operations always return positive integer values for positive integers? Division won't work because if we have a rational function of the form $\frac{P(n)}{Q(n)}$, where $Q(n)$ is not a factor of $P(n)$ (because then we would just get a polynomial instead of a rational function) and $Q(n)$ is non-constant, we will never always have a positive integer return since the denominator itself is not a factor of the numerator. We are only then left with the possibility of exponentiation as an operation that will always return a positive integer value as long as the base is a positive integer and the exponent is a non-negative integer. So let's now assume that $f(n)=a^n$, for some positive integer $a$. Then we have:

$a^{a^{n-1}}=a^{n+1}-a^n \implies a^{a^{n-1}} =a^n(a-1)$

Here we notice that $a \ne 1$ then to satisfy the equation we must have $a \ge 2$. We now continue to simplify the equation:

$\implies a^{\left(a^{n-1}-n \right)} =a-1 \implies a - a^{\left(a^{n-1}-n \right)} = 1$

It is now obvious that as $n \rightarrow \infty$, the L.H.S becomes negative which doesn't satisfy the equation since the R.H.S is $1$. This proves that $f(n) \ne a^n$ where $a$ is some positive integer. Hence there exist no such function $f(n)$ that satisfies the equation.

Q.E.D.

(Do you think the reasoning here suffices as a proof or do you need something more Jorge?)

- 5 years, 10 months ago

The problem is that a function not necessarily has a nice form like $x^n$, $ax+b$, $a^x$, etc. In order to define a function $f:\mathbb{Z}^{+}\to \mathbb{Z}^{+}$ you only need to define the values $f(1), f(2), f(3), \ldots$ and any choice of these numbers will define your function.

Some examples of functions $f:\mathbb{Z}^{+}\to \mathbb{Z}^{+}$ are:

• $f(n)=$ digit sum of $n$
• $f(n)=1$ if and only if $n$ is prime, otherwise $f(n)=2$.
• $f(n)=\left\lfloor \sqrt{2^n} \right\rfloor$
• $f(n)=$ number of digits of the number $5n+n^3$.

- 5 years, 10 months ago

it's f(n)= n for all n>=2

- 5 years, 10 months ago

This is not a difficult question.

We first note that since $f(n+1)-f(n)=f(f(n-1))>0$, thus $f(n+1)>f(n)$ and it is straightforward to deduce that $f$ is strictly increasing (which means that $f(a)>f(b)$ iff $a>b$). A consequence is that $f(n)\ge n$, since $f(n)\ge f(n-1)+1\ge ...\ge f(1)+(n-1)\ge n$.

Now we apply this fact: $f(n+1)-f(n)=f(f(n-1))\ge f(n-1)$. This is a hint that $f$ actually grows rather quickly. In fact, $f(n+1)\ge f(n)+f(n-1)>2f(n-1)$, and with a bit of induction we can show that $f(n)\ge (\sqrt{2})^{n-1}$.

However, $f$ really shouldn't be growing that quickly, since $f(f(n-1))=f(n+1)-f(n). Since $f$ is increasing, $f(n-1), or $f(n).

Merging the two results, we have that $(\sqrt{2})^{n-1}\le f(n), which clearly doesn't hold for some large enough $n$ since the exponential function will eventually overtake the linear function. Hence we attain a contradiction, and $f$ does not exist.

- 5 years, 10 months ago