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$ ?

$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.

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.

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

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

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.