It is obvious from 4:16 that g is an involution (exchanges n and m, so applying it twice gives back the same thing). This shortens the last part, as involution immediately leads to A=1.
same doubt here. But I think since it ends with a nice little value, there was another mistake somewhere else so the double mistake cancelled each other out?
Michael should write a book with the subjects/problems from all his TH-cam videos, perhaps categorized by college course and/or subject matter (e.g., Japanese temple problems). I'd buy it.
I’m sure a few contestants got that one right, after being messed up for 3h and the supervisor says, time, they write down, paniced, 1995. And what do you know
@@tomatrix7525 Though guessing the answer isnt worth any points. There is no point in guessing 1995 since even if you are right you wont get anything for it.
Problem: |2^n + 5^n - 65| is a perfect square. Find all such positive Integers 'n' . Here |x| is a absolute value of 'x' Hey Michael, plz make a vedio on the solution of this problem 🙂
Small comment about induction: Induction principle: Let S:N->N be the follower function of natural numbers. The induction axiom says that if A is a subset of N where 0 is in A and the image of A under S is included in A, then A = N. In other words the induction hypothesis should be of the form that let any k be in A. The induction statement is then that S(k) is in A. The point is that to assume that some k exists in A and S(k)\in A is not formally correct way to do induction. This property holds for the subset {0,1} of natural numbers.
The "proof" (ending at about 12:00) that g(m) =Am is the solution to the functional equation g(r+s)=g(r)+g(s) only proves that such a form behaves linearly, not that it is the only functional form behaving that way.
What do you mean? He did prove (by induction) that a function on the natural numbers that satisfies g(r+s)=g(r)+g(s) for all natural numbers r and s must have the form g(n)=An for a constant A.
@@Notthatkindofdr No, he proved by induction that a linear function satisfies the constraint g(r+s)=g(r)+g(s). He didn't prove that this is the only functional form that satisfies that constraint. (If we were operating over the reals instead of the natural numbers, for instance, the assertion would be false. There are nonlinear functions that satisfy the additive property.) A little more work is required. See, for instance, the Wikipedia article on Cauchy's functional equation en.wikipedia.org/wiki/Cauchy%27s_functional_equation
@@TedHopp I think you are forgetting that in this case g is only defined on the natural numbers. An induction proof shows that g(n)=An must be true for all natural numbers n, which is the only thing being claimed by Michael. This case is so simple, it is brushed over very briefly in the Wikipedia article you mentioned: at the beginning of Case II, equation (*), where we have alpha=n and x=1 (and g(1)=A), and it just refers to "repeated application of Cauchy's equation", i.e. induction. Edit: Maybe you are really complaining about 10:10 where he says "there is only one class of functions" that satisfies the additive rule, without specifying that he means "on the natural numbers".
@@Notthatkindofdr I'm not saying that the assertion of uniqueness is false, just that the proof offered doesn't prove uniqueness. The argument given in the Wikipedia article, by contrast, does prove uniqueness (for the rationals).
you really made 95 disappear from your equations at 13:28 and 13:43, as you said you would in your hint, but that was real magic, not mathematical magic... ;-)
A very cool answer. Who discovered that? I wonder if there is a general proof that all f(X + f(Y)) type problems will be linear? I feel like jumping to f(X) = aX + b whenever I see one.
Possibly using partial derivatives, in a sense? This solution is linear because the n term on the right is linear. I.e. for this problem, taking the derivative of both sides wrt n gives f'(n)f'(m+f(n)) = 1, and since f' maps to positive integers, we must have f'(n) = 1 for all n, which implies f(n) = n + k for some k. Plugging into the equation gives k = 95.
And if you replace the n with n^2, then the equation you get is f'(n)f'(m+f(n)) = 2n for all m,n. Assuming f'(n) ≠ 0, we get that f'(a) = f'(b) for all a,b > min(f(n)), so f(n) = n + k for sufficiently large n. Plugging in to f(m + f(n)) = n^2 + f(m+95) gives m+n+2k = n^2 + m + 95 + k, which implies k = n^2 ‐ n + 95, but that's not a constant, so we get a contradiction.
You can make your own functional equation for a quadratic too. For example, if f(n) = n^2 + 1, then it satisfies f(m+f(n)) = f(m+1) + f(f(n)) + 2mf(n) - 2m - 1. We can recover it by taking the derivative of that equation wrt n: f'(n)f'(m+f(n)) = f'(n)f'(f(n)) + 2mf'(n), So again assuming f'(n) ≠ 0, we get f'(m+f(n)) = f'(f(n)) + 2m, which shows that f'(n) = 2n + A for some A, which shows that f(n) = n^2 + An + B. And then plugging this in and solving should recover A,B
In 1995, I would be very suspicious if I saw the 19 as a limit of the sum because it is a factor of 1995. So if I don't see a 1995 in the solution, I would figure I did something wrong and double-check where I might have gone awry.
Om the other hand if I see that the answer I got was 1995,I would be sure that I got it right..but wait...what if the question setter was evil and if there was a point where we had to add one and you missed it thinking you got 1995 and it's year 1995 so you don't recheck and answer was somehow 1996...
Can anyone find a functional equation (the domain and codomain dont matter) that is satisfied by a linear function (ax+b) AND a nonlinear function? Myself i haven’t seen any, so i think you could conjecture that if a linear function satisfies a functional equation, then only linear function(s) satisfy the functional equation. Then, memorize the proof so you can use it on olympiad problems and such whenever a linear function turns out to be a solution by inspection. That would help because on this problem it wasn’t hard to find that x+95 worked, but the proof that it was unique was tough.
When you define a function f:A -> B, B is called the co-domain. The range is f(A), the set of all values that are actually obtained by f, which is a subset of the co-domain but may be smaller.
It seems to me that you showed that g(n) = A.n is a function that satisfies g(a+b)=g(a)+g(b), but you didn’t appear to show that this is the only class of functions that meets the condition.
That's what he proved by induction. Let g be a function satisfying the condition on natural numbers, define A=g(1), and then he proves that g(n)=An for all natural numbers n.
Ok, another way to solve this: Plugging in 0 for m, we get f(f(n))=n+f(95) [1] or f(f(n))-f(95)=n. Since this is true for all n in the natural numbers, we know that f is injective and the function g: Im(f)->N g(x)=f(x)-f(95) is its inverse. On the other hand, plugging in m=1, we get f(1+f(n))-f(96)=n. Hence, also h:Im(f)->N h(x)=f(1+x)-f(96) is an inverse function for f. But since the inverse function is unique, we get f(1+x)-f(96)=f(x)-f(95) for all x in Im(f). Rearranging, we get f(1+x)-f(x)=f(96)-f(95) for all x in Im(f) [2]. On the other hand, f(f(0))=f(95), which by the injectivity of f means f(0)=95. By f(n)+f(95)=f(f(f(n)))=f(n+f(95))=95+f(n+95) (LHS: plug in f(n) for n in [1], RHS: plug in [1] into the inner function and then the original equation) Rearranging: f(95)-95=f(n+95)-f(n) for all n in N [3]. In particular: f(95)-95=f(96)-f(1) or f(1)-95=f(96)-f(95), so f(1+x)-f(x)=f(1)-f(0) for all x in Im(f), i.e. f(1+x)=f(x)+f(1)-f(0) for x in Im(f) [4]. Now, since for any x>=f(95), we can choose y=f(x)-f(95) to get f(y)=x, Im(f) contains at least all numbers greater than f(95). Hence, we have f(x+f(95))=f(f(95))+x*(f(1)-f(0)) for all x>=0, where the second equation stems from [1]. However, because f reaches all values x for x>f(95), there is in particular some y in Im(f) with y>max(f(95),f(f(95)) such that y+1 is also in Im(f). Thus, there is some pair of integers x1,x2 such that f(f(95))+x1(f(1)-f(0))=y, f(f(95))+x2(f(1)-f(0))=y+1. Subtracting, we get (x1-x2)(f(1)-f(0))=1. Now, clearly (x1-x2) and (f(1)-f(2)) are both integers dividing 1. Now, we have f(1)-f(0)>0 [5, see below], so this means f(1)-f(0)=1, so f(x+f(95))=f(f(95))+x. Since f(n+95)-f(n) is constant by [3], and we clearly have f(95+f(95))-f(f(95))=95, we have f(n+95)-f(n)=95 for all n. In particular, since we know 95 values in progression, we can go backwards and get f(x+f(95))=f(f(95))+x for all x in N-f(f(95)). Substituting y for x+f(95), we get f(y)=f(f(95))-f(95)+y. Plugging in y=0 and f(0)=95, we get f(y)=95+y. And indeed: with f(y)=95+y, we get f(m+f(n))=95+m+95+n=n+(95+(95+m))=n+f(95+m). [5]: At this point, we need that f is a function from N to N: if f(1)-f(0)
My own approach... Let m=95 Then f(95+f(n))=n+f(190) Now... Set, m = f(n)[since f:N->N taking f(n) is valid) It results in... f(f(n)+f(n))=n+f(f(n)+95) ................ = n+ f(95+f(n))= 2n+f(190) So, f(2n)=2n+190 Now the crux move.... Set m = f(x) [x is natural number] We get two results from given definition, 1.f(f(x)+f(n))=n+f(x+95) 2.f(f(n)+f(x))=x+f(n+95) Subtracting 1 from 2 We get f(x+95)-x=f(n+95)-n Thus f(n+95)-n= c [where c is a constant] So f(n+95)=n+c Set n=k-95 And get f(k) = k+c-95 So f(2(f(n))= 2(f(n))+c-95 >>>>>>>>> = 2(n+c-95)+c-95 >>>>>>>>> = 2n+3c-285 But f(2(f(n))= 2n+f(190) >>>>>>>>>>= 2n+c+95 Thus 2n+c+95=2n+3c-285 So..c=190 It means f(k)=k+95..TGPS...😇
I'm not sure whether anybody else has mentioned this here before: I think Michael only proved that the linear function is a solution to that additive functional equation. He did not prove that this is the only possible solution. Or am I missing something?
I applied the same logic. And even if one were to skip on proving the solution thus derived is unique the sum of f(k) over k=1 to 19 must be unique and hence correct.
Replace n with m+f(n) in the original equation. You'll get f(n+t)-f(n)=t, where t=m+f(m+95) Observation is that f(n)=n+c Prove it the same way as in video. Put this in original equation to get c=95.
Add k to both sides. Now left compose bots sides with f, apply given equation you get, f(n+k+95)=f(n)+f(k+95) Then define g:=f-95 The rest (from 7:47 onwards) is similar. No need to play around with g
Maybe you could try a case by case approach: x>1: If y>1 then x^y >1 If y=1 then y^x + x^y = 1 + x > 1 If y1 Just realized x^y > 1 in all those cases xD The only problem could be x,y
@@ricardocavalcanti3343 That's good enough, in that case the minimum is on the boundary, and since the value of the function on the boundary is 1 and since the boundary is not included in the domain, the function is strictly >1.
Hello, tentative simpler solution... STEP 1 For any y and m there exist n = y - f(m+95). So there exist n so that y = n + f(m+95) So per the definition there exist n so that y = f(m + f(y - f(m+95)) ) = f(x) Conclusion : for any y there exist an x so that y = f(x) STEP 2 With m=0 we get f(f(n)) = f(95) With m=1 we get f(f(n)+1) = f(96) So for any n : f(f(n)+1) - f(f(n)) = f(96) - f(95) = a constant let's say K But for any y there is an n so that f(n) = y So for any y : f(y+1) - f(y) = K CONCLUSION f is linear on integers. It is easy from there to fing f(x) = x + 95 QED
@@wasitahmid749 In many places the set of natural numbers is defined to contain 0. You are correct though that the problem specifies that 0 is not included.
in your case, f(x)=95+x is only true when x=f(95) or f(f(0)). f(95) or f(f(0)) is a constant but not a variable. if f(3)=95+3, you cannot claim that x=3, therefore, f(x)=95+x
If you assume f(x)=ax+b for some a,b from the get-go, you can eliminate all of the substitutions. Just plug in and rearrange to get b=n/a+95-an, which can only be a natural number for all n if a=1, thus b=95.
Actually for functions defined in real numbers linear class is not the only one satisfying additive property. There are some really weird functions that can satisfy it. These functions are discontinouos at every point.
g(m+g(n))=n+g(m)=> g(n)-bijection (if g(n)=g(k) then left sides are equal, but right sides are different). g(m+n)=g(m)+g(n)=g(m+g(n))=> g(n)=n because of bijection.
Surjectivity isn't needed(and so neither bijectivity). Injectivity suffices enough for alternative argument. The eq above doesn't generally imply surjectivity as the value g(m) could hinder the varying n from taking all values in ℕ-k (here, k in place of 95)
Much simpler way: let m = 0. so f(f(n)) = n + f(95). Therefore f(n) is a linear function, since f(95) is a constant. f(f(0)) = f(95), so f(0) = 95. therefore f(n) = n + 95
Alternative solution: if m= 0 f(f(n)) = n + f(95). Let f(95) = k and g(x)=f(f(x)), só we have: g(n) = n + k. Since we are working with the Natural Numbers and g is linear, we can think f as polynomial with integer coefficients, so is quite natural to realize that f has to be linear, so let f(n) = an + c, we have a(an + c) + c= n + k , and from this we can conclude that a^2n = n -> a=1 (because of the polynomial equality rule) and replacing it in the original equation, we get f(n) = n + 95.
you can`t plug 0, since it`s a function from the natural numbers to the natural numbers. (no zero included, as he states in the beggining of the video)
assume P(m,n) as a notation for plugging m and n, respectively, at the function f. ----------------------------------------------------------------------------------------------------------------------------- let a, b be natural numbers s.t f(a) = f(b) = c. P(1,a) -> f(1 + f(a)) = a + f(96). ->f(1+c) = a + f(96) P(1,b) ->f(1 + f(b)) = b + f(96). ->f(1+c) = b + f(96). -> a + f(96) = b + f(96). -> a = b. -> f is injective ----------------------------------------------------------------------------------------------------------------------------- P(m, n+x) [x is a natural number] -> f(m + f(n+x)) = [n + f(m + 95)] + x -> f(m+f(n+x)) = f(m + f(n)) + x for all natural m,n,x. P(n, f(m)) [m is a natural number, so f(m) is a natural number] ->f(f(m) + f(n)) = n + f(f(m) + 95) ->f(f(m) + f(n)) = f(f(m+n) + 95) [via the relation i proved above] ->f(m) + f(n) = f(m+n) + 95 [via injectivity] -------------------------------------------------------------------------------------------------------------------------- now, we have to deal with a much simpler f.e: f(m) + f(n) = f(m+n) + 95 P(m,1) -> f(m) + f(1) = f(m+1) + 95. [let f(1) - 95 = c] -> f(m+1) = f(m) + c basically, f is an arithmetic progression. -> f(n) = f(1) + (n-1)*(f(1)-95) plugging this into the original equation, we get that f(1) = 96 is the only valid solution. -> f(n) = 96 + (n-1)*1 -> f(n) = n + 95.
I love that it has the sum goes up to 19, the RHS has 95, and the sum is 1995. Brilliant!
That subtle use of the associativity of the addition on g is AWESOME!!! Such a nice trick!
It is obvious from 4:16 that g is an involution (exchanges n and m, so applying it twice gives back the same thing). This shortens the last part, as involution immediately leads to A=1.
16:22
A good place to s...
At 13:45, didn't you forget to transcribe a "+95" in evaluating the left hand side ? I really enjoy your work Professor Penn, btw.
same doubt here. But I think since it ends with a nice little value, there was another mistake somewhere else so the double mistake cancelled each other out?
He didn't write the 95 because there would be one 95 in the rhs too so he cancelled them both without mentioning:)
He forgot a 95 in the LHS
@@lisandro73 he also missed a +95 when he applied f on the rhs
I think he’s making these “auto-cancelling double mistakes” on purpose
13:38 you actually didn't write the +95 behind A(m+95)
Luckily he loses the +95 from the LHS when writing down the next line, and it matches out :-)
Thanks!
I was just about to comment on that, too.
13:41 you forgot to add 95 to rhs.
But then you ignores the 95 on lhs.
Two wrongs make a right...
minus minus is plus
Michael should write a book with the subjects/problems from all his TH-cam videos, perhaps categorized by college course and/or subject matter (e.g., Japanese temple problems). I'd buy it.
“Peach parentheses” - love it. I wonder if that phrase has ever been uttered before
In a previous video, no doubt
@@MrRyanroberson1 it was! I watched another one where he said it
White chalk, peach chalk could be a good name of a channel...
Oh wait!
Who knew that the solution of a problem would be the year of the problem
I’m sure a few contestants got that one right, after being messed up for 3h and the supervisor says, time, they write down, paniced, 1995. And what do you know
@ゴゴ Joji Joestar ゴゴ r/woosh
@ゴゴ Joji Joestar ゴゴ Yes! Lol, I didn’t even notice.
@@tomatrix7525 Though guessing the answer isnt worth any points. There is no point in guessing 1995 since even if you are right you wont get anything for it.
The best part of it is that the inputs are the year too.
Shouldn't there be a +95 at 13:44?
yeah I think so, but it cancelled with a 95 on the other side, which he didn't mention.
@@evanev7 I'm not so sure. There was a 95A on the RHS but no 95
@@bigern73 RHS at 13:31 should be n+A(m+95)+95, so they cancel.
Sir ... What are some good books for Functional Equations
Thats a good question
I read from BJV
Look at the Functional Equation Book by Amir Hossein Parvardi from AoPS. Definitely enjoyable and useful
Гольдфарб
@@electrovector7212 thank you sir
Problem:
|2^n + 5^n - 65| is a perfect square.
Find all such positive Integers 'n' .
Here |x| is a absolute value of 'x'
Hey Michael, plz make a vedio on the solution of this problem 🙂
Is this sum from IOQM?
Small comment about induction:
Induction principle: Let S:N->N be the follower function of natural numbers. The induction axiom says that if A is a subset of N where
0 is in A and
the image of A under S is included in A,
then A = N.
In other words the induction hypothesis should be of the form that let any k be in A. The induction statement is then that S(k) is in A.
The point is that to assume that some k exists in A and S(k)\in A is not formally correct way to do induction. This property holds for the subset {0,1} of natural numbers.
i love this chap.
That is nice
The "proof" (ending at about 12:00) that g(m) =Am is the solution to the functional equation g(r+s)=g(r)+g(s) only proves that such a form behaves linearly, not that it is the only functional form behaving that way.
Exactly
What do you mean? He did prove (by induction) that a function on the natural numbers that satisfies g(r+s)=g(r)+g(s) for all natural numbers r and s must have the form g(n)=An for a constant A.
@@Notthatkindofdr No, he proved by induction that a linear function satisfies the constraint g(r+s)=g(r)+g(s). He didn't prove that this is the only functional form that satisfies that constraint. (If we were operating over the reals instead of the natural numbers, for instance, the assertion would be false. There are nonlinear functions that satisfy the additive property.) A little more work is required. See, for instance, the Wikipedia article on Cauchy's functional equation en.wikipedia.org/wiki/Cauchy%27s_functional_equation
@@TedHopp I think you are forgetting that in this case g is only defined on the natural numbers. An induction proof shows that g(n)=An must be true for all natural numbers n, which is the only thing being claimed by Michael. This case is so simple, it is brushed over very briefly in the Wikipedia article you mentioned: at the beginning of Case II, equation (*), where we have alpha=n and x=1 (and g(1)=A), and it just refers to "repeated application of Cauchy's equation", i.e. induction. Edit: Maybe you are really complaining about 10:10 where he says "there is only one class of functions" that satisfies the additive rule, without specifying that he means "on the natural numbers".
@@Notthatkindofdr I'm not saying that the assertion of uniqueness is false, just that the proof offered doesn't prove uniqueness. The argument given in the Wikipedia article, by contrast, does prove uniqueness (for the rationals).
At 13:29 you forgot a +95 at the end (but in the next step you dropped it on the left hand side, so these errors cancelled out ...)
you really made 95 disappear from your equations at 13:28 and 13:43, as you said you would in your hint, but that was real magic, not mathematical magic... ;-)
14:49 don't you mean applying g to 100?
I believe so, since g(1) would give something in the codomain anyway (-1) so 100(or really anything larger) would make senseto shoe we reject A = -1
El final fue épico, no me lo esperaba.
At 13:31 there is a mistake. On the right hand side, +95 is missing!!
It's missing on the LHS as well at 13:45 so it all works out in the end
If you take his hint and look for a linear function which satisfies that functional equation you get the function very quickly.
But that doesn't help you to prove that its the unique function that satisfies the equation
@@FadkinsDiet That's absolutely true.
The base case for the additive equation is not n = 1 but n = 0 instead. So proving g(0) = 0 which comes from g(0+0) = g(0)+g(0).
A very cool answer. Who discovered that?
I wonder if there is a general proof that all f(X + f(Y)) type problems will be linear? I feel like jumping to f(X) = aX + b whenever I see one.
Possibly using partial derivatives, in a sense? This solution is linear because the n term on the right is linear.
I.e. for this problem, taking the derivative of both sides wrt n gives f'(n)f'(m+f(n)) = 1, and since f' maps to positive integers, we must have f'(n) = 1 for all n, which implies f(n) = n + k for some k.
Plugging into the equation gives k = 95.
And if you replace the n with n^2, then the equation you get is f'(n)f'(m+f(n)) = 2n for all m,n.
Assuming f'(n) ≠ 0, we get that f'(a) = f'(b) for all a,b > min(f(n)), so f(n) = n + k for sufficiently large n.
Plugging in to f(m + f(n)) = n^2 + f(m+95) gives m+n+2k = n^2 + m + 95 + k, which implies k = n^2 ‐ n + 95, but that's not a constant, so we get a contradiction.
You can make your own functional equation for a quadratic too. For example, if f(n) = n^2 + 1, then it satisfies f(m+f(n)) = f(m+1) + f(f(n)) + 2mf(n) - 2m - 1.
We can recover it by taking the derivative of that equation wrt n:
f'(n)f'(m+f(n)) = f'(n)f'(f(n)) + 2mf'(n),
So again assuming f'(n) ≠ 0, we get f'(m+f(n)) = f'(f(n)) + 2m, which shows that f'(n) = 2n + A for some A, which shows that f(n) = n^2 + An + B. And then plugging this in and solving should recover A,B
youtube algoirhtm blessing, i stumbled upon this problem on Titu's functional equation book with a fixed natural number k in place of 1995
In 1995, I would be very suspicious if I saw the 19 as a limit of the sum because it is a factor of 1995. So if I don't see a 1995 in the solution, I would figure I did something wrong and double-check where I might have gone awry.
Math competitions seem to like such “coincidences”. If I saw that I would assume it was right because of the meta game.
Om the other hand if I see that the answer I got was 1995,I would be sure that I got it right..but wait...what if the question setter was evil and if there was a point where we had to add one and you missed it thinking you got 1995 and it's year
1995 so you don't recheck and answer was somehow 1996...
@@harshanand127 you would think -- but it never happens.
Has it been shown that this is the only solutions of f(n) that satisfy the equation?
Can anyone find a functional equation (the domain and codomain dont matter) that is satisfied by a linear function (ax+b) AND a nonlinear function?
Myself i haven’t seen any, so i think you could conjecture that if a linear function satisfies a functional equation, then only linear function(s) satisfy the functional equation. Then, memorize the proof so you can use it on olympiad problems and such whenever a linear function turns out to be a solution by inspection. That would help because on this problem it wasn’t hard to find that x+95 worked, but the proof that it was unique was tough.
f(f(x)) = x.
f(x) = x is a solution.
f(x) = -x is a solution.
f(x) = 1/x is a solution.
f(x) = -1/x is a solution.
14:53 co-domain? I learned that the set of outputs of a function was the range.
When you define a function f:A -> B, B is called the co-domain. The range is f(A), the set of all values that are actually obtained by f, which is a subset of the co-domain but may be smaller.
From 13:29, a bit confusing what's happening with 95's.
Bravo professor
Thx
How would G(1) give -100 given A being -1, g = An = -1(1) = -1 ? It is in the co domain then?
He meant G(100)=-100.
@@Артем-х9у9к that would make alot more sense. Thanks
awesome video
It seems to me that you showed that g(n) = A.n is a function that satisfies g(a+b)=g(a)+g(b), but you didn’t appear to show that this is the only class of functions that meets the condition.
Also it seems that you dropped a 95 in the determination of A I think
That's what he proved by induction. Let g be a function satisfying the condition on natural numbers, define A=g(1), and then he proves that g(n)=An for all natural numbers n.
Wow...easy one!!!
They had a very similar functional problem in 2018 i think
Once you get that g(m+n) = g(m) + g(n), you obtain that g(g(m)) =m, so A is 1
Ok, another way to solve this:
Plugging in 0 for m, we get f(f(n))=n+f(95) [1] or f(f(n))-f(95)=n. Since this is true for all n in the natural numbers, we know that f is injective and the function g: Im(f)->N g(x)=f(x)-f(95) is its inverse. On the other hand, plugging in m=1, we get f(1+f(n))-f(96)=n. Hence, also h:Im(f)->N h(x)=f(1+x)-f(96) is an inverse function for f. But since the inverse function is unique, we get f(1+x)-f(96)=f(x)-f(95) for all x in Im(f). Rearranging, we get f(1+x)-f(x)=f(96)-f(95) for all x in Im(f) [2].
On the other hand, f(f(0))=f(95), which by the injectivity of f means f(0)=95.
By f(n)+f(95)=f(f(f(n)))=f(n+f(95))=95+f(n+95) (LHS: plug in f(n) for n in [1], RHS: plug in [1] into the inner function and then the original equation)
Rearranging: f(95)-95=f(n+95)-f(n) for all n in N [3].
In particular: f(95)-95=f(96)-f(1) or f(1)-95=f(96)-f(95), so f(1+x)-f(x)=f(1)-f(0) for all x in Im(f), i.e. f(1+x)=f(x)+f(1)-f(0) for x in Im(f) [4].
Now, since for any x>=f(95), we can choose y=f(x)-f(95) to get f(y)=x, Im(f) contains at least all numbers greater than f(95). Hence, we have f(x+f(95))=f(f(95))+x*(f(1)-f(0)) for all x>=0, where the second equation stems from [1]. However, because f reaches all values x for x>f(95), there is in particular some y in Im(f) with y>max(f(95),f(f(95)) such that y+1 is also in Im(f). Thus, there is some pair of integers x1,x2 such that f(f(95))+x1(f(1)-f(0))=y, f(f(95))+x2(f(1)-f(0))=y+1. Subtracting, we get (x1-x2)(f(1)-f(0))=1. Now, clearly (x1-x2) and (f(1)-f(2)) are both integers dividing 1. Now, we have f(1)-f(0)>0 [5, see below], so this means f(1)-f(0)=1, so f(x+f(95))=f(f(95))+x.
Since f(n+95)-f(n) is constant by [3], and we clearly have f(95+f(95))-f(f(95))=95, we have f(n+95)-f(n)=95 for all n. In particular, since we know 95 values in progression, we can go backwards and get f(x+f(95))=f(f(95))+x for all x in N-f(f(95)). Substituting y for x+f(95), we get f(y)=f(f(95))-f(95)+y. Plugging in y=0 and f(0)=95, we get f(y)=95+y.
And indeed: with f(y)=95+y, we get f(m+f(n))=95+m+95+n=n+(95+(95+m))=n+f(95+m).
[5]: At this point, we need that f is a function from N to N: if f(1)-f(0)
You cannot plug 0 as m is a natural number.
@@siddharthavlash1982 0 is a natural number. (At least for most people it is)
@@ElchiKing"at least for most people" No
My own approach...
Let m=95
Then f(95+f(n))=n+f(190)
Now...
Set,
m = f(n)[since f:N->N taking f(n) is valid)
It results in...
f(f(n)+f(n))=n+f(f(n)+95)
................ = n+ f(95+f(n))= 2n+f(190)
So, f(2n)=2n+190
Now the crux move....
Set m = f(x) [x is natural number]
We get two results from given definition,
1.f(f(x)+f(n))=n+f(x+95)
2.f(f(n)+f(x))=x+f(n+95)
Subtracting 1 from 2
We get f(x+95)-x=f(n+95)-n
Thus f(n+95)-n= c [where c is a constant]
So f(n+95)=n+c
Set n=k-95
And get f(k) = k+c-95
So f(2(f(n))= 2(f(n))+c-95
>>>>>>>>> = 2(n+c-95)+c-95
>>>>>>>>> = 2n+3c-285
But f(2(f(n))= 2n+f(190)
>>>>>>>>>>= 2n+c+95
Thus
2n+c+95=2n+3c-285
So..c=190
It means f(k)=k+95..TGPS...😇
Equalities 1 and 2 do not seem correct. f(x+95) should be f(f(x)+95)
13:24 did he forget +95?
I'm not sure whether anybody else has mentioned this here before: I think Michael only proved that the linear function is a solution to that additive functional equation. He did not prove that this is the only possible solution. Or am I missing something?
This is magnificent
if you take n=m+95 you get f(m+f(m+95))=(m+f(m+95))+95 and this is trur for any m.
But you can't say that f(x)=x+95 for any x. Only for x which can be presented in the form m+f(m+95).
@@Артем-х9у9к yes .but there are infinite values of x= m+f(m+95) so you may say that the only function that satisfying this is f(x)= x+95
I applied the same logic. And even if one were to skip on proving the solution thus derived is unique the sum of f(k) over k=1 to 19 must be unique and hence correct.
I want to know how you comment before watching the video 🤣🤣
Isn't a proof of uniqueness of g() missing to provide a complete answer?
"Prove there is a unique..."
I wonder if it would be necessary in IMO or not.
Seems a bit overkill to use induction to prove that a linear function satisfies a linear property, no?
👍
Good
Yeah, lots of the functions in these functional equations are pretty inane.
I do not understand why applying g to one gives negative 100.
I do not understand why applying G to 1 gives -100 when A=-1.
Replace n with m+f(n) in the original equation. You'll get f(n+t)-f(n)=t, where t=m+f(m+95)
Observation is that f(n)=n+c
Prove it the same way as in video.
Put this in original equation to get c=95.
Add k to both sides. Now left compose bots sides with f, apply given equation you get,
f(n+k+95)=f(n)+f(k+95)
Then define g:=f-95
The rest (from 7:47 onwards) is similar. No need to play around with g
When I’m watching this I can’t stop thinking about Windows 95 :’)
Can anyone help me how to prove that, for all positive real numbers (x,y), x^y+y^x>1?
Maybe you could try a case by case approach:
x>1:
If y>1 then x^y >1
If y=1 then y^x + x^y = 1 + x > 1
If y1
Just realized x^y > 1 in all those cases xD
The only problem could be x,y
Define f(x,y)=x^y+y^x, and use calculus to find the minimum.
@@mathunt1130 There is no minimum in the first quadrant, only a saddle point.
@@ricardocavalcanti3343 That's good enough, in that case the minimum is on the boundary, and since the value of the function on the boundary is 1 and since the boundary is not included in the domain, the function is strictly >1.
@@mehdimarashi1736 Good point!
I found the finding of the Cauchy functional equation that g satisfies a bit unmotivated...
Hello, tentative simpler solution...
STEP 1
For any y and m there exist n = y - f(m+95).
So there exist n so that y = n + f(m+95)
So per the definition there exist n so that y = f(m + f(y - f(m+95)) ) = f(x)
Conclusion : for any y there exist an x so that y = f(x)
STEP 2
With m=0 we get f(f(n)) = f(95)
With m=1 we get f(f(n)+1) = f(96)
So for any n : f(f(n)+1) - f(f(n)) = f(96) - f(95) = a constant let's say K
But for any y there is an n so that f(n) = y
So for any y : f(y+1) - f(y) = K
CONCLUSION
f is linear on integers.
It is easy from there to fing f(x) = x + 95
QED
Sorry in STEP 2 of course f(f(n)) = n+f(95) and f(f(n)+1) = n+f(95)
But the proof is still ok.
I just try:
n = 0, m = 0: f(f(0)) = f(95).
n = 95, m = 0: f(f(95)) = 95 + f(95)
X = f(f(0))
Then
f(X) = 95 + X.
Нельзя подставлять ноль в таких случаях, он не входит в область определения
It is defined on the NATURAL numbers man!!! Natural numbers means positive integers( greater than 0)...so you cannot actually have f(0)
@@wasitahmid749 In many places the set of natural numbers is defined to contain 0. You are correct though that the problem specifies that 0 is not included.
in your case, f(x)=95+x is only true when x=f(95) or f(f(0)). f(95) or f(f(0)) is a constant but not a variable. if f(3)=95+3, you cannot claim that x=3, therefore, f(x)=95+x
What proved that the only thing that would work was a polynomial line?
If you assume f(x)=ax+b for some a,b from the get-go, you can eliminate all of the substitutions. Just plug in and rearrange to get b=n/a+95-an, which can only be a natural number for all n if a=1, thus b=95.
let n=m+95, then f(m+f(m+95)) = m+f(m+95) +95 hence f(n)=n+95...
Actually for functions defined in real numbers linear class is not the only one satisfying additive property. There are some really weird functions that can satisfy it. These functions are discontinouos at every point.
f(n) =n+95 io l'ho fatto in 2 minuti
g(m+g(n))=n+g(m)=> g(n)-bijection (if g(n)=g(k) then left sides are equal, but right sides are different).
g(m+n)=g(m)+g(n)=g(m+g(n))=> g(n)=n because of bijection.
The identity g(m)+g(n)=g(m+g(n)) is not obvious to me. Can you derive it without using the fact that g(n)=n?
Surjectivity isn't needed(and so neither bijectivity). Injectivity suffices enough for alternative argument.
The eq above doesn't generally imply surjectivity as the value g(m) could hinder the varying n from taking all values in ℕ-k (here, k in place of 95)
Mr Michael. please tell me are you a harvard teacher , much respect, even some of the top teachers cant solve many you do
Much simpler way:
let m = 0.
so f(f(n)) = n + f(95).
Therefore f(n) is a linear function, since f(95) is a constant.
f(f(0)) = f(95), so f(0) = 95.
therefore f(n) = n + 95
correct me if im wrong but i think f(0) is not equal to 95 in your proof because you haven't proved that the function is injective
m can't be equal to zero.
Alternative solution: if m= 0
f(f(n)) = n + f(95). Let f(95) = k and g(x)=f(f(x)), só we have:
g(n) = n + k. Since we are working with the Natural Numbers and g is linear, we can think f as polynomial with integer coefficients, so is quite natural to realize that f has to be linear, so let f(n) = an + c, we have a(an + c) + c= n + k , and from this we can conclude that a^2n = n -> a=1 (because of the polynomial equality rule) and replacing it in the original equation, we get f(n) = n + 95.
But still, I prefer Michaels way of solving the problem, I think it’s more creative
you can`t plug 0, since it`s a function from the natural numbers to the natural numbers. (no zero included, as he states in the beggining of the video)
assume P(m,n) as a notation for plugging m and n, respectively, at the function f.
-----------------------------------------------------------------------------------------------------------------------------
let a, b be natural numbers s.t f(a) = f(b) = c.
P(1,a)
-> f(1 + f(a)) = a + f(96).
->f(1+c) = a + f(96)
P(1,b)
->f(1 + f(b)) = b + f(96).
->f(1+c) = b + f(96).
-> a + f(96) = b + f(96).
-> a = b. -> f is injective
-----------------------------------------------------------------------------------------------------------------------------
P(m, n+x) [x is a natural number]
-> f(m + f(n+x)) = [n + f(m + 95)] + x
-> f(m+f(n+x)) = f(m + f(n)) + x for all natural m,n,x.
P(n, f(m)) [m is a natural number, so f(m) is a natural number]
->f(f(m) + f(n)) = n + f(f(m) + 95)
->f(f(m) + f(n)) = f(f(m+n) + 95) [via the relation i proved above]
->f(m) + f(n) = f(m+n) + 95 [via injectivity]
--------------------------------------------------------------------------------------------------------------------------
now, we have to deal with a much simpler f.e: f(m) + f(n) = f(m+n) + 95
P(m,1)
-> f(m) + f(1) = f(m+1) + 95. [let f(1) - 95 = c]
-> f(m+1) = f(m) + c
basically, f is an arithmetic progression.
-> f(n) = f(1) + (n-1)*(f(1)-95)
plugging this into the original equation, we get that f(1) = 96 is the only valid solution.
-> f(n) = 96 + (n-1)*1
-> f(n) = n + 95.
Bravo professor