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.
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.
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.
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
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.
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.
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)
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.
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.
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.
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".
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.
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
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 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?
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.
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
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 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.
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.
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
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.
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".
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.
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.
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?
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?
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
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
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?
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?
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?
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?"
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.
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.
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.
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.
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.
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.
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
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
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.
Okay, tried to hold my thought till the end, but i can't. At this point: ruclips.net/video/P2J40wWskDM/видео.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
At first I took x=x, f(y) = 0 (supposing that f(x) can be equal to 0), and got: f(x) = f(f(x)) -1 f(f(x)) = f(x) + 1 | let u = f(x) f(u) = u+1 But then stuck with proving my suggestion)))))))
So then just show that there exists such an x that f(x)=0 to justify your assumption that f(x) can equal 0. It is immediately obvious from your result f(x)=x+1 that the condition is met when x=-1. Therefore your assumption, even though just a guess, is justified.
Go down the path of choosing x=f(y) and substitute such that f(0)=f(f(x))-x-1 ie f(f(x))=x+a (2) for the constant a=f(0)+1 A solution is obviously f(x)=x+a/2, but proceed more generally to ensure all solutions are found, treating a as an unknown constant. Using new variable definitions X=f(x) (3) & Y=f(X) (4) do: f(X)=x+a. (from (2) & (3)) x=f(X)-a f(x)=f(f(X)-a) (applying f to both sides) X=f(f(X)-a) (subst (3)) X+a=f(f(X)-a)+a f(f(X))=f(f(X)-a)+a. (from (2)) f(Y)=f(Y-a)+a. (subst (4)) f(Y)-a=f(Y-a) This is sufficient to show that f is at most linear Set f(x)=Ax+B for some constants A & B and substitute back into the original equation. One solution is A=0,B=-1, ie f(x)=-1, the constant solution(s) we're told not to bother with. The other is A=1,B=1, ie 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?
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...
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.
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.
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!
I didn't why we were aloud to set f(x)= ax+g(x)
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 was away for 3 weeks and missed all your videos. Feels so good to be back:)
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
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.
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.
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
9:32 a discrete differential equation!
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.
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 :)
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.
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".
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.
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
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
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
At 06:45 why can't we just reduce it by f, and leave x+1=f(x)? Probably consider some possible periodical behavior
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?
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.
great explanation
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
This was a great way to start my morning. Thanks Michael.
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
An interesting problem with a great solution!!! 😍
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
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
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.
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.
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
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, ....}
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.
At 10:15 you should use the Method of Frobenius!!!! Also what a nightmare for a complete joke of a result
Everywhere 6 years ago 😉👍
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
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.
I love these problems!
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.
12:58 What exactly would be different then?
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?
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))?
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
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?
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
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
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?
Nice LECTURE.
Can some kind of general statement be made about functional compositions and shifts? I mean…to make these things more straightforward?
I found the answer quickly, and then was struggling to prove it was the only one.
Now I know it is... Over the integers
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
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?
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?
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.
What are thé dimensions of your board ? (Can you send the reference ?)
Too taken for granted.
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.
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.
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)
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.
My mom would love this kind of math babble.. hehehe
Phương trình hàm giải bằng thay thế. Cảm ơn.
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.
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.
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.
台灣欸 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.
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.
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
welp my social credit
the equation for a at 11:30 lost me
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
10 minutes before was a good place to stop. Nice video, man.
The is an effing amazing problem
Greeting from Taiwan!你好～～
Please take problems from isi bstat / bmath entrance examination.. love from india ❤️
Proposed by Dorlir Ahmeti,Albania
f(x) =x+1
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
Please make video about cardinality of real irrational numbers and cardinality of complex numbers.
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!
Okay, tried to hold my thought till the end, but i can't. At this point: ruclips.net/video/P2J40wWskDM/видео.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!
1, -i and f is i ...
how did this get on my suggested lol
IGHODARO GOAL
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.
At first I took x=x, f(y) = 0 (supposing that f(x) can be equal to 0), and got:
f(x) = f(f(x)) -1
f(f(x)) = f(x) + 1 | let u = f(x)
f(u) = u+1
But then stuck with proving my suggestion)))))))
you didnt prove that f is surjective, there could be no integer y such that f(y)=0
So then just show that there exists such an x that f(x)=0 to justify your assumption that f(x) can equal 0. It is immediately obvious from your result f(x)=x+1 that the condition is met when x=-1. Therefore your assumption, even though just a guess, is justified.
anache 🤙🤙
Nice solution to this ugly looking functional equation!
U may not be avle to fnd f(t)=-1
Go down the path of choosing x=f(y) and substitute such that
f(0)=f(f(x))-x-1
ie f(f(x))=x+a (2)
for the constant a=f(0)+1
A solution is obviously f(x)=x+a/2, but proceed more generally to ensure all solutions are found, treating a as an unknown constant.
Using new variable definitions
X=f(x) (3) & Y=f(X) (4)
do:
f(X)=x+a. (from (2) & (3))
x=f(X)-a
f(x)=f(f(X)-a) (applying f to both sides)
X=f(f(X)-a) (subst (3))
X+a=f(f(X)-a)+a
f(f(X))=f(f(X)-a)+a. (from (2))
f(Y)=f(Y-a)+a. (subst (4))
f(Y)-a=f(Y-a)
This is sufficient to show that f is at most linear
Set f(x)=Ax+B for some constants A & B and substitute back into the original equation.
One solution is A=0,B=-1, ie f(x)=-1, the constant solution(s) we're told not to bother with.
The other is A=1,B=1, ie f(x)=x+1.
This does work. Neither X nor Y is allowed to choose from all of integer set Z but a subset of Z.