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\) ?

## Comments

Sort by:

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

ProblemaSea \(\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\) ? – Jorge Tipe · 3 years agoLog in to reply

ProblèmeSoit \(\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\)? – Kenny Lau · 3 years agoLog in to reply

– Jorge Tipe · 3 years ago

Merci! :)Log in to reply

– Kenny Lau · 3 years ago

De rien! :)Log in to reply

問題令\(\mathbb Z^+\)為所有正整數的集合，問在\(f:\mathbb Z^+\rightarrow\mathbb Z^+\)的函數中，在\(n\ge2\)時：\[f(f(n-1))=f(n+1)-f(n)\]的函數存不存在？ – Kenny Lau · 3 years agoLog in to reply

\( 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(2)<(3)<..<f(n)) \)

\( 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. – Juanfelipe Crisostomo Ramos · 3 years ago

Log in to reply

– Michael Tong · 3 years ago

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

– Jit Ganguly · 3 years 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?Log in to reply

– Juanfelipe Crisostomo Ramos · 3 years ago

"f" es estrictamente creciente e inyectiva.Log in to reply

– Jit Ganguly · 3 years ago

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

– Ashar Tafhim · 3 years ago

Very good argument!!Log in to reply

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)<f(n+1)\). Since \(f\) is increasing, \(f(n-1)<n+1\), or \(f(n)<n+2\).

Merging the two results, we have that \((\sqrt{2})^{n-1}\le f(n)<n+2\), 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. – David Lin Kewei · 3 years ago

Log in to reply

it's f(n)= n for all n>=2 – Med Qadi · 3 years ago

Log in to reply

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?) – Muhammad Shariq · 3 years ago

Log in to reply

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

Log in to reply

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{align*}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{align*}\] 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. – Daniel Liu · 3 years ago

Log in to reply

– Jorge Tipe · 3 years ago

\(f\) is a function, is not necessarily a polynomial. Thus you can't talk about the degree of \(f\).Log in to reply

– Daniel Liu · 3 years ago

Ah, I see. Thanks for pointing out my mistake.Log in to reply

– Muhammad Shariq · 3 years 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...Log in to reply