a notorious functional equation.

🌟Support the channel🌟

🌟my other channels🌟

🌟My Links🌟

🌟How I make Thumbnails🌟

🌟Suggest a problem🌟

[cmilkau]

Who else looked at this and thought huh, f(2x²) = f(x²)?

[Bodyknock]

1:29 Obviously based on the statement that f(1)² = f(1) has "a single solution 1" he's defining 0 to not be a Natural Number. But note that whether or not 0 is defined as a Natural Number is a matter of context, in set theory for instance 0 typically IS a Natural Number since the Natural Numbers are defined as the cardinalities of the finite sets (including the empty set which has cardinality 0).

It might be an interesting aside to tweak the problem to include 0 and see what happens. Right off the bat, that opens up f(n) = 0 for various n as a possibility, for instance:

-- f(0²) = f(0) = f(0)² implies f(0) = 1 or f(0) = 0
-- Likewise f(1) = 0 or 1 as well. Note also that f(1) = f(1² + 0²) = f(1)f(0) must also be either 1 or 0. So if f(0) = 0 then f(1) = 0 as well, and if f(0) = 1 then f(1) = 1 as well (they have to be identical)\

-- f(2) = f(1² + 1²) = f(1)f(1), so if f(1) = 1 then f(2) = 1 and likewise if f(1) = 0 then f(2) = 0.

And so on. I'm out of time but my guess is if you follow the steps in the video, but assume f(0) = f(1) = 0 instead of being 1, you'll end up with the alternate solution f(n) = 0 for all n.

[Ardient_]

Why is half the comments debating if whether 0 should be included in |N LOL

[lucacastenetto]

(ac-bd)²+(ad+bc)²=(ac+bd)²+(ad-bc)², appling f and substituting b=c=1 we get:
f(a-d)f(ad+1)=f(a+d)f(ad-1)
If a, d≠1 ad+1>"the 3 other terms"
So using strong induction and the preliminary base cases we get that f of every number n st. n-1≠p (prime) is 1 (because if n-1 is prime we need to have a=1 or d=1).
So we know that f of every odd number is 1
Substituting b=c=1 and d=2 in the first equation we get:
f(a-2)f(2a+1)=f(a+2)f(2a-1)
Choosing a>2 and using strong induction we get that f(a+2)=1 completing the proof

[mathboy]

I did it the exact same way, but for a slight variant, you could use that for simple inductions it's often possible to do essentially the same reasoning, except assuming that there's a first violation of the induction, and then showing that that leads to a contradiction.

So here, you'd ASSUME there's an f satisfying the problem that isn't identically 1.
Then the set { f > 1 }, a subset of the naturals, isn't empty, and so by well ordering it has a least element n (i.e. f(n) > 1 and f(x) = 1 for 0 < x < n). Also, from f(1) = 1, have n > 1.

If n is even, have n = 2m, and using x = 2m, y = 1, get f(4m^2 -1) f(n) = [ f(m) f(1) ]^2 = f(m)^2. But m < n, so f(m) = 1, so RHS = 1, but and f(n) > 1, and f(4m^2 -1) >= 1, so LHS > 1, a contradiction.

Therefore n must be odd.

Thus n = 2m+1 for some m > 0 (as n > 1), and (as in the video) using x = m+1, y = m, get
f(n) f(2m^2 + 2m) = [ f(m) f(m+1) ]^2.
The same reasoning as with the even case (and as with the video): since m and m+1 are both less than n, by the def of n have f(m) = f(m+1) = 1, and so RHS = 1, but LHS, which is f(n)>1 times a natural, is greater than 1, a contradiction.

Thus the assumption was false and so f = 1 on the naturals is the only possible solution.
A quick check shows that f = 1 is a solution, and so that proves that it's the only solution.

As another tiny variant, since there's multiplication everywhere here, instead of showing a contradiction of one side > 1, other side = 1, you could use that a prime that divides n (since n > 1) must divide one side but not the other. That's possible, but not better (it's a bit worse... a touch more cumbersome than needed). However, in a different situation, such a divisibility observation might be the way to solve it.

Anyway, the "work" of the proof is basically identical whether you're doing a positive induction like in the video, or a proof by contradiction which assumes that the induction fails at some point. (As a matter of style, I'd say that a positive induction is generally preferable over a proof by contradiction when possible. Induction also comes with the added benefit of proving that f = 1 actually is a solution, whereas using contradiction proves only that f = 1 is the only possible solution, but still might not be a solution.

[JM-usfr]

I found that same first solution you presented. For your second solution strat, I think there's a couple problems.

First, I don't think we can choose a and b in such a way that they are guaranteed to be smaller than n (in order to invoke strong induction). Secondly, even if you could, it would only prove it for sufficiently large n. This is because to guarantee multiple representations of n^2+m^2 as a sum of two squares, it needs to be composite (see Euler's Factorization Method). This depends on when the totient function of n exceeds the prime counting function of n, in order to guarantee such an m exists (by pigeonhole). Specifically, we want T(n)>pi(n)-w(n), where T is the totient function, and w is the number of distinct prime factors of n.

