a nice non-linear recursion problem

  Рет қаралды 20,787

Michael Penn

Michael Penn

Күн бұрын

Пікірлер: 81
@DrJaneLuciferian
@DrJaneLuciferian 2 жыл бұрын
I know it doesn't matter for the point of the problem, but shouldn't it have been 505 and not 550?
@adandap
@adandap 2 жыл бұрын
Yes!
@jesusthroughmary
@jesusthroughmary 2 жыл бұрын
Indeed, 2020/4
@jursamaj
@jursamaj 2 жыл бұрын
Yes, but the important part is that 2020 is a whole multiple of 4. Since you end up throwing away the 505 anyway, it's exact value doesn't matter.
@idancohen4753
@idancohen4753 2 жыл бұрын
Lol
@winteringgoose
@winteringgoose 2 жыл бұрын
550 = 505 for high values of 505~
@rublade1
@rublade1 2 жыл бұрын
6:59 NOT 550 but 505
@Khaim.m
@Khaim.m 2 жыл бұрын
0:00 Thumbnail is wrong. Sum starts at n=1 not n=0.
@karma_kun9833
@karma_kun9833 2 жыл бұрын
6:00 "attack" :)
@goodplacetostop2973
@goodplacetostop2973 2 жыл бұрын
14:06 Homework 14:43 Good Place To Stop
@kevinmartin7760
@kevinmartin7760 2 жыл бұрын
I don't feel that the "continuous system" is the same; it is the equivalent to (x_(n+1)-x_n)=(x_n-1)/(x_n+1) since y' corresponds to the difference between consecutive terms. I think the corresponding continuous system would be y'=(y-1)/(y+1)-y=-(y^2+1)/(y+1). An alternative would be for y to be a solution to the functional equation f(x+1)=(f(x)-1)/(f(x)+1)
@qschroed
@qschroed 4 ай бұрын
You can try it with the taylor expansion around 0 (assuming everything is nice) and collect terms, it gives us 4 integrals that can probably be evaluated each
@Roberto-REME
@Roberto-REME 2 жыл бұрын
I am very impressed with your brilliance and I really enjoy your videos, Michael. You narrate very well your thought process and your delivery is clear and well timed plus, I might add, you come across as having a very pleasant disposition.
@s4623
@s4623 2 жыл бұрын
14:06 that looks like a separable DE and once you have the family of solutions you can get the antiderivative and substitute.
@zuzaaa1998
@zuzaaa1998 2 жыл бұрын
After solving this ODE you get an implicit function in terms of y and determining the constant of integration is tricky, there should be different solution to this problem
@IanXMiller
@IanXMiller 2 жыл бұрын
Lambert W function needed to write y explicitly which is integrable but after that to find the constant of integration get very messy.
@TinySpongey
@TinySpongey 2 жыл бұрын
By analogy with the presented solution I tried looking at y'' and that didn't obviously help.
@sergeipetrov5572
@sergeipetrov5572 2 жыл бұрын
Thank you, Michael! I saw a new type of problems in your video. It's pretty interesting.
@demenion3521
@demenion3521 2 жыл бұрын
The second quadratic equation you get can even more easily be solved than with the quadratic formula by noticing that replacing x0 with -x0 gives the other equation.
@laokratis55
@laokratis55 2 жыл бұрын
Since I spent quite some time on the supplementary problem, here is my effort for the differential equation. (a) the equation is separable and the general solution is y+2Ln(y-1)=x+C b)Defining a=y(1) and b=y(2020) (which will appear in the limits of the condition) we can eliminate the constant C and get the first equation for a,b which is a-b+2Ln((a-1)/(b-1)=2019. c) Next we work with the integral condition. We change from the x to the y variable. Using the differential equation we solve for dx and we get dx=(y+1)*dy/(y-1). Substituting we get the integral y*(y+1)*dy/(y-1) with limits from a to b for the y variable. Since this integral is 0 we get a second equation for a and b which after some manipulations is (b-a)(4+a+b)=4Ln((b-1)/(a-1). d) Defining a temporary parameter K=2Ln((b-1)/(a-1) we get a simpler system b-a+K=2019,(b-a)(4+a+b)=2K which allows to find a and b as rational functions of K. These expressions are substituted in the definition of K and a non linear equation has to be solved numerically for K. I wish someone else has a simpler approach to this or even to prove me wrong in the above. The requirement for a solution to exist is (a>1 ,b>1) or (a
@OdedSpectralDrori
@OdedSpectralDrori 2 жыл бұрын
I've spent ages on this as well and eventually achieved y is a lambert W function of exp(x/2 + C), with some additional coefficients (substitute u = 0.5(y-1) and you will get there). This basically equivalent to your solution. There's a formula for the indefinite integral of W(exp(z)) which you can plug in and get the value. my sanity shattered when I got here and that's where I stopped!
@Theoutcome0
@Theoutcome0 2 жыл бұрын
@@OdedSpectralDrori without Michael telling where a good place to stop is, we will keep going until we shatter our sanity
@jursamaj
@jursamaj 2 жыл бұрын
Putting the basic recursion in a spreadsheet, it was immediately clear that there was a cycle of 4 values. Summing 4 values & trying a few numbers for x0, I quickly narrowed in to near 2.4. On a guess, I went to 1+√2, and all the other values fell out.
@wynautvideos4263
@wynautvideos4263 Жыл бұрын
Engineer solution 😂😂😂
@daniellosh1015
@daniellosh1015 2 жыл бұрын
Coming back to continuous version and worked out a numerical solution, but I'm not sure whether it is correct or not. By direct integration of the differential equation y' = (y-1)/(y+1), we get y + 2ln|y-1| = x+C (eqn 1). Rearrange, we also have (y+1)y' = y-1 or y = (y^2/2 + y + x)', integrating over (1, 2020), we have [y^2/2 + y + x] = 0 or [(y+1)^2 + 2x -1] = 0 for x = 2020 and 1. [(y(1)+1)^2 + 2(1) -1] = [(y(2020)+1)^2 + 2(2020) -1], using eqn 1, C can be solved out numerically as C = -998.7 (approximately). Back substitute into eqn 1, y(0) = -1012.5 (approx.) When we plot x = g(y) = y + 2ln|y-1| + 999 (y as a variable), it is asymptotic at large absolute y values (x = y + 999, a straight line at the two ends) with a singularity (cusp) at y = 1. BTW, y(1) = -1009.5 and y(2020) = 1007.5 (approx.)
@Pengochan
@Pengochan 2 жыл бұрын
I wonder if the "continuous" version even has a solution. y(x) has a perpendicular tangent (y' becomes infinite) w in hen y=-1, y'>=0 when y>=1, so for y(x) to cross the x-axis 0
@claudio9991
@claudio9991 2 жыл бұрын
But you don't know for what's values of x, y is bigger or equals 1. I think
@Pengochan
@Pengochan 2 жыл бұрын
@@claudio9991 If y(x) is ever larger than 1, then it will stay so, since then y'>0. Also it can't get there from y(x)0 but also end at some (?,-1) before crossin the x-axis. So there are four classes of solutions, where for all x: y(x)>1, y(x)==1, -1
@OdedSpectralDrori
@OdedSpectralDrori 2 жыл бұрын
copying a reply to another comment here : I've spent ages on this as well and eventually achieved y is a lambert W function of exp(x/2 + C), with some additional coefficients (substitute u = 0.5(y-1) and you will get there). This basically equivalent to your solution. There's a formula for the indefinite integral of W(exp(z)) which you can plug in and get the value. my sanity shattered when I got here and that's where I stopped!
@Pengochan
@Pengochan 2 жыл бұрын
@@OdedSpectralDrori Well one can integrate my solution for x(y), then calculate the area between x(y) and 2020 for y
@cicik57
@cicik57 2 жыл бұрын
great i solved in the same way. Calculate x[n+2]=-1/xn you will see that the sequence is a loop of size 4
@pablocopello3592
@pablocopello3592 2 жыл бұрын
If the nr. Of terms is mult. Of 4, when x0 is solution, x1, x2 and x3 also are. If you invert x0 or change sign of x0, the sum changes sign, so, if x0 is solution also are 1/x0 and - x0 (and - 1/x0, that is x2). So solving x1=-x0, you have 2 solutions, and with x1=1/x0 have the other 2. Given the recursive func. Is ratio al with num. and den. 1st. Degree, and Given periodicity of. 4, we cannot have more than 4th Degree (in num. when sum x0 to x3 in funct of x0) , so no more than 4 solutions. So the previous are all sulutions.
@daniellosh1015
@daniellosh1015 2 жыл бұрын
y+2ln(y-1)=x+c or e^y(y-1)^2=Ae^x, subject to B.C. int(1,2020)[y]=0.
@srikanthtupurani6316
@srikanthtupurani6316 2 жыл бұрын
X0=tan(x) X1=tan(x-pi/4).. We can do this It is a periodic sequence.
@leonhardfrommhold8463
@leonhardfrommhold8463 2 жыл бұрын
Its pretty easy to just guess one solution, you can do xn+1=-xn --> -x=(x-1)/(x+1) and solve that directly and get -1+-root(2) very easily. Ofc there could be more but getting one is pretty easy
@mathsisthebest616
@mathsisthebest616 2 жыл бұрын
Set 1/x_n = tan(a_n). I believe we get a_{n+1} = a_n + pi/4.
@replicaacliper
@replicaacliper 2 жыл бұрын
wow that's a really clever observation jesus
@user-en5vj6vr2u
@user-en5vj6vr2u 2 жыл бұрын
Damn nice idea. You could even go and set x(n)=tan(b(n)) then use the angle addition formula to rewrite the original equation as tan(b(n+1))=(tan(bn)-tan(pi/4))/(1+tan(bn)tan(pi/4))=tan(bn-pi/4) thus b(n+1)=b(n)-pi/4
@dirk_math6794
@dirk_math6794 2 жыл бұрын
In fact you should mention that x_0 cannot be -1, 0 or 1 as in those cases the reduction mod 4 of the indices doesn't hold
@jursamaj
@jursamaj 2 жыл бұрын
In those cases, the cycle of 4 values runs 1, 0, -1, [division by 0].
@edwardlulofs444
@edwardlulofs444 2 жыл бұрын
Fun, thanks.
@louisreinitz5642
@louisreinitz5642 Жыл бұрын
I vaguely remember this is cyclic except for some initial values
@johnloony68
@johnloony68 2 жыл бұрын
6:59 where do you get the 550 from?
@prbprb2
@prbprb2 2 жыл бұрын
There is a group type structure where the four solutions are related by the transformation, and the transformation cycles through the roots. That is, no matter what solution one picks for x0, the unordered set {x0,x1,x2,x3} is the same. This is a particular version of the Mobius transformations. Maybe MP can comment. Best
@IgnoredJoel
@IgnoredJoel 2 жыл бұрын
Subscribed! Reaching pi*10^5 is a worthy goal
@replicaacliper
@replicaacliper 2 жыл бұрын
another way to finish up the problem and solve the last equation is to make the substitution u=x-1/x, then (x-1)/(x+1)-(x+1)/(x-1)=-4/u
@pablocopello3592
@pablocopello3592 2 жыл бұрын
In the picture of the video the sum is from 0 to 2020 (2021 terms). Almost the same, but the expression of the solutions are not so nice. El
@triplecrossproduct8656
@triplecrossproduct8656 2 жыл бұрын
The problem in the thumbnail is not the problem in the video! Summing from 0 to 2020 gives a much less simple answer than 1 to 2020...
@alainzanchetta
@alainzanchetta 2 жыл бұрын
Once again mixed feelings between the interest of the problem + an overall nice way to solve it on one side and some random complexities + the horror of the mistake when dividing by 4 on the other...
@dudewaldo4
@dudewaldo4 2 жыл бұрын
I tried the thumbnail version where the sum starts at 0 💀
@samosavaglio2141
@samosavaglio2141 2 жыл бұрын
I think i proved that the continous problem has no solution, that, to me, it's pretty strange given that the discrete analogous has solutions
@sharpnova2
@sharpnova2 2 жыл бұрын
the continuous problem isn't the proper analogue to the discrete problem in the video. that's the issue.
@marcorademan8433
@marcorademan8433 2 жыл бұрын
Z tranforms would also solve problems similar to this. Could you perhaps do some problems using the engineer's favourite discrete tool?
@TancrediDeHauteville
@TancrediDeHauteville 2 жыл бұрын
Very nice
@alienmoonstalker
@alienmoonstalker 2 жыл бұрын
If professor Penn were to sing Do-Re-Mi from The Sound of Music, he would start it like this: "Let's stop at the very ending, a very good place to stop..."
@carstenmeyer7786
@carstenmeyer7786 2 жыл бұрын
14:05 Time to do some homework! Let's try to prove no solution exists. For simplicity let *N := 2020* , define *z(x) := 1 - y(x)* and only consider *y, z* on the interval *z: D := [1; N] -> ℝ with initial condition z(1) := c* As long as *z ≠ 0* we move all terms to one side: *1 = -z' * (2 - z) / (-z) = z' * ( 2/z - 1 ) = d/dx ( 2 * ln |z| - z ) =: d/dx f(z)* Integrate both sides from *1* to *x* and get *x - 1 = f(z(x)) - f(c) => x - k = f(z(x)) | k := 1 - f(c)* We found *z(x)* must lie in the pre-image of *{x - k}* under *f* (we can't simply take the inverse as *f* is not bijective). To get an idea what that actually looks like, do the following: 1.) Sketch the graph of *f(z)* 2.) Swap axes, thus flipping the graph 3.) Shift the flipped graph by *k* to the right (results in a left-shift if *k < 0* ) Notice the resulting graph has (at most) three different branches we can choose *z(x)* from: - First branch: *z(x) ≥ 2* - Second branch: *z(x) ∈ (0; 2]* - Third branch: *z(x) < 0* The graph of the continuous function *z* must stay on one of these branches. To check which one actually may lead to a solution, consider the integral condition (transformed to *z* ): *∫_1^N z dx = ∫_1^N (1 - y) dx = N - 1 > 0 ( * )* The first and third branch result in integral values *> 2N - 2* or *< 0* , respectively, so they cannot lead to a solution. If *z* lies on the second branch, the integral *( * )* represents a flipped and shifted sub-area of *∫_0^2 |f(z)| dz = ∫_0^2 -f(z) dz = [ z^2 / 2 - 2z * ( ln |z| - 1) ]_0^2 = 6 - 4 * ln(2)* As a sub-area the value of the integral *( * )* will be smaller than *6 - 4 ln(2) < N - 1* , regardless of the shift *k* we may introduce: Even on the second branch we can never satisfy the integral condition!
@ayoubelouafy6174
@ayoubelouafy6174 2 жыл бұрын
Please , Could u solve the last ex that you've mentioned in the end, i tried to simplify the y' = y(x+h) - y(x) / h i don't know if it's the good way to achieve the solution or not !!!
@nosemeocurrenada93
@nosemeocurrenada93 2 жыл бұрын
What is this problem suggestor that Michael mentions so often?
@jacob4097
@jacob4097 2 жыл бұрын
I just imagine that the secret problem suggester is just Michael with a disguise on.
@bobtannous5464
@bobtannous5464 2 жыл бұрын
very good but it is 505 instead of 550
@와우-m1y
@와우-m1y 2 жыл бұрын
asnwer=1 . 0 isit 🤣🤣🤣🤣🤣
@charliegordon5245
@charliegordon5245 2 жыл бұрын
8:46 Sub-Zero Wins!
@petterituovinem8412
@petterituovinem8412 2 жыл бұрын
could you make a video about Stirling's approximation/formula
@lucachiesura5191
@lucachiesura5191 2 жыл бұрын
great
@pandabearguy1
@pandabearguy1 2 жыл бұрын
What a about a non-nice linear problem?
@lucachiesura5191
@lucachiesura5191 2 жыл бұрын
in fact, if f(x) = 1-2/(x+1) and if we draw the graph of the function and the element of the sequences, after 4 steps we meet the first element; the sum is zero if the first element is +/-1+/-2^0.5. thanks!!
@talberger4305
@talberger4305 2 жыл бұрын
505 not 550 2020/4=505
@ymymymymym
@ymymymymym 2 жыл бұрын
My solution for the homework: y=y’(y+1)+1=y’y+y’+1 A primitive of y is therefore : (1/2).y^2 + y + x So the integral equals : (1/2).y(2020)^2+y(2020)+2020-(1/2).y(0)^2-y(0) If it’s equal to 0 we have y(0)=??? Maybe I missed something.. let me know!
@claudio9991
@claudio9991 2 жыл бұрын
The integral is from 1 to 2020.
@cohomological46
@cohomological46 2 жыл бұрын
Great vid as always :)
@gustavoexel5569
@gustavoexel5569 2 жыл бұрын
Ok, so for homework, I think I almost got it, but the part that I didn't get I was exploring numerically, and it seemed that the answer diverged, but anyway, let's get to it. I'll present my solution, hoping that someone can continue it, or at least give me a hint to how to finish it. I'll also show what I think we were supposed to do. y' = (y-1)/(y+1) Which is a separable differential equation ∫((y+1)/(y-1)) dy = ∫dx u = y-1, du = dy x = ∫((u+2)/u) du x = ∫(1+2/u) du x = u + 2 ln u + C' e^x = C⋅u²⋅e^u e^x/C = u²⋅e^u √(e^x/C)/2 = (u/2)⋅e^(u/2) W(√(e^x/C)/2) = (u/2) y = 1 + 2W(√(e^x/C)/2) And we got y(x) with an integration constant C. Now we can perform ∫y(x) dx = 0, and from now on, all integrals are evaluated from 1 to 2020. 0 = ∫y(x) dx 0 = ∫[1 + 2W(√(e^x/C)/2)] dx 0 = 2019 + 2∫W(√(e^x/C)/2) dx v = W(√(e^x/C)/2) v⋅e^v = √(e^x/C)/2 4C⋅v²⋅e^(2v) = e^x x = ln[4C⋅v²⋅e^(2v)] x = ln(4C)+2ln(v)+2v dx = 2(1/v+1)dv Substituting v and dv in the integral, and changing the integration limits to v(1) to v(2020), meaning W(√(e/C)/2) to W(√(e^2020/C)/2). 0 = 2019 + 4∫v⋅(1/v+1)dv 0 = 2019 + 4v(2020) - 4v(1) + 2v²(2020) - 2v²(1) 0 = 2019 + 4W(√(e^2020/C)/2) - 4W(√(e/C)/2) + 2W²(√(e^2020/C)/2) - 2W²(√(e/C)/2) Now we have an equation with only C as variable, but I couldn't figure out a way to isolate C in this equation. I was going to try to do it numerically, but as you can see, the e^2020 part explodes. Anyway, I tried to substitute the number 2020 in the equation by a lower number like 5, but even then, it seemed that only an infinite C would make the right-hand side of the equation equal to 0. So I probably got something wrong. I was also thinking that we probably were supposed to start the solution similarly to the video, so one thing we could is to differentiate the equation y' = (y-1)/(y+1) y'' = 2y' / (y+1)² And substitute y' into y'', just like he did y'' = 2(y-1)/(y+1)³ Doing the same thing again y''' = 4(2-y)y' / (y+1)⁴ y''' = -8(y-2)(y-1) / (y+1)⁷ But that doesn't seem to get us anywhere...
@carstenmeyer7786
@carstenmeyer7786 2 жыл бұрын
I got the same results until the line *x = u + 2 ln |u| + C' =: f(u) + C'* From what I can tell *-2
@khoozu7802
@khoozu7802 2 жыл бұрын
Just a simple mistake, last solution u should substitute y' not y''
@gustavoexel5569
@gustavoexel5569 2 жыл бұрын
@@carstenmeyer7786 Yeah you're right, it doesn't make sense not to use ln |u|. But yeah, I tried other ways, numerically solving the ODE, and integrating it, making it a function of y0, which only makes sense for y0 >= 1. And sure enough, for y0 = 1, the integral equals 2019, and for every y0 > 1 the integral only grows. I'm not sure about complex entries cause the numerical library I was using doesn't deal too well with complex numbers, but for real numbers I can say that there isn't a solution.
@gustavoexel5569
@gustavoexel5569 2 жыл бұрын
If anyone wants to explore a little bit this numerical solution, the code is really simple, I used Python: import numpy as np import matplotlib.pyplot as plt from scipy.integrate import odeint def dy_dx(y,x): return (y-1)/(y+1) dx = 1e-2 x = np.arange(1,2020,dx) Y0 = np.linspace(1,5,50) I = [] for y0 in Y0: y = odeint(dy_dx, y0, x)[:,0] I.append( np.trapz(y,dx=dx) ) plt.plot(Y0, I) plt.show() It shows how for y0 = 1, the integral is equal to 2019, but as soon as y0 is an infinitesimal bigger (or for computers 1e-16 bigger), the integral starts from 1.8e6 and only grows.
@carstenmeyer7786
@carstenmeyer7786 2 жыл бұрын
@@gustavoexel5569 Nice results using numpy! With the initial condition *y0 = 1* you get *y(x) = 1* as a constant solution, so 2019 makes sense. The jump from integral value 2019 to 1.8e6 seems weird, though: You are switching branches, but essentially you still have *y' ≈ 0* , so I'd expect *y* to be very close to *1* for a long time, close to the constant case above. Maybe *y0 ≈ 1 + 1e-16* already leads to such rapidly exploding solutions, one cannot choose *y0 > 1* small enough numerically to get the integral value in range of 2019? Regarding the other branches *y0 < 1* , I'm pretty sure I found an analytical/geometrical proof no solution can exist there either - it's in the comment section if you're interested. The geometrical arguments are used only to avoid double integration and _Fubini's Theorem_ .
a nice floor problem from the IMO long list.
18:47
Michael Penn
Рет қаралды 14 М.
Non-linear recursions are trickier (with a new technique!)
17:07
Michael Penn
Рет қаралды 18 М.
IL'HAN - Qalqam | Official Music Video
03:17
Ilhan Ihsanov
Рет қаралды 700 М.
One of the most beautiful and powerful tools in mathematics!
13:50
Michael Penn
Рет қаралды 120 М.
A nice suggested differential equation
11:41
Michael Penn
Рет қаралды 52 М.
everyone loves a nice recursive sequence!
15:21
Michael Penn
Рет қаралды 13 М.
On the fifth root of the identity matrix.
14:42
Michael Penn
Рет қаралды 32 М.
Can you solve this "old-style" problem from 1986?
16:25
Michael Penn
Рет қаралды 45 М.
just an average recursion...OR IS IT?
18:24
Michael Penn
Рет қаралды 55 М.
You should know this number theory result -- Bertrand's Postulate
19:34
an interesting approach to the Gaussian integral.
14:30
Michael Penn
Рет қаралды 49 М.
The Simple Math Problem That Revolutionized Physics
32:44
Veritasium
Рет қаралды 8 МЛН
This open problem taught me what topology is
27:26
3Blue1Brown
Рет қаралды 781 М.