A functional equation in positive integers

This interesting problem comes from Belarus. Post your ideas, comments and solutions!

Problem Let Z+\mathbb{Z}^{+} be the set of positive integers. Does there exist a function f:Z+Z+f: \mathbb{Z}^{+}\to \mathbb{Z}^{+} such that f(f(n1))=f(n+1)f(n),f(f(n-1))=f(n+1)-f(n), for all n2n\geq 2 ?

Note by Jorge Tipe
5 years, 9 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

En español (aunque es fácil la traducción) :)

Problema Sea Z+\mathbb{Z}^{+} el conjunto de los enteros positivos. ¿Existe una función f:Z+Z+f: \mathbb{Z}^{+}\to \mathbb{Z}^{+} tal que f(f(n1))=f(n+1)f(n),f(f(n-1))=f(n+1)-f(n), para todo n2n\geq 2 ?

Jorge Tipe - 5 years, 9 months ago

Log in to reply

En français:

Problème Soit Z+\mathbb Z^+ l'ensemble des entiers positifs. Est-ce qu'une fonction f:Z+Z+f:\mathbb Z^+\rightarrow\mathbb Z^+ existe pour que: f(f(n1))=f(n+1)f(n),f(f(n-1))=f(n+1)-f(n),pour tout n2n\ge2?

Kenny Lau - 5 years, 9 months ago

Log in to reply

Merci! :)

Jorge Tipe - 5 years, 9 months ago

Log in to reply

@Jorge Tipe 中文:

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

Kenny Lau - 5 years, 9 months ago

Log in to reply

@Jorge Tipe De rien! :)

Kenny Lau - 5 years, 9 months ago

Log in to reply

f(f(n1))=f(n+1)f(n),f(f(n1))Z+f(n+1)>f(n) f(f(n-1))=f(n+1)-f(n) , f(f(n-1)) \in Z^+ → f(n+1)>f(n) "f" → "f" es creciente e inyectiva (f(1)<f(2)<(3)<..<f(n)) ( f(1)<f(2)<(3)<..<f(n))

f(n+1)=f(n)+f(f(n1))f(n+1)>f(f(n1))f(n1)<n+1 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:

1f(1)<3 1 \leq f(1) < 3

2f(2)<42 \leq f(2) < 4

3f(3)<5 3 \leq f(3) < 5

...

n0f(n0)<n0+2 n_0 \leq f(n_0) < n_0+2

.....

nf(n)<n+2 n \leq f(n) < n+2

Supongamos que f(n0)=n0+1 f(n_0)=n_0 +1 → es fácil llegar a que

f(n0+1)=n0+2 f(n_0+1)=n_0+2 ; f(n0+2)=n0+3 f(n_0+2)=n_0+3 ; ...f(n)=n+1 f(n) = n+1

Reemplazando en el dato: f(f(n0))=f(n0+2)f(n0+1) f(f(n_0))=f(n_0+2)-f(n_0+1)

n0+2=n0+3n02n0=1 → n_0 +2 = n_0 +3 - n_0 - 2 → n_0= -1 (Absurdo)

Entonces no debe existir ningún n0 n_0 en el cual f(n0)=n0+1 f(n_0)=n_0+1

Por lo tanto podemos concluir que f(n)=n f(n) = n

Reemplanzado en el dato: f(f(n1))=f(n+1)f(n) f(f(n-1))=f(n+1)-f(n) n1=n+1nn=2 n-1=n+1-n → n=2 , donde notamos que no cumple para todo n2 n≥2 .

Por lo tanto no existe tal función.

Juanfelipe Crisostomo Ramos - 5 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 - 5 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 - 5 years, 9 months ago

Log in to reply

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

Juanfelipe Crisostomo Ramos - 5 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 - 5 years, 9 months ago

Log in to reply

Very good argument!!

Ashar Tafhim - 5 years, 9 months ago

Log in to reply

Let deg(f(n))=d\text{deg}(f(n))=d. We see that d2=dd^2=d; therefore d=0,1d=0,1. Let us first consider the case d=0d=0.

Let f(n)=cf(n)=c for some constant cc. We see that c=cc    c=0c=c-c\implies c=0; therefore our function is f(n)=0f(n)=0. However, the function must satisfy f:Z+Z+f:\mathbb{Z}^+\rightarrow \mathbb{Z}^+. Therefore this case does not work.