Seeing that T(n)>pi(n)-w(n) even for something like n=24, it might not be impossible to prove it this way, but it's still not really necessary.

[Risuchan]

Excluding 0 from ℕ is very confusing. I ended up resolving a completely different problem :o Using ℕ* or ℕ\{0} notation would be proper.

[joaopedrogoncalvesramos]

The same holds if we replace the codomain by R instead of N.

Indeed, let’s prove by induction that, for each n in N, there is an integer exponent a(n) such that

f(n)=f(1)^(a(n))

The proof of this fact for n <= 5 is as in the video. For n larger, we use induction: since f(a-2)f(2a+1) = f(a+2)f(2a-1) whenever a >= 3 and f(a-4)f(2a+2) = f(a+4)f(2a-2) whenever a >= 5, the claim follows for n = 2a+1 by using the first identity, and for n = 2a+2 using the second.

Now, since f(1) = 1, the result follows, i.e., f is constant

[deebd]

For the record: if N (the natural numbers) includes 0 - and that's how I was educated long time ago, but maybe it's also a regional question, I'm german - the problem is really trivial, you can directly conclude that f(x) = 1 is the only solution by setting y to 0 and checking the consequences. But what I wonder: are there maybe any smart theorems concerning such "domain switches" that could be used? In the sense of "if a functional equation applied to the non-negative integers has only one specific solution, those are the requirements that the same equation applied to the positive integers can have other solutions"?

[johannmeier]

First condition, setting x=y, then f(2x²) = f²(x). Replacing RHS with Second condition leaves us f(2x²) = f(x²) which is only solved by "f(x) = const" (any const) as the only solution for first condtion. The second condtion limits this to const=1 and const=0 (if you consider 0 in N), because f=f².

[Noam_.Menashe]

If we count 0 as a natural number we get two possible answers in a matter if seconds.

[cmilkau]

16:15 check is a one-liner: n = 2m + 1 = m + (m + 1), where both summands are at least 1.

[georgeharrison]

There's one word I like to say about this presentation: "NIFTY!!!"

[rhythmshah]

Let y=0 in 1st equation:
we get f(x^2)=f(x)*f(0), and by second equation, we get f(x^2)=(f(x))^2
So, f(x)*f(x)=f(x)*f(0), so either f(x)=0 or f(x)=f(0)=1, and for natural numbers, the only solution would be f(x)=1, isnt this a very small correct solution?

[Dazai]

I solved this problem a bit differently. First, I let x be free and y=0. Thus, f(x^2)=f(x)f(0). Then, I applied the second function, making (f(x))^2=f(x)f(0). I checked if f(0) was a solution, which it was, so, with the addition of f(x)=0 to the solution set, I could divide both sides by f(x). Third, I divided both sides by f(x), giving f(x)=f(0). As the function is from the natural numbers to the natural numbers, f(0) is a natural number, so f(x)=n, where n is a natural number. Plugging this into the second equation, the only solution is f(x)=1. With the addition of f(x)=0, the only 2 solutions are f(x)=1, f(x)=0

[emilyliedtke]

Reminds me of what I heard is supposedly the hardest problem they ever did on the german Bundeswettbewerb Mathematik: Given a recursive function f(0)=0, f(n)=n-f(f(n-1)), find an explicit formula for f(n)

[רועיתורגמן-זמ]

Great video as always! I thought about another approach:

=> f(x) = 0 or f(x) = f(0).
f(x) = 0 is a solution, now consider f(x) = f(0).
but f(0) = f(0)^2 => f(0) = 0 or f(0) = 1.
but f(x) is not identically 0 so f(x) = 1.

To sum up, f(x) is either identically 0 or 1.

[mokouf]

Depends on the context, natural number may or may not include 0.
If we replace the f: N→N with f: R→R, can we still solve it?

[doraemon]

0 is a natural number. Anyone who says otherwise is mad

[CoolCatDoingAKickflip]

16:50 The head of that arrow looks like a perfectly written capitalized V.