A functional equation in positive integers

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\) ? – Jorge Tipe · 3 years, 6 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(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, 6 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)<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, 6 months ago

it's f(n)= n for all n>=2 – Med Qadi · 3 years, 6 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?) – Muhammad Shariq · 3 years, 6 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{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, 6 months ago