Waste less time on Facebook — follow Brilliant.
×

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, 9 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

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, 9 months ago

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

Kenny Lau - 3 years, 9 months ago

Log in to reply

Merci! :)

Jorge Tipe - 3 years, 9 months ago

Log in to reply

@Jorge Tipe De rien! :)

Kenny Lau - 3 years, 9 months ago

Log in to reply

@Jorge Tipe 中文:

問題令\(\mathbb Z^+\)為所有正整數的集合,問在\(f:\mathbb Z^+\rightarrow\mathbb Z^+\)的函數中,在\(n\ge2\)時:\[f(f(n-1))=f(n+1)-f(n)\]的函數存不存在?

Kenny Lau - 3 years, 9 months ago

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.

Juanfelipe Crisostomo Ramos - 3 years, 9 months ago

Log in to reply

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

Michael Tong - 3 years, 9 months ago

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?

Jit Ganguly - 3 years, 9 months ago

Log in to reply

@Jit Ganguly "f" es estrictamente creciente e inyectiva.

Juanfelipe Crisostomo Ramos - 3 years, 9 months ago

Log in to reply

@Juanfelipe Crisostomo Ramos Pardon me, but I couldnt understand you. Can you kindly post in English?

Jit Ganguly - 3 years, 9 months ago

Log in to reply

Very good argument!!

Ashar Tafhim - 3 years, 9 months ago

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, 9 months ago

Log in to reply

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

Med Qadi - 3 years, 9 months 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, 9 months ago

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:

  • \(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\).

Jorge Tipe - 3 years, 9 months ago

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, 9 months ago

Log in to reply

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

Jorge Tipe - 3 years, 9 months ago

Log in to reply

Ah, I see. Thanks for pointing out my mistake.

Daniel Liu - 3 years, 9 months ago

Log in to reply

@Daniel Liu 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...

Muhammad Shariq - 3 years, 9 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...