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.
Markdown
Appears as
*italics* or _italics_
italics
**bold** or __bold__
bold
- bulleted - list
bulleted
list
1. numbered 2. list
numbered
list
Note: you must add a full line of space before and after lists for them to show up correctly
Let deg(f(n))=d. We see that d2=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⟹c=0; therefore our function is f(n)=0. However, the function must satisfy f:Z+→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 a(a(n−1)+b)+b=a(n+1)+b−(a(n)+b)⟹a2n−a2+ab+b=an+a+b−an−b⟹a2n−a2+ab+b=a 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 does not exist any functions. □
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
–
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...
Since f(n) is defined on the positive integers and returns a positive integer for n≥2, we have that operations contained within our function must always return positive integer values for any positive integer satisfying n≥. 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 anxn+an−1xn−1+...+a0. 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 Q(n)P(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)=an, for some positive integer a. Then we have:
aan−1=an+1−an⟹aan−1=an(a−1)
Here we notice that a=1 then to satisfy the equation we must have a≥2. We now continue to simplify the equation:
⟹a(an−1−n)=a−1⟹a−a(an−1−n)=1
It is now obvious that as n→∞, the L.H.S becomes negative which doesn't satisfy the equation since the R.H.S is 1. This proves that f(n)=an 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?)
The problem is that a function not necessarily has a nice form like xn, ax+b, ax, etc. In order to define a function f:Z+→Z+ you only need to define the values f(1),f(2),f(3),… and any choice of these numbers will define your function.
Some examples of functions f:Z+→Z+ are:
f(n)= digit sum of n
f(n)=1 if and only if n is prime, otherwise f(n)=2.
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)≥n, since f(n)≥f(n−1)+1≥...≥f(1)+(n−1)≥n.
Now we apply this fact: f(n+1)−f(n)=f(f(n−1))≥f(n−1). This is a hint that f actually grows rather quickly. In fact, f(n+1)≥f(n)+f(n−1)>2f(n−1), and with a bit of induction we can show that f(n)≥(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 (2)n−1≤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.
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:
*italics*
or_italics_
**bold**
or__bold__
paragraph 1
paragraph 2
[example link](https://brilliant.org)
> This is a quote
\(
...\)
or\[
...\]
to ensure proper formatting.2 \times 3
2^{34}
a_{i-1}
\frac{2}{3}
\sqrt{2}
\sum_{i=1}^3
\sin \theta
\boxed{123}
Comments
Sort by:
Top NewestEn español (aunque es fácil la traducción) :)
Problema Sea Z+ el conjunto de los enteros positivos. ¿Existe una función f:Z+→Z+ tal que f(f(n−1))=f(n+1)−f(n), para todo n≥2 ?
Log in to reply
En français:
Problème Soit Z+ l'ensemble des entiers positifs. Est-ce qu'une fonction f:Z+→Z+ existe pour que: f(f(n−1))=f(n+1)−f(n),pour tout n≥2?
Log in to reply
Merci! :)
Log in to reply
問題令Z+為所有正整數的集合,問在f:Z+→Z+的函數中,在n≥2時:f(f(n−1))=f(n+1)−f(n)的函數存不存在?
Log in to reply
Log in to reply
f(f(n−1))=f(n+1)−f(n),f(f(n−1))∈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≤f(1)<3
2≤f(2)<4
3≤f(3)<5
...
n0≤f(n0)<n0+2
.....
n≤f(n)<n+2
Supongamos que f(n0)=n0+1→ es fácil llegar a que
f(n0+1)=n0+2 ; f(n0+2)=n0+3 ; ...f(n)=n+1
Reemplazando en el dato: f(f(n0))=f(n0+2)−f(n0+1)
→n0+2=n0+3−n0−2→n0=−1 (Absurdo)
Entonces no debe existir ningún n0 en el cual f(n0)=n0+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.
Log in to reply
I don't understand spanish but this looks like the basic idea I had for my solution :)
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?
Log in to reply
Log in to reply
Log in to reply
Very good argument!!
Log in to reply
Let deg(f(n))=d. We see that d2=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⟹c=0; therefore our function is f(n)=0. However, the function must satisfy f:Z+→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 a(a(n−1)+b)+b=a(n+1)+b−(a(n)+b)⟹a2n−a2+ab+b=an+a+b−an−b⟹a2n−a2+ab+b=a 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 does not exist any functions. □
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.
Log in to reply
f is a function, is not necessarily a polynomial. Thus you can't talk about the degree of f.
Log in to reply
Ah, I see. Thanks for pointing out my mistake.
Log in to reply
Log in to reply
Since f(n) is defined on the positive integers and returns a positive integer for n≥2, we have that operations contained within our function must always return positive integer values for any positive integer satisfying n≥. 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 anxn+an−1xn−1+...+a0. 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 Q(n)P(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)=an, for some positive integer a. Then we have:
aan−1=an+1−an⟹aan−1=an(a−1)
Here we notice that a=1 then to satisfy the equation we must have a≥2. We now continue to simplify the equation:
⟹a(an−1−n)=a−1⟹a−a(an−1−n)=1
It is now obvious that as n→∞, the L.H.S becomes negative which doesn't satisfy the equation since the R.H.S is 1. This proves that f(n)=an 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?)
Log in to reply
The problem is that a function not necessarily has a nice form like xn, ax+b, ax, etc. In order to define a function f:Z+→Z+ you only need to define the values f(1),f(2),f(3),… and any choice of these numbers will define your function.
Some examples of functions f:Z+→Z+ are:
Log in to reply
it's f(n)= n for all n>=2
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)≥n, since f(n)≥f(n−1)+1≥...≥f(1)+(n−1)≥n.
Now we apply this fact: f(n+1)−f(n)=f(f(n−1))≥f(n−1). This is a hint that f actually grows rather quickly. In fact, f(n+1)≥f(n)+f(n−1)>2f(n−1), and with a bit of induction we can show that f(n)≥(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 (2)n−1≤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.
Log in to reply