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 ago
No vote yet
1 vote
Easy Math Editor
*italics*or_italics_**bold**or__bold__paragraph 1
paragraph 2
[example link](https://brilliant.org)> This is a quote# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"2 \times 32^{34}a_{i-1}\frac{2}{3}\sqrt{2}\sum_{i=1}^3\sin \theta\boxed{123}Comments
Sort by:
Top NewestEn 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\) ?
Log in to reply
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\)?
Log in to reply
Merci! :)
Log in to reply
中文：
問題令\(\mathbb Z^+\)為所有正整數的集合，問在\(f:\mathbb Z^+\rightarrow\mathbb Z^+\)的函數中，在\(n\ge2\)時：\[f(f(n-1))=f(n+1)-f(n)\]的函數存不存在？
Log in to reply
De rien! :)
Log 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.
Log in to reply
I don't understand spanish but this looks like the basic idea I had for my solution :)
Log in to reply
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
"f" es estrictamente creciente e inyectiva.
Log in to reply
Pardon me, but I couldnt understand you. Can you kindly post in English?
Log in to reply
Very good argument!!
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.
Log in to reply
\(f\) is a function, is not necessarily a polynomial. Thus you can't talk about the degree of \(f\).
Log in to reply
Ah, I see. Thanks for pointing out my mistake.
Log in to reply
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
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?)
Log in to reply
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:
Log in to reply
it's f(n)= n for all n>=2
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.
Log in to reply