×

# 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
3 years, 2 months ago

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$$ ? · 3 years, 2 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$$? · 3 years, 2 months ago

Merci! :) · 3 years, 2 months ago

De rien! :) · 3 years, 2 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. · 3 years, 2 months ago

I don't understand spanish but this looks like the basic idea I had for my solution :) · 3 years, 2 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? · 3 years, 2 months ago

"f" es estrictamente creciente e inyectiva. · 3 years, 2 months ago

Pardon me, but I couldnt understand you. Can you kindly post in English? · 3 years, 2 months ago

Very good argument!! · 3 years, 2 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. · 3 years, 2 months ago

it's f(n)= n for all n>=2 · 3 years, 2 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?) · 3 years, 2 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$$.
· 3 years, 2 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. · 3 years, 2 months ago

$$f$$ is a function, is not necessarily a polynomial. Thus you can't talk about the degree of $$f$$. · 3 years, 2 months ago

Ah, I see. Thanks for pointing out my mistake. · 3 years, 2 months ago