17:49 i think there's a mistake. Equating the arguments gives f(n)+1 = n+1 =>f(n)=n , but not f(n+1)=f(n)+1 like shown on the board. Correct reasult either way :)
I think a good video topic would be Cauchy's functional equation. It's the equation f(x+y)=f(x)+f(y), and you could show the proof that solutions exist not of the form f(x)=ax, and that all such solutions are dense, i.e the function passed through all discs on the plane no matter how small.
the existence of such solutions is not trivial at all tho, it requires the use of axiom of choice and knowledge about its various equivalent forms.. how would you approach this?
At 17:50, I believe you meant to write that 1 + f(n) = n + 1, since that's the interior of those two functions. From that, it's immediately obvious that f(n) = n.
A little faster way is to prove injectivity is to realise that when holding f(m+n) constant (e.g. choosing m->m+x and n->n-x) and changing x, we get arbitrarily large image of f (when n is chosen carefully), which proves that f is clearly not periodic.
@@andrewulinov3920 That is why we need to select n to be sufficiently large and then intuitively when we let n approach infinity, we get infinitely large image of f.
Nah we're only talking about numbers bigger than/equal to zero so you can't just take -n. Also you're using injectivity in your argumentation which means that it doesn't make the proof any shorter since showing injectivity was the only thing taking a lot of time
@@janekgroe4304 You're right about the first thing, but I think he wasn't using injectivity. He argued that, since the value of the function is zero, by the assumption that we made in the second case, the only possible way to get zero is for the argument of the function to be zero.
16:03 Is it really correct that f(y)=f(y+b-a), since we have only proved that the function is periodic from some point and not in the beginning as well.
a little nagging regarding the proof using [b-a] periodicity, if you ends up with b-a=0 then there is no periodicity, the image is not necessarily finite and does not necessarily have a maximum (as in the final results). a more rigorous way is to say, assuming b-a>0 there is periodicity... concluding b-a must be 0, in contradiction
What type of functions have m*f(x) = f(m*x). Is it just f(x) = a*x? I know linear operators like integrals have that but I guess they aren’t functions.
However, I still think m=/=0 because m=0 has only one solution that is f(0)=0 where x=0. In this way we can prove f(1), where x=1, x>=a, a=0, or a=1. When a=1, m=x-a=1-1=0 which is not accepted. So, a=0, the repeated value of f(1)=f(1+(b-a)) =f(1+b-0)=f(b+1). Last value of the first non-repeated series=f(b+1-1)=f(b)
Does anyone know of, or could anyone create, a functional equation which has both linear and quadratic solutions? I haven’t tried very hard to come up with one but it’s not clear to me how one would do it
There must be smarter or more elegant ones, but consider f(x+1)=f(x)^2+ 2(f(x)-x)/(x-1) +1. It seems to me (it's hard to pay full attention to tedious calculations though) that the only polynomials satisfying that equation are ax^2+bx for a+b=1. I didn't try to find an argument discarding more general functions. Here's how I generated that equation. I started with f(x+1)=x+1, obviously satisfied by f(x)=x. For the square function, we have f(x+1)=f(x)+2x+1, which is rather similar. To cram both identities in one single expression we write f(x+1)=f(x)+1+g(x) and look for some g that becomes 0 for f(x)=x and 2x for f(x)=2x. The first requirement is easy, we'll just put a factor (f(x)-x) in the definition of g to make sure it is 0. That yields x^2-x when f is the square function, while we want 2x. We just multiply by 2x/(x^2-x), that is, 2/(x-1) and we are done: both x and x^2 are solutions to f(x+1)=f(x)+1+ (f(x)-x)*2/(x-1).
you can actually get the answer from f(m^2)=mf(m) by assuming f(m)=sum of i from 1 to inf a(i)*m^i (no need for 0-th term because f(0)=0). S is sum from 1 to inf. then we get S(a(2i)*m^2i) = S(a(i)*m^(i+1)) First term is a(1)*m^2 for both, plus all a(even) are 0 because they are coefs for m^odd which exists only on the right side and it has to work for any natural m. By getting rid of all of that, Sum from 2 to inf (a(i)-a(2i-1))*m^2i = 0 so every single a(i)-a(2i-1) is 0. For any odd value of i we get a(i)=a((i+1)/2) but we'll eventually get to a(even) on the right side, so all values of a except a(1) are 0. Thus f(m)=a*m. You can find a being either 1 or 0 by putting f(m) into initial equation.
You went from f(1 + f(n)) = f(n + 1) to f(n + 1) = f(n) + 1 quoting injectivity. But wouldn't injectivity yield, f(n) + 1 = n + 1, then immediately follows that f(n) = n. If f(a) = f(b), then a = b. Here a = f(n) + 1 and b = n + 1.
I went a different way at about @1:30. After determining that f(0) = 0 with the substitution m = 0, I determined that f(m^2) = m f(m) with the substitution n = 0, from which it was pretty straightforward to prove that f(n) = C n, for some constant C. Substituting this into the original functional equation gave the only possible values for C of 0 and 1.
"from which it was pretty straightforward to prove that f(n) = C n, for some constant C" I don't see how this follows straightforward. Could you please explain?
@@bjornfeuerbacher5514 I was a bit inaccurate in my statement. It's straightforward to prove it, _assuming_ f(n) is a polynomial, which is a bit sloppy. With this assumption, f(n) = a[0] + a[1] n + a[2] n^2 + ... + a[k] n^k. Since f(0) = 0, it must be that a[0] = 0. Expanding the functions on both sides of the equation f(n^2) = n f(n) gives: a[1] n^2 + a[2] n^3 + ... + a[k] n^(k+1) = a[1] n^2 + a[2] n^4 + ... + a[k] n^(2 k) Since these are identically equal, and the expansion on the right hand side has no terms of odd degree, the coefficients of the terms of odd degree on the left hand side must all equal zero, which gives a[2 j] = 0. Equating the remaining terms gives a[2 j-1] = a[j], for all j > 1. When j is even, a[2 j-1] = 0. When it is odd, since j = 2 ((j+1)/2) - 1, j can be replaced by (j+1)/2, giving a[2 j-1] = a[(j+1)/2]. Since (j+1)/2 < j for all j > 1, and there are a finite number of integers between 0 and any finite number j, this descending sequence must eventually terminate. Further, for all odd integers j > 1, the least possible value of (j+1)/2 is 2 (this can be proved by assuming that (j+1)/2
Here was my process f(m²+mf(n)) = mf(m+n) When m = 0 we get f(0) = 0 When n = 0 we get f(m²) = mf(m) m = 1 gives us f(1+f(n)) = f(n+1) Applying the inverse function on both sides gives us f(n)+1 = n+1 Or f(n)=n Meaning that our solution is f(x) = x Also, when looking at our function, we can easily see that f(x)=0 works. Less rigorous, but similar results.
You can prove the injectivity from periodicity directly, because periodic implies finite image, but the given assumption for large enough m gives large enough f.
f(m^2 +m*f(n))=n*f(m+n). (1) Take m=n. f(n^2 +n*f(n))=n*f(2n). (2) Since f(n) represents the set of non-negative integers in the same, then looking for it in the form of a series n with non-negative degrees: f(n)= a0+ a1*n +a2*n^2 +a3*n^3 +... (3) Substituting (3) into (2) seems cumbersome, but it quickly gives the desired result. a0 + a1*(n^2+n*f(n)) +a2*(n^2+n*f(n))^2 +a3 *(n^2 +n*f(n))^3+........= = n*a0+n*a1*2*n+n*a2* (2*n)^2 + n*a3*(2*n)^3+...... a0+a1*n^2 +a1*(n*a0+n*a1*n +n*a2*n^2+n*a3*n^3+....)+ a2*(n^4 +2*n^3 *a0+...+n^2*a0+....=a0*n+2*a1*n^2 +4*a2*n^3+.... It follows that there is a trivial solution: a0= a1=a2=a3...=0, => f(n)≡0 And there is a solution a0=0, a1=1 , a2=a3=...=0. => f(n)=n. (4) Substituting (4) into (1), we get m^2+mn=n*(m+n) => m=n (we take into account that m and n are non-negative integers). Answer: f(n)=n, m=n and f(n)≡0. I note that f(n)=n the solution is not only for m=1, but for m=n.
@@fullfungo he didn't assume that it was a polynomial he assumed it has a series representation which is still not allowed for functions from uncountable sets to uncountable sets but because ℕ∪{0} is countable he can assume there is a series representation...
I'm lost at 9:40. Why do you assume that y and z are integers? It seems to me it's just an hypotesis you made, and as such y+z = 1 can have other solutions, rather than y or z being 1 and the other being 0.
I got a much better solution but i dont see anyone talking about it so there s a chance it s wrong: We can easily get f(0)=0 , then using the eq f(m)=f(m^2)/m and plugging in x^2 , x^4 etc we get: f(m)=f(m^2)/m=f(m^4)/m^3=....= f(m^(2^n)/m^((2^n)-1). Set u=m^(2^n), assuming m>=2 and sending n to infinity we have : f(m)=m • lim u->inf f(u)/u . The lim has to exist and be a real number (cause it s ewual to f(m) ) so we have f(m)=bm. Plugging back into the original we can easily get b=1, then just find f(1) (cause we assumed m>=2) and we are done
I know it varies between mathematicians and ‘areas of interest’, but I’d really prefer you remained true and faithful to the Von Neumann (pr/ Vonn Noy-munn) natural numbers which start from Ø (ie. zero, 0), then {Ø}, {Ø,{Ø}}, {Ø, {Ø}, {Ø,{Ø}}} and so on. I’m sure you, Michael, are familiar with Undergraduate Logic & Set Theory, I just include it for completeness and interest for other readers.
17:49 i think there's a mistake. Equating the arguments gives f(n)+1 = n+1 =>f(n)=n , but not f(n+1)=f(n)+1 like shown on the board. Correct reasult either way :)
Lol, yeah!
LOL...yeah obviously....big error although the final answer came out correct
That was what I thought as well.
yeah lol
A lucky error indeed!
I think a good video topic would be Cauchy's functional equation. It's the equation f(x+y)=f(x)+f(y), and you could show the proof that solutions exist not of the form f(x)=ax, and that all such solutions are dense, i.e the function passed through all discs on the plane no matter how small.
the existence of such solutions is not trivial at all tho, it requires the use of axiom of choice and knowledge about its various equivalent forms.. how would you approach this?
at 16:03 we apply periodicity, but we have only proved that f(x+b-a)=f(x) if x>=a. We can prove pretty easily that y=1: f(y^2)=yf(y)
18:39 Indian flag on the thumbnail gonna bring a lot of viewers and comments…
At 7:30, wouldn't it be easier to write f(y) >= f(y2)=yf(y)>f(y) unless y=0?
This is so brilliantly instructive, nice explanation
09:00 Use twice the period, i.e., f(y + 2z) = f(y+z) = f(z), leading to (y+2z-1)f(y) 0, so f(y)=0.
At 17:50, I believe you meant to write that 1 + f(n) = n + 1, since that's the interior of those two functions. From that, it's immediately obvious that f(n) = n.
Wrong step again leads to correct solution😂
A little faster way is to prove injectivity is to realise that when holding f(m+n) constant (e.g. choosing m->m+x and n->n-x) and changing x, we get arbitrarily large image of f (when n is chosen carefully), which proves that f is clearly not periodic.
I was thinking about just saying that if there's a period, then there would be infinite z s.t. f(z)=0, which contradicts our assumption from case 2
Well, you are not able to do this. When changing x your new variable (n := n-x) becomes negative, and we are working in nonnegative numbers.
@@andrewulinov3920 That is why we need to select n to be sufficiently large and then intuitively when we let n approach infinity, we get infinitely large image of f.
at the point that we got f(m^2)=mf(m) I guess the solution would be the identity, though I wouldn’t have been able to show it. great video!
For case 2, we could set m=-n, then f(n^2-nf(n))=0, by case 2 assumption, n^2-nf(n)=0 => f(n)=n
Nah we're only talking about numbers bigger than/equal to zero so you can't just take -n. Also you're using injectivity in your argumentation which means that it doesn't make the proof any shorter since showing injectivity was the only thing taking a lot of time
@@janekgroe4304 You're right about the first thing, but I think he wasn't using injectivity. He argued that, since the value of the function is zero, by the assumption that we made in the second case, the only possible way to get zero is for the argument of the function to be zero.
@@andrycraft69 oh yes right I forgot we assumed "injectivity at 0"
16: 10 How do we know that f(y) = f(y + b - a), we have the periodicity only for y => a, right?
Great video, prof Penn:) Thanks!
Can anyone help explain 9:50? Could the function no just be negative everywhere except its maximum?
In the problem statement, the function is defined as having its codomain be the non-negative integers, so f(x) can never be negative.
It could, but the original equation asks us to only look at functions from the non-negative integers to the non-negative integers.
Brill thanks guys
Pro tip: Don't use country maps
16:03 Is it really correct that f(y)=f(y+b-a), since we have only proved that the function is periodic from some point and not in the beginning as well.
This is a tough one. Well done, Michael!
Now what if it was over the rationals or the reals?
At 13:27 you should require x>a so that m does not equal zero
This video was a whole lot of magic for me. Lol. Cool result!
It is impossible for f(x) to be periodic because f(m^2)=mf(m) can be arbitrarily large unless f(x) is always 0. This would save a lot of time.😂
In the second case, how can f(n) have the behavior of "periodic after a point" if it's injective?
That's what...the period was b-a which is 0.
This by definition of periodicity, f(x) = f(0+x) which is an identity.
a little nagging
regarding the proof using [b-a] periodicity, if you ends up with b-a=0 then there is no periodicity, the image is not necessarily finite and does not necessarily have a maximum (as in the final results). a more rigorous way is to say, assuming b-a>0 there is periodicity... concluding b-a must be 0, in contradiction
is the same, b-a=0 means no periodicity but also means injectivity is true
What type of functions have m*f(x) = f(m*x). Is it just f(x) = a*x? I know linear operators like integrals have that but I guess they aren’t functions.
Yes, because f(x)=f(x*1)=x*f(1), that is, we have a=f(1).
14:28 How do we know f(b) is the last value in the image?
x>=a, x=/=0
x=0 satisfies f(0)=0 but not satisfies f(x) =f(x+(b-a)) because it states that f(x) =/=0 for x=/=0
In other words it means image of f cannot have a repeating value of zero
However, I still think m=/=0 because m=0 has only one solution that is f(0)=0 where x=0. In this way we can prove f(1), where x=1, x>=a, a=0, or a=1. When a=1, m=x-a=1-1=0 which is not accepted. So, a=0, the repeated value of f(1)=f(1+(b-a))
=f(1+b-0)=f(b+1). Last value of the first non-repeated
series=f(b+1-1)=f(b)
Does anyone know of, or could anyone create, a functional equation which has both linear and quadratic solutions? I haven’t tried very hard to come up with one but it’s not clear to me how one would do it
There must be smarter or more elegant ones, but consider
f(x+1)=f(x)^2+ 2(f(x)-x)/(x-1) +1.
It seems to me (it's hard to pay full attention to tedious calculations though) that the only polynomials satisfying that equation are ax^2+bx for a+b=1. I didn't try to find an argument discarding more general functions.
Here's how I generated that equation. I started with f(x+1)=x+1, obviously satisfied by f(x)=x. For the square function, we have f(x+1)=f(x)+2x+1, which is rather similar. To cram both identities in one single expression we write
f(x+1)=f(x)+1+g(x)
and look for some g that becomes 0 for f(x)=x and 2x for f(x)=2x.
The first requirement is easy, we'll just put a factor (f(x)-x) in the definition of g to make sure it is 0. That yields x^2-x when f is the square function, while we want 2x. We just multiply by 2x/(x^2-x), that is, 2/(x-1) and we are done: both x and x^2 are solutions to
f(x+1)=f(x)+1+ (f(x)-x)*2/(x-1).
@@pedroteran5885 awesome, thanks!
Thank you, professor.
You have a mistake
If f injective
And for all n in N
f(1+f(n))=f(n+1)
Then 1+f(n)=n+1
Then f(n) =n
So the period o f is infinite?
you can actually get the answer from f(m^2)=mf(m) by assuming f(m)=sum of i from 1 to inf a(i)*m^i (no need for 0-th term because f(0)=0). S is sum from 1 to inf.
then we get S(a(2i)*m^2i) = S(a(i)*m^(i+1))
First term is a(1)*m^2 for both, plus all a(even) are 0 because they are coefs for m^odd which exists only on the right side and it has to work for any natural m. By getting rid of all of that,
Sum from 2 to inf (a(i)-a(2i-1))*m^2i = 0
so every single a(i)-a(2i-1) is 0. For any odd value of i we get a(i)=a((i+1)/2) but we'll eventually get to a(even) on the right side, so all values of a except a(1) are 0. Thus f(m)=a*m. You can find a being either 1 or 0 by putting f(m) into initial equation.
You're soooooooooo underrated!!!
Bonus points for using correct Indian map.
You went from f(1 + f(n)) = f(n + 1) to f(n + 1) = f(n) + 1 quoting injectivity. But wouldn't injectivity yield, f(n) + 1 = n + 1, then immediately follows that f(n) = n.
If f(a) = f(b), then a = b. Here a = f(n) + 1 and b = n + 1.
Non negative integers is called Whole numbers
An easier approach of this
Set m=n=0
f(0)=0×f(0)
~f(0)=0
m=n=1
f(1+f(1))=f(2)
~f(1)=1
m=1,n=n
f(1+f(n))=f(n+1)
1+f(n)=n+1
f(n)=n
I went a different way at about @1:30.
After determining that f(0) = 0 with the substitution m = 0, I determined that f(m^2) = m f(m) with the substitution n = 0, from which it was pretty straightforward to prove that f(n) = C n, for some constant C. Substituting this into the original functional equation gave the only possible values for C of 0 and 1.
"from which it was pretty straightforward to prove that f(n) = C n, for some constant C"
I don't see how this follows straightforward. Could you please explain?
@@bjornfeuerbacher5514 I was a bit inaccurate in my statement. It's straightforward to prove it, _assuming_ f(n) is a polynomial, which is a bit sloppy.
With this assumption, f(n) = a[0] + a[1] n + a[2] n^2 + ... + a[k] n^k. Since f(0) = 0, it must be that a[0] = 0. Expanding the functions on both sides of the equation f(n^2) = n f(n) gives:
a[1] n^2 + a[2] n^3 + ... + a[k] n^(k+1) = a[1] n^2 + a[2] n^4 + ... + a[k] n^(2 k)
Since these are identically equal, and the expansion on the right hand side has no terms of odd degree, the coefficients of the terms of odd degree on the left hand side must all equal zero, which gives a[2 j] = 0. Equating the remaining terms gives a[2 j-1] = a[j], for all j > 1. When j is even, a[2 j-1] = 0. When it is odd, since j = 2 ((j+1)/2) - 1, j can be replaced by (j+1)/2, giving a[2 j-1] = a[(j+1)/2]. Since (j+1)/2 < j for all j > 1, and there are a finite number of integers between 0 and any finite number j, this descending sequence must eventually terminate. Further, for all odd integers j > 1, the least possible value of (j+1)/2 is 2 (this can be proved by assuming that (j+1)/2
In general q*f(p) = f(q*p), q, p >1, but in general we can extend the function in Z, f( - k) = f(1+f(-k-1)), k>0.
a q p
w
Here was my process
f(m²+mf(n)) = mf(m+n)
When m = 0 we get
f(0) = 0
When n = 0 we get
f(m²) = mf(m)
m = 1 gives us
f(1+f(n)) = f(n+1)
Applying the inverse function on both sides gives us
f(n)+1 = n+1
Or
f(n)=n
Meaning that our solution is f(x) = x
Also, when looking at our function, we can easily see that f(x)=0 works.
Less rigorous, but similar results.
f has to be injective and surjective to have an inverse
You can prove the injectivity from periodicity directly, because periodic implies finite image, but the given assumption for large enough m gives large enough f.
f(m^2 +m*f(n))=n*f(m+n). (1)
Take m=n. f(n^2 +n*f(n))=n*f(2n). (2)
Since f(n) represents the set of non-negative integers in the same, then looking for it in the form of a series n with non-negative degrees:
f(n)= a0+ a1*n +a2*n^2 +a3*n^3 +... (3)
Substituting (3) into (2) seems cumbersome, but it quickly gives the desired result.
a0 + a1*(n^2+n*f(n)) +a2*(n^2+n*f(n))^2 +a3 *(n^2 +n*f(n))^3+........=
= n*a0+n*a1*2*n+n*a2* (2*n)^2 + n*a3*(2*n)^3+......
a0+a1*n^2 +a1*(n*a0+n*a1*n +n*a2*n^2+n*a3*n^3+....)+ a2*(n^4 +2*n^3 *a0+...+n^2*a0+....=a0*n+2*a1*n^2 +4*a2*n^3+....
It follows that there is a trivial solution:
a0= a1=a2=a3...=0, => f(n)≡0
And there is a solution
a0=0, a1=1 , a2=a3=...=0. => f(n)=n. (4)
Substituting (4) into (1), we get
m^2+mn=n*(m+n) => m=n (we take into account that m and n are non-negative integers).
Answer: f(n)=n, m=n
and f(n)≡0.
I note that f(n)=n the solution is not only for m=1, but for m=n.
Your step (3) is not well justified. You simply assume that f(.) is a polynomial, rather then prove it.
@@fullfungo he didn't assume that it was a polynomial he assumed it has a series representation which is still not allowed for functions from uncountable sets to uncountable sets but because ℕ∪{0} is countable he can assume there is a series representation...
Nice🙌
Functional equations are cool but it’s somewhat disappointing that we almost always end up with something like f(x)=x 😅
Nice video though!
The identity function
Damn , the map tho , lmao , nice problem I think i have seen this one outside of the Indian TST but maybe I am just making stuff up
It's very easy to solve by just setting m=1 -> f(1 + f(n)) = f(1 + n) -> f(n) = n
Bruh
You have to prove that the function is injective if you claim f(n) = n
I'm lost at 9:40. Why do you assume that y and z are integers? It seems to me it's just an hypotesis you made, and as such y+z = 1 can have other solutions, rather than y or z being 1 and the other being 0.
The function f is only defined for integers.
f is only defined for Z^nonneg \cup {0} or Z_{\geq 0}, therefore y, z are bound to be either 0 or 1 to have a sum of 1.
The question states that the domain and co domain of f is the set of non negative integers
I got a much better solution but i dont see anyone talking about it so there s a chance it s wrong: We can easily get f(0)=0 , then using the eq f(m)=f(m^2)/m and plugging in x^2 , x^4 etc we get: f(m)=f(m^2)/m=f(m^4)/m^3=....=
f(m^(2^n)/m^((2^n)-1). Set u=m^(2^n), assuming m>=2 and sending n to infinity we have :
f(m)=m • lim u->inf f(u)/u . The lim has to exist and be a real number (cause it s ewual to f(m) ) so we have f(m)=bm. Plugging back into the original we can easily get b=1, then just find f(1) (cause we assumed m>=2) and we are done
This solution also kinda works even if the domain was the reals
All this only for f(x) = 0
I know it varies between mathematicians and ‘areas of interest’, but I’d really prefer you remained true and faithful to the Von Neumann (pr/ Vonn Noy-munn) natural numbers which start from Ø (ie. zero, 0), then {Ø}, {Ø,{Ø}}, {Ø, {Ø}, {Ø,{Ø}}} and so on. I’m sure you, Michael, are familiar with Undergraduate Logic & Set Theory, I just include it for completeness and interest for other readers.
You are great...
Just let m=-a at 13:22 and you're instantely done
m can not be negative
@@dicksonchang6647 why not?
@@larspos8264 It is in the problem statement that m and n are non-negative.
@@kimbel2804 ofcouce, I only saw the Z, my bad
I don't know if you feel the same or not, but functional equation is the hardest topic for me 😬
No, at this point polynomials bother me more. Hopefully that changes.
Nice problem. A shame the answer is so often something simple when solving functional equations.
Yeet