I noted that the equation was f(n)=n+1 mod 2 and then wrote f(n)=2g(n)+n+1 for some (integer) function g(n). Plugging this into the equation we get 3g(n)+2g(2g(n)+1)=0. With this we can show that g(n) must be divisible by two. But then g(n) must be divisble by 4 as 2g(2g(n)+1) is now divisible by four. This goes on, thus g(n) is divisible by all powers of 2 for all n. The only function that satisfies this is the zero function. Hence g(n)=0 and f(n)=n+1.
@cantcommute
Жыл бұрын
This has the bonus of showing it to be a unique solution too! Though g(n) has an extended domain and im unsure if that ruins anything.
@cantcommute
Жыл бұрын
(reading another comment made me realize that you could rearrange the equation 3g(n)+2g(2g(n)+1)=0 and show that it contradicts g(n) being a function of the integers unless g(n) is the zero function)
@sk8erJG95
2 жыл бұрын
I found a quicker way which also doesn't assume the form of f(n). Claim 1) f(n) > n for all n. Proof 1) If f(n)
@sk8erJG95
2 жыл бұрын
Details: Prop 1) f is injective, since if f(n) = f(m), the lefthand side of the func. equation will be equal but the righthand side would be 3n + 5 and 3m + 5, meaning they must be equal, so n = m. Let f^m(n) = f(f(f(...f(n))) m times. Prop 2) If f(k) = k+3 for all even m and f^m(k) = (1/2)(3k+5 - (k-1)) = k + 3. Thats m = 1 and m = 2 for the base cases. Then we assume it holds for all m < M. If M is odd, then f^M(k) = (1/2)(3f^(M-2)(k) + 5 - f^(M-1)(k)), and by the inductibe hypothesis we know f^(M-2)(k) = k+ 3, so f^M(k) = k + 8 >= k + 3. That ends the induction. So then the flushed out proof of my Claim 1 is) If f(k) < k, then f^M(k) < k for all odd M by Prop 2, which is impossible because f is injective by Prop 1 and {1,2,...,k-1} is finite. Similarly my Claim 2 would be proven by the same Prop 1 and a Prop 3. Prop 3) If f(k) >= k + 2, then f^m(k) >= k + 5 for odd m > 1 and f^m(k) = k + 2, then f^2(k) = (1/2)(3k + 5 - f(k)) = (1/2)(3(k+2) + 5 - (k+1)) = k + 5. For M even, we have f^M(k)
@sil1235
Жыл бұрын
Let a0=n,a(k+1)=f(a(k)), then a(k+1)+2a(k+2)=3a(k)+5. Small substition b(k)=a(k)-k turns the recurrence into linear b(k+1)+2b(k+2)=3b(k), which we easily solve as b(k)=A+B*(-3/2)^k. Since b(k) must be an integer for all k, we conclude B=0, hence b(k)=A for some constant A, and a(k)=A+k. But a(0)=n=A and so a(k)=n+k. Then necessarily a(1)=f(n)=n+1 (since we did this process for arbitrary starting value of n).
@pNsB
2 жыл бұрын
I substituted f(n) = an + b, got a quadratic equation in terms of a which gave me 1 as the only integer answer, substituted *that* into the other equation I got from equating like terms and for 1 for b.
@emurphy42
2 жыл бұрын
I did the same, but that doesn’t prove that it’s the *only* function meeting all the conditions. The method shown in the video does prove that.
@cantcommute
Жыл бұрын
there could be a function that satisfies the equation that isn't linear. What you did was show that if f(n) is linear then only answer is n+1
@thanhchan3365
Жыл бұрын
Your videos are really good and helpfull. Could I repost your channel on the platform of Ganjing World? - That is the great platform too. I will keep everything as is and include your channel link as the source. Thanks, dear!
@yepyeniceri
2 жыл бұрын
Why we didn't just use f(n) = an + b and solve the equation?
@angelmendez-rivera351
2 жыл бұрын
Because f may not be a polynomial. It may be some other strange function.
@sonlaihop3754
2 жыл бұрын
@@angelmendez-rivera351 But if the right-hand side is a 1st order polynomial, the left-hand side must be the same: f(n) = an + b => f(f(n)) = a(an+b) + b = (a^2)n + ab + b f(n) = a*exp(n) => f(f(n)) = a*exp(a*exp(n)) And so on
@sonlaihop3754
2 жыл бұрын
That's why we can use f(n) = an + b and solve the equation, faster than just substitute n
@angelmendez-rivera351
2 жыл бұрын
@@sonlaihop3754 That is not true.
@Deathranger999
2 жыл бұрын
@@sonlaihop3754 This is not true. For example, what if I define f(n) = n - 1 for even n, and f(n) = n + 1 for odd n? Then f(f(n)) = n, but f is certainly not polynomial.
@realcolby
Жыл бұрын
I’ve seen a lot of people sharing their solutions so here’s mine that’s a little long: Firstly suppose ∃m∈ℕ:f(m)=m+1 ⇒m+1+2f(m+1)=3m+5 ⇒2f(m+1)=2m+4 ⇒f(m+1)=m+2 By induction this shows that: f(m)=m+1 ⇒ f(m+k)=m+k+1 ∀k∈ℕ Now looking at the original equation mod 2 you find: f(n)+2f(f(n))≡3n+5(mod 2) simplifying yields: f(n)≡n+1(mod 2) Substituting n for f(n) also shows: f(f(n))≡n(mod 2) By the original equation: f(f(n))=(3n+5-f(n)/2 ⇒(3n+5-f(n))/2≡n(mod 2) ⇒(3n+1-f(n))/2≡n(mod 2) ⇒3n+1-f(n)≡2n(mod 4) ⇒f(n)≡n+1(mod 4) I was including 0 in the natural numbers so I solved for 0. f(0)+2f(f(0))=5 ⇒f(0)≤5 Since f(0)≡1(mod 4): Either f(0)=1 or f(0)=5 f(0)=5 yields a contradiction: 5+2f(5)=5 ⇒f(5)=0 But f(5)=0≢6(mod 4) Therefore f(0)=1. To verify this fact: 1+2f(1)=5 ⇒f(1)=2≡2(mod 4) Since f(0)=1 satisfies the equation f(m)=m+1, it is clear from earlier that f(0+n)=0+n+1 And finally: f(n)=n+1 ∀n∈ℕ
@Byeollanii
Жыл бұрын
When will you make a new video I've watched all of them!!!!
@rocky171986
2 жыл бұрын
How did you deduce the function must be linear?
@jakobr_
2 жыл бұрын
f(n) = n+1 was an educated guess based on the values of the function at 1,2,3.
@VSN1001
2 жыл бұрын
RHS -> f(n) is a polynomial deg[3n+5]=1 Assume that deg[f(n)]>1 Then, deg[f(n)+2f(f(n))] >1 Contradiction. Hence f(n) is linear
@ManuelRuiz-xi7bt
2 жыл бұрын
@@VSN1001 First step is incorrect.
@joeheeley31
2 жыл бұрын
@@VSN1001 the justification that f is a polynomial is faulty
@anngo2323
2 жыл бұрын
The proof never states that f linear
@icfj77
Жыл бұрын
it works also for f: N U{0} -->N U {0}.
@JojiThomas7431
2 жыл бұрын
This problem is so simple but i could not solve it. Good video. This requires more KZitem views
@martinnolin2315
Жыл бұрын
2:30 use the € symbol instead of =
@realcolby
Жыл бұрын
Here’s the actual Unicode character: ∈
@Arcadax
2 жыл бұрын
How do you explain the uniqueness? I don’t think it’s trivial.
@user-vg1qo5gi3l
2 жыл бұрын
I don't get your question. Problem is fully solved
@ManuelRuiz-xi7bt
2 жыл бұрын
It follows from the induction.
@dashinblu
2 жыл бұрын
f(1)=2, f(2)=3 ... is implified by the function definition. So it implies f(n)=n+1. If there exists another function f2, then the function must fulfill f2(1) = 1, f2(2) = 2 ... So it's a unique solution.
@ManuelRuiz-xi7bt
2 жыл бұрын
@@dashinblu "So it implies f(n)=n+1". Only via the inductive argument. It is not immediately obvious that you can cover all the positive integers like that.
@bait6652
2 жыл бұрын
From the trivial I.C, run iter from n: 1 to 100 (4 iters should suffice , author did 3). Then name another function that matches the pattern f(n)=n+1. IF u can then the author solution is not unique
@angelmendez-rivera351
2 жыл бұрын
Let id be such that id(n) = n, so f + 2·f°f = 3·id + 5. Let f^m be such that f^(m + 1) = f^m°f. Hence f^(m + 1) + 2·f^(m + 2) = 3·f^m + 5, which is equivalent to 2·f^(m + 2) - 2·f^(m + 1) = 3·f^m - 3·f^(m + 1) + 5 = 5 - 3·[f^(m + 1) - f^m], so 2·[f^(m + 2) - f^(m + 1)] + 3·[f^(m + 1) - f^m] = 5 = 2 + 3, hence 2·[f^ (m + 2) - f^(m + 1) - 1] + 3·[f^(m + 1) - f^m - 1] = 0, which implies f^(m + 1) - f^m - 1 = 0 for all m. This means f^(m + 1) - f^m = 1. Summing from m = 0 to m = p - 1 results in f^p - f^0 = p, and since f^0 = id, it means f^p = id + p. Therefore, f = id + 1. Therefore, f(n) = n + 1 for all n.
@josebeleno1213
2 жыл бұрын
Great proof!!! But how do you prove that 2•[f^(m+2) - f^(m+1)-1]+3•[f^(m+1) - f^(m)-1]=0 implies that f^(m+1) - f^(m)-1 = 0? . Obviously that satisfies the first equation, but can't see why it would ve the only "solution".
@boristerbeek319
2 жыл бұрын
@@josebeleno1213 the domain of f is the set of natural numbers. if the insides of those parentheses were nonzero, the equation would in fact have rational solutions instead of strictly natural ones
@Deathranger999
2 жыл бұрын
Looks like you deleted your other comment. Care to address what I had mentioned under it?
@Deathranger999
2 жыл бұрын
@@boristerbeek319 Also I agree with Jose's comment - it doesn't seem like this is necessarily true. What's stopping us from having f^(m + 2) - f^(m + 1) - 1 = 3 and f^(m + 1) - f^m - 1 = -2? I see an argument that you could probably make for that, but it's definitely not obvious. I think the induction proof from the video is far nicer.
@angelmendez-rivera351
2 жыл бұрын
@@josebeleno1213 You are right. That part of my demonstration was sloppy. Here is what is missing. Let g : {Z >= 0} -> {Z > 0}^{Z > 0} be defined such that g(m) = f^(m + 1) - f^m - 1, so that g(0) = f - id - 1. Hence 2·g(m + 1) + 3·g(m) = 0, meaning that g(m + 1) = -3/2·g(m). This means g(m + ν) = (-3/2)^ν·g(m), which implies g(ν) = (-3/2)^ν·(f - id - 1), which means f - id - 1 = μ(ν)·2^ν, since the output g(ν) must be some function {Z > 0} -> {Z > 0}, since this is what the solution is supposed to be. f = id + 1 + μ(ν)·2^ν, as such, and so f°f = id°(id + 1 + μ(ν)·2^ν) + (1 + μ(ν)·2^ν)°(id + 1 + μ(ν)·2^ν) = id + 1 + μ(ν)·2^ν + 1 + μ(ν)·2^ν = id + 2 + μ(ν)·2^(ν + 1), so 2·(f°f) = 2·id + 4 + μ(ν)·2^(ν + 2), and so f + 2·(f°f) = 3·id + 5 + μ(ν)·[2^(ν + 2) + 2^ν] = 3·id + 5, and so μ(ν) = 0. Therefore, g(ν) = 0 and f = id + 1.
@samwalko
2 жыл бұрын
Proving that f(n) = n+1 is a solution is pretty easy, as shown here, but proving it the only solution is somewhat less so. Notably, all steps used in the inductive step work in either direction, but I'm not actually sure that proves uniqueness in general. Base case: f(1) = 1+1 is the only solution as shown in video. I.H.: Assume f(n) = n+1 for some integer k. Then f(k)+2f(f(k)) = 3k+5 => k+1+2f(k+1) = 3k+5 => 2f(k+1) = 2k+4 => f(k+1) = (k+1)+1 is the only possible solution for f(k+1). Therefore, f(n) = n+1 is the only possible solution.
@Deathranger999
2 жыл бұрын
That’s basically the exact same inductive proof he did in the video, you just said some additional words. I agree it could’ve been a little clearer but it’s definitely sound.
@oleksandryatsenko1
2 жыл бұрын
why f(1) must be integer?
@dashinblu
2 жыл бұрын
Qns says F is function from natural number to natural number
@alxjones
2 жыл бұрын
f: N -> N means that only elements of N can be put into f and only elements of N will come out of it. Here, N is considered to be the positive integers {1, 2, 3, 4, ... }, so that is where all the inputs and outputs of functions must live. Clearly, 1 is in this set, so we are able to plug it into f, and by definition, whatever comes out of it must also be in this set; the thing which comes out of f when 1 is put in is called f(1).
@manamimnm
2 жыл бұрын
Shouldn’t the natural number set include zero as well?
@angelmendez-rivera351
2 жыл бұрын
My observation is that maths KZitemrs refuse to accept to accept that 0 is a natural number, despite the fact that, mathematically speaking, this exclusion makes absolutely no sense whatsoever. Ultimately, though, when it comes to these videos, it just becomes an issue of semantics and notation. So here is my advice: whenever you hear someone on KZitem talk about the natural numbers, just replace the phrase "natural numbers" with "positive integers" instead, and it will save you the trouble of having to argue with people about the topic. People have a phobia of the number 0, and that will never go away, most likely. As for myself, whenever I talk about the natural numbers, I will always, without exception, be talking about the Von Neumann natural numbers, which include 0 as the smallest element and as additive identity.
@cardieel
2 жыл бұрын
@@angelmendez-rivera351 cry about it
@angelmendez-rivera351
2 жыл бұрын
@@cardieel Your comment proves my point. Thank you.
@mmmmmark9751
2 жыл бұрын
No. Zero is not positive, so is not a natural number.
@miguelsorribesherrero871
2 жыл бұрын
Pretty sure Natural numbers are thought as the numbers you use to count sets.
@srikanthtupurani6316
2 жыл бұрын
we can also solve this in a different way. for fixed n let u(r)=fofo.....r times(n). now we get a recurrence equation. it is a very bad solution.
@VerSalieri
2 жыл бұрын
You can't just say this is the only solution... I can find many other solutions verifying f(1)=2, f(2)=3, and f(3)=4. For example: f(n) = n^3 - 6n^2 + 12n - 5. Uniqueness is far from trivial. In fact, it could be that the family of solutions to be found is easy but the difficulty lies in proving there are no others. Forgot to mention that I love your content, keep up the good work my friend.
@angelmendez-rivera351
2 жыл бұрын
Exactly. In fact, I would not be surprised if this equation had nonconstructible solutions.
@Deathranger999
2 жыл бұрын
But what he's proved is that because f(3) = 4, we also have that f(4) = 5, which implies that f(5) = 6, which implies that... etc. etc. That's the whole point of the induction at the end. Your function does not satisfy that.
@tianqilong8366
2 жыл бұрын
wow, true man
@tianqilong8366
2 жыл бұрын
@@Deathranger999 he is not saying the author is doing something wrong, it might just be that there are other solutions than f(n) = n + 1, for example a cubic thing
@Deathranger999
2 жыл бұрын
@@tianqilong8366 My point is that the video proved by induction that there are no other functions that satisfy the given functional equation.
@ibrahimmassy2753
2 жыл бұрын
You showed by induction that f(n)=n+1 is valid solution but not proved uniqueness
@ibrahimmassy2753
2 жыл бұрын
Idea: let f(m,n) be f(n) composed m times. So you have f(m,n)+2*f(m+1,n)=3*f(m-1,n)+5 Arranging the equation you have 2*(f(m+1,n)-f(m,n)-1)+3*(f(m,n)-f(m-1,n)-1)=0 As f goes from N to N the terms in parenthesis must be zero, otherwise you have rational numbers in f(m+1,n)-f(m,n)-1 So f(m+1,n)-f(m,n)=1 f(m,n)=m+q(n) but f(0,n)=n by definition thus f(m,n)=m+n As f(n)=f(1,n) you have f(n)=n+1
@angelmendez-rivera351
2 жыл бұрын
@@ibrahimmassy2753 Excellent! Now THIS is actually a proof of uniqueness. And to be honest, that was beautiful. I did not even see how easy it was to solve the equation using functional composition until your comment. You should post this in the main comments section, and get your comment pinned.
@Deathranger999
2 жыл бұрын
He did actually prove uniqueness - the inductive step isn't assuming that f(n) = n + 1 for all n (that would be fallacious), but rather, it assumes that f(n) = n + 1 for some particular choice of n, and then proves that f(n + 1) = (n + 1) + 1 - then by induction (with the base case already proved), f(k) = k + 1 for all k.
@ibrahimmassy2753
2 жыл бұрын
Answering to Max Lindemann (I can't reply to him directly) if we get the equation 2*(f(m+1,n)-f(m,n)-1)+3*(f(m,n)-f(m-1,n)-1)=0 that's imply f(m+1,n)-f(m,n)-1=3/2*(f(m,n)-f(m-1,n)-1) so the expression f(m,n)-f(m-1,n)-1 is 3/2 the previous one, so f(m,n)-f(m-1,n)-1=K*(3/2)^m. If m is large enought and K is nonzero integer f(m,n)-f(m-1,n)-1 becomes neccesarily a fraction. Thus K must be 0 therefore f(m,n)-f(m-1,n)-1=0
@ibrahimmassy2753
2 жыл бұрын
Excuse me f(m,n)-f(m-1,n)-1 is -3/2 the previous one
@francescosmerilli5384
4 ай бұрын
Ok, for you, zero is not natural number. Ok, is only a convection, and because in all other parts of this planet, 0 is a natural number, maybe you can use N+ simbol, to avoid useless misunderstood. Thanks.
@giuseppemalaguti435
2 жыл бұрын
n+1
@TechToppers
2 жыл бұрын
Please, please. Don't use N and stuff like that. It leads to conflict lmao. Just explicitly state the sets or use Z+ or something like that.
@motherisape
2 жыл бұрын
why
@ngc-fo5te
2 жыл бұрын
What for? There is no conflict here.
@AlexandreRibeiroXRV7
2 жыл бұрын
@@ngc-fo5te I believe he means some people include 0 as part of the natural numbers, while others don't (this is based on my experience, seeing that some countries teach it one way and other countries the other). The set of positive integers removes this ambiguity, though I particularly don't care either way lol
@motherisape
2 жыл бұрын
@@AlexandreRibeiroXRV7 that is true but in most book f:ℕ -> ℕ means ℕ={1,2 ,3,4,5,6......}
@bait6652
2 жыл бұрын
N is for counting...1, 2 , +1. W=NU{0} is term from fractions -1 is accounting
Пікірлер: 242