at the point (a²-a)(x+y)+2ab-b=1 you could already argue that the coefficient of (x+y) must be 0 because the rest of the equation are constants and hence a²=a --> a=0 or a=1. since a=0 would give us a constant function, a=1 is the only valid option
@@mohammadzaeriamirani7776 that is not what i said. it literally doesn't matter what b is at this point as long as it's a constant. x and y are the only variables and since the equation is supposed to hold for any x and y, the coefficient of x+y must be 0. b just follows from that observation about a
17:53 It is never too late to start working towards your dreams. Forget about the past, it does not define your future. What defines is what you do today. Happy Friday!
Exactly! I was literally screaming that and I don't know why he didn't mention that at all. You can take the inverse of both sides, as long as f-inv is possible, which ends up being such a straightforward solution
@@MattiaBelletti once you get to f(x) = ax + b we know f is injective (because only the case a=0 would be non-injective and constant functions are ruled out in the statement of the problem)
The extra rigour (showing g(x) is constant for integer x) demonstrates the solution is exhaustive. Perhaps the solution was longer than necessary, but it was complete.
In the first proposed substitution 4:16, one can replace every f(y) by x, which leads to « f(0) = f(f(x)) -x -1 ». True for ar least one x, but more than one since we know the f() is not constant and x is f(y). Since -for those x- f(f(x)) = x plus a constant, it very strongly hints at some linear function.
When I see something like 9:46 my first thought is to immediately do a sum. Notice that if the sum the left hand side of the equation you would get a telescoping series, and you can easily sum up the right hand side as well. I would sum both sides from t (the value at which f(t) is -1) to x and go from there
This video excels in something that many videos on similar topics fail to convey (the most prominent example being the videos by MindYourDecisions). While most videos will present a neat and tidy way to solve the problem at hand, you actually take the time to go over the thought process involved in solving problems like this, making it clear that this problem is not at all trivial to solve. In my opinion, this aspect alone makes this video much more worthwhile than most others like it.
Great solution. I think you already arrived at the solution at time index 6:43 but maybe didn't notice it. You arrived at the result f (x+1) = f (f (x)) From that it necessarily follows that x+1 = f (x) because the nature of the function f(x) as defined always returns the same value for any given x in Z
We’d have to prove that f is injective (one-to-one), because if we don’t there’s still the possibility that x+1 and f(x) are different but happen to output the same integer when run through f again.
A rigorous argument is: from the t-substitution we know that f(f(x))=f(x+1) from the initial substitution f(y)=x used the other way we know that f(f(x))=x+1+f(0) Combining both follows that f(x+1)=x+1+f(0), or f(x)=x+f(0). To find f(0) replace x with f(x) and get f(f(x))=f(x)+2f(0) and equating with the other expression for f(f(x) we get f(0)=1.
At 7:00 it might have been clearer to introduce a new variable name. It's not immediately clear that the "x" on the LHS is a new "x" being defined in terms of the old "x".
There's a gap at 9:45. You specialize x = f(x')-1, y=x' and then conclude that f(x+1)-f(x)=const (which is fine); but then you conclude f(x+1)-f(x)=const for all x, which doesn't work unless f is surjective.
Setting x=0, f(-f(y)) = f(f(0)) -f(y)-1. Since f(y) is an integer (say z), this gives f(-z)=f(f(0)) -z -1. Then f(z) = z + f(f(0)) -1 let f(f(0))=k (a constant). Then, f(z) = z + k -1 (Equation 1) Substituting z =0, f(0) = k - 1 f(f(0)) = k - 1 + k - 1 = 2k -2 but, f(f(0))= k by definition, hence k = 2k -2 (i.e.) k = 2. Substituting k=2 in Equation 1 gives f(z)=z+1 And, that's a good place to stop.
You could set x=-1 so that it has the form f(u)=f(f((-1))+u where u= -f(y)-1. So we see it has the form u+a. Now plug that like michael back in the functional equation and you would get x+1=f(x)
At 13:30 you could also use that with x=0 and y=0 you get that f(-f(0))=f(f(0))-f(0)-1=f(1)-f(0)-1=f(-1)+1-1=f(-1) and use that the function is injective so -f(0)=-1 -> f(0)=1=f(-1)+f(-1)+1 -> f(-1)=0 since the "gradient" is f(-1)+1 by 9:00. Just to avoid the a and b mess.
another way to argue why f(x+1)-f(x)=a leads to linearity is as follows: since f(x+1)-f(x)=a we apply sigma on both sides taking limits from x=0 to x=y-1(y is an arbitrary integer) note that when we sum from 0 to y-1 then many terms cancel each other out giving us f(y)=ay+f(0) setting f(0)=b we get that f(y)=ay+b for all y€Z so f must be linear.
To prove f(x+1)-f(x) = a implies f(x) = mx + p there is a much shorter way to do : You let x = k and you take the sum k = 0 to n-1 on both sides. On the RHS you get na because a is constant and on the LHS, this is a telescoping sum, simplifying to f(n) - f(0). Then you obtain the general form of f(x), and conclude.
At 3:40 you got to "f(something) = -1". You missed that since it is (from the problem definition) a non constant function, the "something" must be constant in order for f(something) to be constant. So then we can say: something = x-f(f(x)) = -k Or: f(f(x))=x+k and f(f(0)) = k Going back to y=free,x=f(y) we can easily derive f(f(f(0))) = 1, aka f(k) = 1 From the original equation, we can let x=free,y=k and get: f(x-f(k)) = f(f(x)) - f(k) - 1 Substituting f(k)=1 and f(f(x)=x+k we get: f(x-1) = x + k - 2 From there it is pretty simple to derive the final answer.
At 7:20 he set x = f(x)-1, y as x and he gets a = f(-1) + 1 = f(x+1) - f(x). So if I'm not wrong, this conclusion is specific to x where x = f(x)-1 and y = x But on the next clip he use f(x+1) - f(x) = a for all x in Z, so I'm a bit confused. Since we didn't know that f(x) is 1 to 1, we couldn't concludes x = f(x) - 1 from f(x+1) = f(f(x)). Is there a way to proof x = f(x) - 1 for all x or did I overlooked something?
If it helps to make it less confusing, pick an arbitrary value for c, and set x = f(c) - 1 and y to c. The functional equation must be true for this choice of x and y since it must be true for every x and y. The conclusion that you then get is that f(-1) + 1 = f(c + 1) - f(c) for every value of c. When he says "Take x = f(x) - 1", the x on the LHS is the x in the functional equation, while the x on the RHS is a free variable. People often write this way when presenting solutions for functional equations, but it can be confusing. Another style that is possibly less confusing that people sometimes use is to start the solution with "Let P(x, y) be the statement f(x - f(y)) = ...", and then instead of saying "Set x = f(x) - 1, and y = x", they'll instead write "Since P(f(x) - 1, x) is true, we have that ... and so f(-1) + 1 = f(x + 1) - f(x) for all x".
I have a question, what if we can't assume the image of f() is all integers? I set y=f^(-1)(0) so f(y)=0 f(x) = f(f(x))-1 x2 = f(x) x2 = f(x2)-1 so f(x) = x+1 I assumed f^(-1)(0) exists. What if there wasn't? Does there exist a different function where the image is not all ints?
You can also let x free and set y such that f(y)=-1. then we have directly f(f(x))=f(x)+1 for all x so f(x)=x+1. we can then verify of course that there is a y such that f(y)=-1.
In 6:46 the solution is already there: f(x+1)=f(f(x)) ! Just apply f^-1 on both sides => f(x)=x+1. One has just to prove that it is indeed a solution. Invertability is not even necessary to prove. But that’s easy. Just insert. Remains to prove it’s the only solution.
If x = f(y) => f(0) = f^3(y) - f(y) - 1 f^3(y) - f(y) = f(0) + 1 (this value must be constant) Since the difference is a constant, the function can't exclude any integer as a result, so f(x) in general = x + n. Letting f(y) = 0 (which is thus possible), it follows that f(x) = f^2(x) - 1 => f(x) = x+1.
Set x=f(y), then, by rearranging the terms we get f(f(x))=x+1+f(0). f(f(x)) is linear, which implies that f(x) is linear as well (does that need a proof?). Thus there exists a "y" such that f(y)=0. We can substitute it back in to the original equation. f(x)=f(f(x))-1. Set t=f(x) and we have f(t)=t+1 and that's a good place to stop
Here, a = f(x+1) - f(x) so a must be an integer. Thus, b must also be an integer since we posit that f(x) = ax+b and if b is not an integer then f(x) has non-integer values.
Mostly its about trial and error. U can guess the magic values of x and y by looking at the structure of eq.(try to guess what values would simplify it)
I took hours doing many substitutions, cases and combining equations. In the end I only managed to proof that there are two solutions, f(x) =x+1 and f(x) =-1, which are the only ones of the form ax+b and that assuming 0 in im(f), the only solution is x+1. I then kind of worked into the right direction, but never did the clever substitution x=f(v) - 1
if we put y= f(x) f(x-f(f(x)))= f(f(x)) - f(f(x)) -1 = -1 f(x-f(f(x))) = -1 let g(x) = x - f(f(x)) f(g(x))= -1 since it is given that f:Z > Z is non constant function so g(x) must be constant so, x - f(f(x)) = constant that means f(f(x)) = x + b where b is any constant
I did some of solution which is not at all good as per my side Let x=0 and y=0 f(-f(0))=f(f(0))-f(0)-1 Next let x=0 y=y f(-f(y))=f(f(0)) - f(y) -1 Let -f(y) = a Then f(a) = f(f(0)) - a - 1 Taking this as a general equation And then let a=0 f(0) = f(f(0)) - 1 f(0) + 1 = f(f(0)) Let f(0) = b Now b + 1 = f(b) And now taking this as a general rule , f(0) = 1 And so on, and putting this into the original equation, it satisfies the equation
I'm slightly confused, the question doesn't seem to limit x and y to a dependency, as far as it's concerned they are freely independent variables. Does the assumption that one is the function applied to the other not limit the potential solutions?
From f(x)=ax+b, a non-zero, we know f is injective (do not say invertible because the domain of f is not rational number). Then apply injectivity to f(f(x))=f(x+1) to get f(x)=x+1. Then verify this satisfies the original equation.
Couldn't you set some variable a = x - f(y), and get the functional equation: f(a) = f(f(x)) + a - x - 1 Then choose a = x, getting: f(f(x)) = f(x) + 1 Then we can easily see that: f(a) - a = f(x) - x Then let a = 0: f(x) = f(0) + x Now you simply plug this into our given equation to find f(0) = 1, and therefore f(x) = x + 1? Is this solution valid?
What's wrong with simplifying by subbing in x=-1 at the start, then defining a variable z=-1-f(y)? Have I overly constrained to solutions where f(-1) is defined, or something?
I first assume that it is linear so I can take the f(y) out of the outer function and cancel it. What is left is f(x)+1=f(f(x)). Change the variable to u=f(x) leaves behind f(u)=u+1. How to find whether it is linear is out of my reach. Also, I don't know how to make sure it is the only solution.
X=0, then we have f(-f(y))=f(f(0))-f(y)-1 Giving u=-f(y) and knowing that c=f(f(0))-1 is a constant, we derive f(u)=u+c Putting that in the main equation: (x-(y+c))+c=((x+c)+c)-(y+c)-1 Then: x-y-c+c=x+2c-y-c-1 x-y=x-y+c-1 Therefore c=1 So... F(x)=x+1
Not sure if I just got lucky or if this is even valid. I assumed that f(x) had a zero at some value. I set y to that arbitrary value, simplifying it to f(x) = f(f(x)) - 1. Then, set x=0 to show that f(0) = f(f(0)) - 1. Set a = f(0). This becomes a = f(a) - 1. Substitute x for a. f(x) = x + 1.
I think f(x)=-1 would be only constant function solution if you did not exclude constant functions at outset. Also, assuming f(x) is a polynomial, would force f(x) = mx + b because of degree clashes. For example, suppose degree of f is two, then f(f(x)) on RHS is degree 4 and there are no x^4 term on LHS. This is a little slippery since polynomials in the variables x and y are present. Also f(x) a rational function or function involving radicals sure don't seem like they would work in the absence of a rigorous proof. Using f(x) = mx + b and the well known polynomial result of equating coefficients leads to m=b=1
How could x-f(f(x)) only be an integer for a single value of x? We know that f goes from the integers to the integers, so that term is just a subtraction of integers and itself an integer.
Very few people really understand what it takes to make that thumbnail, and I appreciate your courage to do so. I don't even know what to say but just...you're the best, man. Edit: He may just get himself banned from China government by publishing that thumbnail.
Wait a sec. At 6:47 we see that f(x+1)=f(f(x). But isn't this only when y=t and f(t)= -1 ? So is it valid to then say at 8:42 that f(f(u))=f(u+1) when this was derived from the new value of y=x ?
I noticed that and assumed (probably incorrectly) that the arguments of the outer f() must be equal, so (x+1) = (f(x)). I'm sure Michael was just more thorough ...
We know that there is 𝘴𝘰𝘮𝘦 value of T such that F(T) = -1. At this point in the video, we don't know what it is, but we know that it exists. Substituting that into the original functional equation tells us that F( X+1 ) = F( F(X) ). This new identity is true for all values of X.
At 7:15, when you assume that x=f(x)-1, isn't that circular reasoning? You just assumed that f(x)=x+1 by doing that, and that assumption rules out all other possible solution functions. At 14:00 you have a good proof that any linear function that solves the original equation must be the f(x)=x+1 equation, but that isn't sufficient to solve the original question of "what are all functions that solve the original equation?"
7:15 when you replace x = f(x) -1 ..... Isn't that saying that f(x) = x + 1 , but supossely You still don't know what the function f(x) your looking for is
But where did you get x=f(y) and y=f(x) from? You can't just assume things that aren't stated! What if the question was more difficult? Could you have just made up random things and found a solution anyways?
y-->f(x) f(x-f(f(x)))=f(f(x)-f(f(x))-1=-1, and since f is non-constant, x-f(f(x))=-c f(f(x))=x+c for some constant c. This also proves surjectivity, since the RHS is arbitrary. Then substituting that into the original equation we get f(x-f(y)) =x+c-f(y)-1=(x-f(y)+c)-1=f(f(x-f(y)))-1. We can now just set f(x-f(y))-->x (since f is surjective) and we are ready. This seems too good to be true. Can anyone spot if I made a mistake?
f(x-f(y))=f(f(x))-f(y)-1. Differentiate the equation by y, using the rule of differentiation "complex functions"(the chain rule , that expresses the derivative of the composition of two differentiable functions f and g in terms of the derivatives f and g). f'_u(u)*(x-f(y))'_y= (f(f(x)) - f(y) -1)'_y , u=x- f(y). f'_u(u)*(- f'_y(y))= (- f'_y(y)). It is taken into account here that the derivatives of the constant and of functions that depend only on x are equal to zero. f'_y(y)*[f'_u(u)-1]=0. f'_y(y)≠0, that is, f(y)≢ const, which corresponds to the condition of the problem. So f'_u(u) = 1 =>f'_x(x) =1 => f(x)=x+c. We substitute this expression into the original equation (the most difficult moment!)) [x-(y+c)]+c= (x+c)+c -(y+c)-1 => c =1. Answer: f(x)=x+1.
wow i h8 math but looked from the beginning to the end with understanding only 2% but I was kind of facinanted until I decidet that I will quit my math study. Nice Work man you defenetly won't have Alzheimer.
why so complicated? :) f(x - f(y)) = f(f(x)) - f(y) - 1; set y to a value that makes this equation true: f(y) = x - f(x); then x - f(y) = f(x); f(f(x)) = f(f(x)) - f(y) - 1; f(y) = -1; x - (-1) = f(x); f(x) = x + 1. This is the only possible function. check: f(x - (y + 1)) = f(x + 1) - (y + 1) - 1; x - (y + 1) - 1 = (x + 1) - 1 - (y + 1) - 1; x - y - 2 = x - y - 2; Answer: f(x) = x + 1
I think it can be done more straightforward: rewrite as f(x-f(y)) + f(y) + 1 = f(f(x)). Right hand side is independent of f(y) and therefore so is the left hand side. Pick f(y) = 0, this gives f(x) + 1 = f(f(x)). Rename f(x) to x and you get x + 1 = f(x). What am I missing?
There are two problems here: The first is that you can't set f(y) = 0 without knowing that that there is a value of y such that f(y) = 0. For example if the function turned out to be f(x) = x^2 + 1, then there would be no y such that f(y) = 0. The second problem is similar: If you take f(x) to be x in the equation f(x) + 1 = f(f(x)), then the conclusion that x + 1 = f(x) is only true for those values of x that are in the image of f. So we can't say that x + 1 = f(x) for all x in this case; we can only say that if x is such that there is a y such that f(y) = x, then f(x) = x + 1. If we had some way of showing that f is surjective, then this does give us the conclusion that we want. But we don't know a priori that f is surjective.
Problem: is it possible to find ALL solutions of f(x)=f(2x)? I mean, you can deduce the existence of constant solutions, but do you really need a "happy idea" to find other solutions? And if so, how can you prove that you found them all? Thanks, Michael!
The sign function satisfies this and isn't constant. If you also impose continuity on f, then only constant functions satisfy f(x) = f(2x) for all x in ℝ: Let x1, x2 ∈ ℝ, then f(x1) = lim_{n→∞} f(x1/2^n) = f(0) = lim_{n→∞} f(x2 / 2^n) = f(x2).
@@huellenoperator but there is also a couple's of solutions using cosine and sine functions, but I don't see how these solutions arise by using the methods for solving functional equations that Micheal Penn usually use in his videos. So I wonder how exhaustive these methods are.
Set x = f(y). Then, f(f(x)) = x + f(0) + 1 Hence, f(x) = x + (f(0) + 1)/2 x = 0 => f(0) = 1 So, f(x) = x + 1. EDIT: This is assuming f is linear. f = -1 is also a solution.
Okay, tried to hold my thought till the end, but i can't. At this point: th-cam.com/video/P2J40wWskDM/w-d-xo.html we prove: f(x+1) = f(f(x)). Therefore f(x) = x+1. Why not? Tried watching it a couple more minutes, holding my thought, but got impatient. I jump all the way to end (i know... bad me...) and i find that indeed that is the final answer. By WHY? Why is the equation, f(f(x)) = f(x+1) NOT sufficient to prove f(x) = x+1 directly, without having to go thru all that torture from that point till the end? Can you explain? Pretty please??
Because we want to know that it is the only solution. You can't just lop off an F from both sides of the functional equation F( F(X) ) = F( X+ 1) and call it good, because you don't know, a priori, that F is bijective.
I had the same thought as you at that, but poked a hole in it by supposing f(x) isn't linear; then f(x)=a doesn't have to be x+1 to have the same image under f. At his point in the video we don't know for sure that f is a line. At least that's how I was thinking of it.
If you are given f(x+1)=f(f(x)) then you cannot simply cancel one f from both sides to say that f(x)=x+1 but why? Because the function f was not proven to be injective till that point...what is an injective function..? It is basically a class of functions having the property that if f(a)=f(b) then it is necessary that a=b in other words distinct elements in the domain of f maps to distinct elements in the range of f. Now let me give you an example of a non injective function, consider f(x)=x² note that f(2)=f(-2) so can we say that 2=-2? NO. I hope you got it
May by we can have more simplify solution: 1) x = f(y); y in Z ==> f(0) = f(f(x)) -x -1 f(f(x)) = f(0) +x -1 2) x= f(y) + z; y in Z ,z is const in Z ==> f(z) = f(f(x)) - (x - z) -1 f(f(x)) = f(z) - z + x + 1 --for any z in Z Now we can equal RHS1 and RHS2 : f(0) + x +1 = f(z) - z + x + 1 f(0) = f(z) + z f(z) = z + f(0) so f(x) = x + C now put it in the equation: f(x - f(y)) = f(f(x)) - f(y) - 1 f(x - y - C) = f(x + C) - y - C - 1 x - y - C + C = x + C + C -y -C -1 x - y = x - y + C - 1 C = 1 so result is f(x) = x + 1
at the point (a²-a)(x+y)+2ab-b=1 you could already argue that the coefficient of (x+y) must be 0 because the rest of the equation are constants and hence a²=a --> a=0 or a=1. since a=0 would give us a constant function, a=1 is the only valid option
In fact, the conclusion from b(2a - 1) = 1 to say b = +- 1 is not accurate.
@@mohammadzaeriamirani7776 that is not what i said. it literally doesn't matter what b is at this point as long as it's a constant. x and y are the only variables and since the equation is supposed to hold for any x and y, the coefficient of x+y must be 0. b just follows from that observation about a
17:53 It is never too late to start working towards your dreams. Forget about the past, it does not define your future. What defines is what you do today. Happy Friday!
HAHHAHAHAHAHA
Today is a Good Time To Start
@@diniaadil6154 Indeed!
I would say the Unabomber's past pretty much defined his future in Supermax prison in Colorado. Wonder if Ted is a subscriber to this channel?
9:32 a discrete differential equation!
6:50, if you prove f is invertable, then you immediately get that f(x)=x+1 since f(either) are equal.
even injectivity is enough (as opposed to invertibility)
Exactly! I was literally screaming that and I don't know why he didn't mention that at all. You can take the inverse of both sides, as long as f-inv is possible, which ends up being such a straightforward solution
Yes, but how do you prove the injectivity? :-?
@@MattiaBelletti once you get to f(x) = ax + b we know f is injective (because only the case a=0 would be non-injective and constant functions are ruled out in the statement of the problem)
The extra rigour (showing g(x) is constant for integer x) demonstrates the solution is exhaustive. Perhaps the solution was longer than necessary, but it was complete.
Why make it easier, if it can be harder...
This was also on my team selection test. Was very close to fully solving it and I've also made a video about the problem on my channel
In the first proposed substitution 4:16, one can replace every f(y) by x, which leads to « f(0) = f(f(x)) -x -1 ». True for ar least one x, but more than one since we know the f() is not constant and x is f(y). Since -for those x- f(f(x)) = x plus a constant, it very strongly hints at some linear function.
How did you learn to understand this video? ... what's your resources... learning material?! ... please help!
When I see something like 9:46 my first thought is to immediately do a sum. Notice that if the sum the left hand side of the equation you would get a telescoping series, and you can easily sum up the right hand side as well. I would sum both sides from t (the value at which f(t) is -1) to x and go from there
I didn't why we were aloud to set f(x)= ax+g(x)
This video excels in something that many videos on similar topics fail to convey (the most prominent example being the videos by MindYourDecisions). While most videos will present a neat and tidy way to solve the problem at hand, you actually take the time to go over the thought process involved in solving problems like this, making it clear that this problem is not at all trivial to solve. In my opinion, this aspect alone makes this video much more worthwhile than most others like it.
Great solution. I think you already arrived at the solution at time index 6:43 but maybe didn't notice it. You arrived at the result
f (x+1) = f (f (x))
From that it necessarily follows that
x+1 = f (x)
because the nature of the function f(x) as defined always returns the same value for any given x in Z
That was my thought as well, but I am not sure he could have missed something like that. Must be we are missing something instead.
Do we know that f is bijective?
We’d have to prove that f is injective (one-to-one), because if we don’t there’s still the possibility that x+1 and f(x) are different but happen to output the same integer when run through f again.
@@trdi You need to prove injectivity to make that claim. What if f(x) = -1 for all x? This is also a solution
A rigorous argument is:
from the t-substitution we know that f(f(x))=f(x+1)
from the initial substitution f(y)=x used the other way we know that f(f(x))=x+1+f(0)
Combining both follows that f(x+1)=x+1+f(0), or f(x)=x+f(0).
To find f(0) replace x with f(x) and get f(f(x))=f(x)+2f(0)
and equating with the other expression for f(f(x) we get f(0)=1.
I was away for 3 weeks and missed all your videos. Feels so good to be back:)
At 7:00 it might have been clearer to introduce a new variable name. It's not immediately clear that the "x" on the LHS is a new "x" being defined in terms of the old "x".
An interesting problem with a great solution!!! 😍
There's a gap at 9:45. You specialize x = f(x')-1, y=x' and then conclude that f(x+1)-f(x)=const (which is fine); but then you conclude f(x+1)-f(x)=const for all x, which doesn't work unless f is surjective.
Setting x=0, f(-f(y)) = f(f(0)) -f(y)-1.
Since f(y) is an integer (say z), this gives f(-z)=f(f(0)) -z -1.
Then f(z) = z + f(f(0)) -1
let f(f(0))=k (a constant).
Then, f(z) = z + k -1 (Equation 1)
Substituting z =0, f(0) = k - 1
f(f(0)) = k - 1 + k - 1 = 2k -2
but, f(f(0))= k by definition, hence k = 2k -2 (i.e.) k = 2.
Substituting k=2 in Equation 1 gives
f(z)=z+1
And, that's a good place to stop.
You could set x=-1 so that it has the form f(u)=f(f((-1))+u where u= -f(y)-1. So we see it has the form u+a. Now plug that like michael back in the functional equation and you would get x+1=f(x)
But wouldnt that work Only if u Is -1-f(y) so It isnt true for all u but Only the ones in that form right?
@@lucacastenetto1230 I think it works because since ATQ f has range of all intergers, therefore (-1-f) also has range of all integers
@@pierce8308 no, we actually should prove surjectivity first
@@jamesjames1549 Thats right. Completely missed that
At 13:30 you could also use that with x=0 and y=0 you get that f(-f(0))=f(f(0))-f(0)-1=f(1)-f(0)-1=f(-1)+1-1=f(-1) and use that the function is injective so -f(0)=-1 -> f(0)=1=f(-1)+f(-1)+1 -> f(-1)=0 since the "gradient" is f(-1)+1 by 9:00. Just to avoid the a and b mess.
great explanation
another way to argue why f(x+1)-f(x)=a leads to linearity is as follows: since f(x+1)-f(x)=a we apply sigma on both sides taking limits from x=0 to x=y-1(y is an arbitrary integer) note that when we sum from 0 to y-1 then many terms cancel each other out giving us f(y)=ay+f(0) setting f(0)=b we get that f(y)=ay+b for all y€Z so f must be linear.
To prove f(x+1)-f(x) = a implies f(x) = mx + p there is a much shorter way to do :
You let x = k and you take the sum k = 0 to n-1 on both sides. On the RHS you get na because a is constant and on the LHS, this is a telescoping sum, simplifying to f(n) - f(0).
Then you obtain the general form of f(x), and conclude.
Right, this is just the discrete version of integrating to solve a differential equation :)
4:25
Sorry I haven't studied higher lvl maths. But what does "image of f(x)" mean?
the set of all the numbers that result in applying f to the integers. For example if f(x)=x^2 then then image of f would be {0, 1, 4, 9, 16, ....}
if you set x = -1, a = -f(y) - 1 you will get
f(a) = a + f(f(-1)) thus
f(x) = x + c, c = f(f(-1))
you can easly show that c = 1
and you are done.
who are YOU!?
@@lubibubi6380 a guy, i think
At 3:40 you got to "f(something) = -1". You missed that since it is (from the problem definition) a non constant function, the "something" must be constant in order for f(something) to be constant.
So then we can say:
something = x-f(f(x)) = -k
Or: f(f(x))=x+k and f(f(0)) = k
Going back to y=free,x=f(y) we can easily derive f(f(f(0))) = 1, aka f(k) = 1
From the original equation, we can let x=free,y=k and get:
f(x-f(k)) = f(f(x)) - f(k) - 1
Substituting f(k)=1 and f(f(x)=x+k we get:
f(x-1) = x + k - 2
From there it is pretty simple to derive the final answer.
At 7:20 he set x = f(x)-1, y as x and he gets a = f(-1) + 1 = f(x+1) - f(x). So if I'm not wrong, this conclusion is specific to x where x = f(x)-1 and y = x
But on the next clip he use f(x+1) - f(x) = a for all x in Z, so I'm a bit confused. Since we didn't know that f(x) is 1 to 1, we couldn't concludes x = f(x) - 1 from f(x+1) = f(f(x)). Is there a way to proof x = f(x) - 1 for all x or did I overlooked something?
If it helps to make it less confusing, pick an arbitrary value for c, and set x = f(c) - 1 and y to c. The functional equation must be true for this choice of x and y since it must be true for every x and y. The conclusion that you then get is that f(-1) + 1 = f(c + 1) - f(c) for every value of c. When he says "Take x = f(x) - 1", the x on the LHS is the x in the functional equation, while the x on the RHS is a free variable. People often write this way when presenting solutions for functional equations, but it can be confusing. Another style that is possibly less confusing that people sometimes use is to start the solution with "Let P(x, y) be the statement f(x - f(y)) = ...", and then instead of saying "Set x = f(x) - 1, and y = x", they'll instead write "Since P(f(x) - 1, x) is true, we have that ... and so f(-1) + 1 = f(x + 1) - f(x) for all x".
@@DylanNelsonSA this makes a lot of sense now, thank you!
I was confused at the same point thinking how he could just say x=f(x)-1 which is a whole new condition.
and if that was true then f(x)=x+1 haha.
@@DylanNelsonSA very well explained - thank you
I have a question, what if we can't assume the image of f() is all integers?
I set y=f^(-1)(0) so f(y)=0
f(x) = f(f(x))-1
x2 = f(x)
x2 = f(x2)-1
so f(x) = x+1
I assumed f^(-1)(0) exists. What if there wasn't? Does there exist a different function where the image is not all ints?
I love these problems!
You can also let x free and set y such that f(y)=-1. then we have directly f(f(x))=f(x)+1 for all x so f(x)=x+1. we can then verify of course that there is a y such that f(y)=-1.
Everywhere 6 years ago 😉👍
At 10:15 you should use the Method of Frobenius!!!! Also what a nightmare for a complete joke of a result
At 06:45 why can't we just reduce it by f, and leave x+1=f(x)? Probably consider some possible periodical behavior
11:46 Does g(x) need to be a constant? Couldn't it be some periodic function with a period of 1?
g(x) is a function on integers so that's equivalent to being a constant
In 6:46 the solution is already there: f(x+1)=f(f(x)) ! Just apply f^-1 on both sides => f(x)=x+1. One has just to prove that it is indeed a solution. Invertability is not even necessary to prove. But that’s easy. Just insert. Remains to prove it’s the only solution.
If x = f(y) => f(0) = f^3(y) - f(y) - 1
f^3(y) - f(y) = f(0) + 1 (this value must be constant)
Since the difference is a constant, the function can't exclude any integer as a result, so f(x) in general = x + n.
Letting f(y) = 0 (which is thus possible), it follows that f(x) = f^2(x) - 1 => f(x) = x+1.
Set x=f(y), then, by rearranging the terms we get f(f(x))=x+1+f(0). f(f(x)) is linear, which implies that f(x) is linear as well (does that need a proof?). Thus there exists a "y" such that f(y)=0. We can substitute it back in to the original equation. f(x)=f(f(x))-1. Set t=f(x) and we have f(t)=t+1 and that's a good place to stop
This was a great way to start my morning. Thanks Michael.
Nice LECTURE.
16:56 I think that is not so obvious that both b and a (or 2a - 1) should be integer.
Here, a = f(x+1) - f(x) so a must be an integer. Thus, b must also be an integer since we posit that f(x) = ax+b and if b is not an integer then f(x) has non-integer values.
The question is: How do you know which substitution is gonna work in each step ? Is it all about trial and error ?
Mostly its about trial and error.
U can guess the magic values of x and y by looking at the structure of eq.(try to guess what values would simplify it)
I took hours doing many substitutions, cases and combining equations. In the end I only managed to proof that there are two solutions, f(x) =x+1 and f(x) =-1, which are the only ones of the form ax+b and that assuming 0 in im(f), the only solution is x+1. I then kind of worked into the right direction, but never did the clever substitution x=f(v) - 1
the solution was just on the board at 6:40 just by taking f inverse to both sides
I found the answer quickly, and then was struggling to prove it was the only one.
Now I know it is... Over the integers
if we put y= f(x)
f(x-f(f(x)))= f(f(x)) - f(f(x)) -1 = -1
f(x-f(f(x))) = -1
let g(x) = x - f(f(x))
f(g(x))= -1
since it is given that
f:Z > Z is non constant function
so g(x) must be constant so,
x - f(f(x)) = constant
that means f(f(x)) = x + b
where b is any constant
I did some of solution which is not at all good as per my side
Let x=0 and y=0
f(-f(0))=f(f(0))-f(0)-1
Next let x=0 y=y
f(-f(y))=f(f(0)) - f(y) -1
Let -f(y) = a
Then f(a) = f(f(0)) - a - 1
Taking this as a general equation
And then let a=0
f(0) = f(f(0)) - 1
f(0) + 1 = f(f(0))
Let f(0) = b
Now b + 1 = f(b)
And now taking this as a general rule , f(0) = 1
And so on, and putting this into the original equation, it satisfies the equation
12:58 What exactly would be different then?
I'm slightly confused, the question doesn't seem to limit x and y to a dependency, as far as it's concerned they are freely independent variables. Does the assumption that one is the function applied to the other not limit the potential solutions?
in 6:44 you actually have the answer both sides are functions of f so what is inside should be euel f(x)=x+1
What are thé dimensions of your board ? (Can you send the reference ?)
How do I prove that the difference equation shown in the video has a unique solution, much like a linear homogeneous ODE? That is not so obvious to me
Too taken for granted.
From f(x)=ax+b, a non-zero, we know f is injective (do not say invertible because the domain of f is not rational number).
Then apply injectivity to f(f(x))=f(x+1) to get f(x)=x+1. Then verify this satisfies the original equation.
Couldn't you set some variable a = x - f(y), and get the functional equation:
f(a) = f(f(x)) + a - x - 1
Then choose a = x, getting:
f(f(x)) = f(x) + 1
Then we can easily see that:
f(a) - a = f(x) - x
Then let a = 0:
f(x) = f(0) + x
Now you simply plug this into our given equation to find f(0) = 1, and therefore f(x) = x + 1?
Is this solution valid?
What's wrong with simplifying by subbing in x=-1 at the start, then defining a variable z=-1-f(y)? Have I overly constrained to solutions where f(-1) is defined, or something?
Phương trình hàm giải bằng thay thế. Cảm ơn.
I first assume that it is linear so I can take the f(y) out of the outer function and cancel it. What is left is f(x)+1=f(f(x)). Change the variable to u=f(x) leaves behind f(u)=u+1.
How to find whether it is linear is out of my reach.
Also, I don't know how to make sure it is the only solution.
X=0, then we have f(-f(y))=f(f(0))-f(y)-1
Giving u=-f(y) and knowing that c=f(f(0))-1 is a constant, we derive f(u)=u+c
Putting that in the main equation:
(x-(y+c))+c=((x+c)+c)-(y+c)-1
Then:
x-y-c+c=x+2c-y-c-1
x-y=x-y+c-1
Therefore c=1
So... F(x)=x+1
Can some kind of general statement be made about functional compositions and shifts? I mean…to make these things more straightforward?
6:45 f(x+1)=f(f(x)). Doesn't this show directly that f(x)=x+1?
You need to prove f is injective in the first place
Just substitute x=f(y), then f(x)=x+(1+f(0))/2. Another substitution gives f(0)=1 and thus, f(x)=x+1.
How do you get this expression from the substitution, particularly how do you get rid of the composite function such as f(f(x))?
uhhh to prove f(x)=ax+b just notice that its a constant rate of change in both x and y. So its a line.
Not sufficient for showing that `b` must be a constant, however. That must be done as well in order to satisfy the problem as stated.
Not sure if I just got lucky or if this is even valid. I assumed that f(x) had a zero at some value. I set y to that arbitrary value, simplifying it to f(x) = f(f(x)) - 1.
Then, set x=0 to show that f(0) = f(f(0)) - 1. Set a = f(0).
This becomes a = f(a) - 1.
Substitute x for a.
f(x) = x + 1.
I think f(x)=-1 would be only constant function solution if you did not exclude constant functions at outset.
Also, assuming f(x) is a polynomial, would force f(x) = mx + b because of degree clashes. For example, suppose degree of f is two, then f(f(x)) on RHS is degree 4 and there are no x^4 term on LHS. This is a little slippery since polynomials in the variables x and y are present. Also f(x) a rational function or function involving radicals sure don't seem like they would work in the absence of a rigorous proof.
Using f(x) = mx + b and the well known polynomial result of equating coefficients leads to m=b=1
My mom would love this kind of math babble.. hehehe
How could x-f(f(x)) only be an integer for a single value of x?
We know that f goes from the integers to the integers, so that term is just a subtraction of integers and itself an integer.
Very, very cool.
Btw f(x+1) - f(x) = a => f(n) = a + n*f(0) just by simple induction.
Very few people really understand what it takes to make that thumbnail, and I appreciate your courage to do so. I don't even know what to say but just...you're the best, man.
Edit: He may just get himself banned from China government by publishing that thumbnail.
Wait a sec. At 6:47 we see that f(x+1)=f(f(x). But isn't this only when y=t and f(t)= -1 ? So is it valid to then say at 8:42 that f(f(u))=f(u+1) when this was derived from the new value of y=x ?
I noticed that and assumed (probably incorrectly) that the arguments of the outer f() must be equal, so (x+1) = (f(x)). I'm sure Michael was just more thorough ...
We know that there is 𝘴𝘰𝘮𝘦 value of T such that F(T) = -1. At this point in the video, we don't know what it is, but we know that it exists. Substituting that into the original functional equation tells us that F( X+1 ) = F( F(X) ). This new identity is true for all values of X.
At 7:15, when you assume that x=f(x)-1, isn't that circular reasoning? You just assumed that f(x)=x+1 by doing that, and that assumption rules out all other possible solution functions.
At 14:00 you have a good proof that any linear function that solves the original equation must be the f(x)=x+1 equation, but that isn't sufficient to solve the original question of "what are all functions that solve the original equation?"
His expression is sloppy. He meant to write x -> f(x)-1.
7:15 when you replace x = f(x) -1 ..... Isn't that saying that f(x) = x + 1 , but supossely You still don't know what the function f(x) your looking for is
question - you know that g(x) = constant, but it is only for x in Z, but in R it could be not constant but for example periodical?
g(x) is a function from Z -> Z
But where did you get x=f(y) and y=f(x) from? You can't just assume things that aren't stated! What if the question was more difficult? Could you have just made up random things and found a solution anyways?
f(x-f(y)) = f(f(x)) - f(y) - 1
1) Set x=0 and y=0 => f(f(0)) = f(f(0)) - f(0) - 1 => f(0) = 1
2) Set x as free variable and y=0 => f(x-f(0)) = f(f(x)) - f(0) - 1
3) Replace f(0) in step 2 with the value found in step 1 => f(x+1) = f(f(x)) + 1 - 1 => f(x+1) = f(f(x))
Then, supposing f(x) has an inverse function 'finv':
finv(f(x+1)) = finv(f(f(x)))
x+1 = f(x)
y-->f(x)
f(x-f(f(x)))=f(f(x)-f(f(x))-1=-1, and since f is non-constant, x-f(f(x))=-c f(f(x))=x+c for some constant c. This also proves surjectivity, since the RHS is arbitrary.
Then substituting that into the original equation we get f(x-f(y)) =x+c-f(y)-1=(x-f(y)+c)-1=f(f(x-f(y)))-1. We can now just set f(x-f(y))-->x (since f is surjective) and we are ready.
This seems too good to be true. Can anyone spot if I made a mistake?
Doesn't the yellow '*' equation f(x+1) = f(f(x)) imply that f(x) = x+1 ?
Only if f is injective, which I guess is not proven yet at that point.
Only if f is invertible.
lol just substitute x=-1 at the very start, and considering that f is not a constant function you'll get f(x) = x+C, where C is some constant
welp my social credit
The is an effing amazing problem
f(x-f(y))=f(f(x))-f(y)-1.
Differentiate the equation by y, using the rule of differentiation "complex functions"(the chain rule , that expresses the derivative of the composition of two differentiable functions f and g in terms of the derivatives f and g).
f'_u(u)*(x-f(y))'_y= (f(f(x)) - f(y) -1)'_y ,
u=x- f(y).
f'_u(u)*(- f'_y(y))= (- f'_y(y)). It is taken into account here that the derivatives of the constant and of functions that depend only on x are equal to zero.
f'_y(y)*[f'_u(u)-1]=0.
f'_y(y)≠0, that is, f(y)≢ const, which corresponds to the condition of the problem.
So f'_u(u) = 1 =>f'_x(x) =1 => f(x)=x+c.
We substitute this expression into the original equation (the most difficult moment!))
[x-(y+c)]+c= (x+c)+c -(y+c)-1 => c =1. Answer: f(x)=x+1.
Nice. But the differentiability needs to be proved even if the problem does not specify the domain to be the integer set.
台灣欸 yes translate it, fans from Malaysia
wow i h8 math but looked from the beginning to the end with understanding only 2% but I was kind of facinanted until I decidet that I will quit my math study. Nice Work man you defenetly won't have Alzheimer.
the equation for a at 11:30 lost me
why so complicated? :)
f(x - f(y)) = f(f(x)) - f(y) - 1;
set y to a value that makes this equation true: f(y) = x - f(x);
then
x - f(y) = f(x);
f(f(x)) = f(f(x)) - f(y) - 1;
f(y) = -1;
x - (-1) = f(x);
f(x) = x + 1.
This is the only possible function. check:
f(x - (y + 1)) = f(x + 1) - (y + 1) - 1;
x - (y + 1) - 1 = (x + 1) - 1 - (y + 1) - 1;
x - y - 2 = x - y - 2;
Answer: f(x) = x + 1
Please make video about cardinality of real irrational numbers and cardinality of complex numbers.
Please take problems from isi bstat / bmath entrance examination.. love from india ❤️
I think it can be done more straightforward: rewrite as f(x-f(y)) + f(y) + 1 = f(f(x)). Right hand side is independent of f(y) and therefore so is the left hand side. Pick f(y) = 0, this gives f(x) + 1 = f(f(x)). Rename f(x) to x and you get x + 1 = f(x). What am I missing?
i dont think we can pick f(y) = 0 , since we dont know whether the equation f(x)=0 has a root or no . Im not sure though .
This doesn't 'find all'. This just 'shows a case where'.
@@Khalibi makes sense!
There are two problems here: The first is that you can't set f(y) = 0 without knowing that that there is a value of y such that f(y) = 0. For example if the function turned out to be f(x) = x^2 + 1, then there would be no y such that f(y) = 0. The second problem is similar: If you take f(x) to be x in the equation f(x) + 1 = f(f(x)), then the conclusion that x + 1 = f(x) is only true for those values of x that are in the image of f. So we can't say that x + 1 = f(x) for all x in this case; we can only say that if x is such that there is a y such that f(y) = x, then f(x) = x + 1. If we had some way of showing that f is surjective, then this does give us the conclusion that we want. But we don't know a priori that f is surjective.
@@DylanNelsonSA thanks!
how did this get on my suggested lol
Problem: is it possible to find ALL solutions of f(x)=f(2x)? I mean, you can deduce the existence of constant solutions, but do you really need a "happy idea" to find other solutions? And if so, how can you prove that you found them all? Thanks, Michael!
Is f mapping from R to R?
@@saamshahrouzi8521 yes
The sign function satisfies this and isn't constant.
If you also impose continuity on f, then only constant functions satisfy f(x) = f(2x) for all x in ℝ: Let x1, x2 ∈ ℝ, then f(x1) = lim_{n→∞} f(x1/2^n) = f(0) = lim_{n→∞} f(x2 / 2^n) = f(x2).
@@huellenoperator but there is also a couple's of solutions using cosine and sine functions, but I don't see how these solutions arise by using the methods for solving functional equations that Micheal Penn usually use in his videos. So I wonder how exhaustive these methods are.
Set x = f(y).
Then, f(f(x)) = x + f(0) + 1
Hence, f(x) = x + (f(0) + 1)/2
x = 0 => f(0) = 1
So, f(x) = x + 1.
EDIT: This is assuming f is linear. f = -1 is also a solution.
Okay, tried to hold my thought till the end, but i can't. At this point: th-cam.com/video/P2J40wWskDM/w-d-xo.html we prove: f(x+1) = f(f(x)). Therefore f(x) = x+1. Why not? Tried watching it a couple more minutes, holding my thought, but got impatient. I jump all the way to end (i know... bad me...) and i find that indeed that is the final answer. By WHY? Why is the equation, f(f(x)) = f(x+1) NOT sufficient to prove f(x) = x+1 directly, without having to go thru all that torture from that point till the end? Can you explain? Pretty please??
Because we want to know that it is the only solution. You can't just lop off an F from both sides of the functional equation
F( F(X) ) = F( X+ 1)
and call it good, because you don't know, a priori, that F is bijective.
I had the same thought as you at that, but poked a hole in it by supposing f(x) isn't linear; then f(x)=a doesn't have to be x+1 to have the same image under f. At his point in the video we don't know for sure that f is a line. At least that's how I was thinking of it.
@@bobbyhanson346 injective*, but yes
If you are given f(x+1)=f(f(x)) then you cannot simply cancel one f from both sides to say that f(x)=x+1 but why? Because the function f was not proven to be injective till that point...what is an injective function..? It is basically a class of functions having the property that if f(a)=f(b) then it is necessary that a=b in other words distinct elements in the domain of f maps to distinct elements in the range of f. Now let me give you an example of a non injective function, consider f(x)=x² note that f(2)=f(-2) so can we say that 2=-2? NO. I hope you got it
@@pratikmaity4315 Makes sense, thanks!
May by we can have more simplify solution:
1) x = f(y); y in Z ==> f(0) = f(f(x)) -x -1
f(f(x)) = f(0) +x -1
2) x= f(y) + z; y in Z ,z is const in Z ==> f(z) = f(f(x)) - (x - z) -1
f(f(x)) = f(z) - z + x + 1 --for any z in Z
Now we can equal RHS1 and RHS2 :
f(0) + x +1 = f(z) - z + x + 1
f(0) = f(z) + z
f(z) = z + f(0)
so f(x) = x + C
now put it in the equation:
f(x - f(y)) = f(f(x)) - f(y) - 1
f(x - y - C) = f(x + C) - y - C - 1
x - y - C + C = x + C + C -y -C -1
x - y = x - y + C - 1
C = 1
so result is f(x) = x + 1
Greeting from Taiwan!你好～～
f(x) =x+1
1, -i and f is i ...
IGHODARO GOAL
Proposed by Dorlir Ahmeti,Albania
My first instinct was to just suppose f(x) is linear and then see what I get for a and b. Not as rigorous but gets the job done.
10 minutes before was a good place to stop. Nice video, man.
anache 🤙🤙
Nice solution to this ugly looking functional equation!
U may not be avle to fnd f(t)=-1
11SECONDS LATE