Now let's tackle the d=1d=1 case.

Let us assume f(n)=an+bf(n)=an+b. We see that a(a(n1)+b)+b=a(n+1)+b(a(n)+b)    a2na2+ab+b=an+a+banb    a2na2+ab+b=a\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=0a=0. Therefore the function is f(n)=bf(n)=b. However, this is a degree 00 function, which we know does not yield any solutions. Therefore there does not exist any functions\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 - 5 years, 9 months ago

Log in to reply

ff is a function, is not necessarily a polynomial. Thus you can't talk about the degree of ff.

Jorge Tipe - 5 years, 9 months ago

Log in to reply

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

Daniel Liu - 5 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 - 5 years, 9 months ago

Log in to reply

Since f(n)f(n) is defined on the positive integers and returns a positive integer for n2n \ge 2, we have that operations contained within our function must always return positive integer values for any positive integer satisfying nn \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)f(n) is not of the form anxn+an1xn1+...+a0a_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 P(n)Q(n)\frac{P(n)}{Q(n)}, where Q(n)Q(n) is not a factor of P(n)P(n) (because then we would just get a polynomial instead of a rational function) and Q(n)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)=anf(n)=a^n, for some positive integer aa. Then we have:

aan1=an+1an    aan1=an(a1)a^{a^{n-1}}=a^{n+1}-a^n \implies a^{a^{n-1}} =a^n(a-1)

Here we notice that a1a \ne 1 then to satisfy the equation we must have a2a \ge 2. We now continue to simplify the equation:

    a(an1n)=a1    aa(an1n)=1\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 nn \rightarrow \infty, the L.H.S becomes negative which doesn't satisfy the equation since the R.H.S is 11. This proves that f(n)anf(n) \ne a^n where aa is some positive integer. Hence there exist no such function f(n)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 - 5 years, 9 months ago

Log in to reply

The problem is that a function not necessarily has a nice form like xnx^n, ax+bax+b, axa^x, etc. In order to define a function f:Z+Z+f:\mathbb{Z}^{+}\to \mathbb{Z}^{+} you only need to define the values f(1),f(2),f(3),f(1), f(2), f(3), \ldots and any choice of these numbers will define your function.

Some examples of functions f:Z+Z+f:\mathbb{Z}^{+}\to \mathbb{Z}^{+} are:

  • f(n)=f(n)= digit sum of nn
  • f(n)=1f(n)=1 if and only if nn is prime, otherwise f(n)=2f(n)=2.
  • f(n)=2nf(n)=\left\lfloor \sqrt{2^n} \right\rfloor
  • f(n)=f(n)= number of digits of the number 5n+n35n+n^3.

Jorge Tipe - 5 years, 9 months ago

Log in to reply

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

Med Qadi - 5 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(n1))>0f(n+1)-f(n)=f(f(n-1))>0, thus f(n+1)>f(n)f(n+1)>f(n) and it is straightforward to deduce that ff is strictly increasing (which means that f(a)>f(b)f(a)>f(b) iff a>ba>b). A consequence is that f(n)nf(n)\ge n, since f(n)f(n1)+1...f(1)+(n1)nf(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(n1))f(n1)f(n+1)-f(n)=f(f(n-1))\ge f(n-1). This is a hint that ff actually grows rather quickly. In fact, f(n+1)f(n)+f(n1)>2f(n1)f(n+1)\ge f(n)+f(n-1)>2f(n-1), and with a bit of induction we can show that f(n)(2)n1f(n)\ge (\sqrt{2})^{n-1}.

However, ff really shouldn't be growing that quickly, since f(f(n1))=f(n+1)f(n)<f(n+1)f(f(n-1))=f(n+1)-f(n)<f(n+1). Since ff is increasing, f(n1)<n+1f(n-1)<n+1, or f(n)<n+2f(n)<n+2.

Merging the two results, we have that (2)n1f(n)<n+2(\sqrt{2})^{n-1}\le f(n)<n+2, which clearly doesn't hold for some large enough nn since the exponential function will eventually overtake the linear function. Hence we attain a contradiction, and ff does not exist.

David Lin Kewei - 5 years, 9 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...