idk how he does it, but he always finds the best place to stop

@martineizinger1511

Жыл бұрын

what about b < a? :(

@TamissonReis

Жыл бұрын

​@@martineizinger1511 similar logic...

@wyattstevens8574

11 ай бұрын

"And... I think that's a good place to stop."

Intuitively: Each next term is half way between the previous two, so imagine 2 points in space to represent the first 2 terms, A and B with somebody standing at A. Brackets will indicate the location of the walker. (A) ---------------------------- B Their next destination is B (a_2) A ----------------------------- (B) Then they need to go halfway between A and B, so they walk backwards to the midpoint. A ------------ (C) ----------- B Now they need to go halfway between the midpoint and B, so they go halfway back to B. A ---------------- C ----- (D) ------ B The process repeats, with the person always walking halfway back to the place they just came from, and you can probably guess they end up 2/3 of the way from the start in the limiting case. If you want to prove this, you can set the distance from A to B as x, and the final destination is an infinite geometric series, namely x - 1/2x + 1/4x - 1/8x +..... = x (1 - 1/2 + 1/4 - 1/8 +....) = 2/3 x (using the formula for geometric series) Now I'll watch the video (hopefully 2/3 was right...) Hmm, in terms of a and b, that should be... a + 2/3(b-a) = 1/3(3a+2b-2a) = 1/3(a+2b), which is the video answer. Nice!

@superluminallag5154

Жыл бұрын

Even more intuitively, each iteration A walks twice as much as B, and the remaining distance shrinks as a ratio < 1. Therefore A must meet B after walking twice the distance B walks, so A walks 2d/3 and B walks d/3.

@hansulrichkeller6651

Жыл бұрын

Perfect! I like your solution very much - simple and neat!

@angel-ig

9 ай бұрын

If you identify A with 0 and B with 1 in a 1D coordinate system, your solution corresponds to the fact that 0.101010... = 2/3 in binary: each 1 corresponds to taking the right half and a 0 is taking the left half. For general values of a and b, it suffices to scale and translate the coordinate system appropiately to arrive at the final value of the limit.

@fahrenheit2101

9 ай бұрын

@@superluminallag5154 Ooh i didnt see this until now but yes that's much nicer. Though A and B in my analogy weren't people, I still get the picture

@fahrenheit2101

9 ай бұрын

@urkoma i think your recurrence relation is a little off E.g. if you try a is 0, and b is 1 for m = 3, your recurrence doesnt tend to the value you predict, of 3/4. It actually tends to 0, oddly enough, though I can't think of any simple way of showing that beyond computing the formula from the recurrence. Anyways the recurrence you are probably after is a(n + 2) = a(n + 1) + 1/m * (a(n) - a(n + 1)) I.e term n+2 is the n+1 plus going an mth of the way "back" towards n. That can be rearranged if you like to a(n+2) = ((m - 1)a(n + 1) + a(n))/m I.e. what you had, with an extra m - 1 coefficient for the a(n + 1) term. I'm not too sure how you can get the required sum directly from the recurrence if I'm honest, though the intuition is the same of course, as is the final result that you got.

Converges to (a₁ + 2a₂)/3 very quickly with an error of (4/3)2⁻ⁿ|a₁ - a₂|. You're basically expanding 2/3 in binary.

@momom6197

Жыл бұрын

When I grow up I wanna be able to see that as intuitively as you. 👀

Here's an alternative method by solving directly for a[n] = 1/3 (a + 2b + (-1)^n 2^(1 - n) (a - b) ). This can be found by letting a(n) go as r^n, solving 2r^2-r-1=0 with roots of 1 and -1/2. Letting a(n)=c 1^n + d (-1/2)^n and setting a0 and a1 equal to a and b to solve for c and d. The limit then drops out pretty easily as 1/3 (a + 2 b) since the (-1/2)^n part heads toward zero as n goes to infinity.

@goncalofreitas2094

Жыл бұрын

Exactly how I thought about it, but I guess Michael was trying to arrive there using simpler mathematics, making the argument more elegant perhaps

@GandalfTheWise0002

Жыл бұрын

​@@goncalofreitas2094 Yep. Relatively simple problems like this one can be good practice for using techniques that can apply to a range of more complicated problems. The direct a(n)->r^n approach only works for a limited subset of sequences where a polynomial in r can be directly solved for roots. The method here is more likely to have a chance for solving limits of nonlinear types of recursions.

@SeresHotes25

Жыл бұрын

Yes, but for that you need to know, that you can view a_n as sum of r_k^n, where the amount of r_k^n is equal to order of the equation (and this equation has order of 2).

@koga2960

Жыл бұрын

What's the name of this method? and how did you derive 2r^2-r-1=0?

@Skandalos

Жыл бұрын

Yup, came up with the same solution. The sequence of coefficients reminded me of the fibonacci sequence, just slightly different: Xn = Xn-1 + 2*Xn-2, so I solved the equation x^2 = x + 2 which has the roots -1 and 2, so I created the closed form for the coefficents of a and b just like they describe it on the wikipedia entry for the fibonacci sequence without really understanding what I was doing there :) but it worked so who cares.

Love it! It is the algorithm to approximate the cut of a segment in thirds when all you can do is make halves.

Point of order: the conclusion that the odd-termed sequence is increasing while the even-termed sequence is decreasing is predicated on an assumption that b>a. If, instead, a>b then the odd-termed sequence is decreasing and the even-termed sequence is increasing. Interestingly, the final evaluation of the limit a + 2(b-a)/3 works in either case.

looking in the comments its fun to see the many different ways of solving this problem i'm not as clever or as experienced with recursive sequences so my first instinct was to go for the kill by forming an ordinary generating function, which i used to then get: a(n) = (a+2b)/3+2(a-b)/3*(-1/2)^n (-1/2)^n goes to 0 as n goes to infinity, so the limit is just (a+2b)/3

If a

We can actually give the values of a(n) explicitely: a(n+2) = ( a(n+1)+a(n) ) / 2 gives the equation: x^2 = ( x + 1 ) / 2 with solutions: x = 2 and x = -1. So a(n) = ( (2b+a)2^n - (2b-2a)(-1)^n )/ (3(2)^n) that converges to (2b+a)/3.

@lukasmoudry9973

Жыл бұрын

You have to check that limit exists, without that you cant just solve the equation.

@GuzmanTierno

Жыл бұрын

@@lukasmoudry9973 yes you are right ... but when you have an explicit formula that matches all the conditions you can do that easily

@ilmionomenonloso

Жыл бұрын

How do you get the equation x^2 = ( x + 1 ) / 2 from the recursion a(n+2) = ( a(n+1)+a(n) ) / 2 ?

@GuzmanTierno

Жыл бұрын

@@ilmionomenonloso English: it is a standard technique: a(n+2) corresponds to x^2, a(n+1) corresponds to x^1, a(n) corresponds to x^0 i.e. 1, and the coefficients are kept the same ... (everything can be formalized by seeing the recursion as a differential equation in a discrete space) ... then the numbers that one obtains are used to generate the solutions (same technique as for homogeneous differential equations ...) Italiano: è una tecnica standard: a(n+2) corrisponde a x^2, a(n+1) corrisponde a x^1, a(n) corriponde a x^0 cioè 1, e si tengono i coefficienti che ci sono nella ricorsione ... (si può formalizzare tutto vedendo le ricorsioni come equazioni differenziali in uno spazio discreto) ... poi i numeri che uno ottiene si usano per generare le soluzioni (stessa tecnica delle equazioni differenziali omogenee ...)

@ilmionomenonloso

Жыл бұрын

@@GuzmanTierno Non la conoscevo...grazie!

An easy but important question, thanks Michael👍

As others have stated, there is a general formula for a[n] = (a+2b+(b-a)*(-1/2)^(n-1))/3. The derivation I used for this came from a similar pattern in a problem given to me by a student a year ago. The problem was essentially as follows: Given a graph with 3 nodes, and an edge connecting every node to every other node (in this case just a triangle), choose one node as the "start" and one node as the "end". If you are given "n" moves, how many unique paths are there from the start node to the end node? Note that each move corresponds to traveling from one node to another distinct node. Another fun exercise is that same problem, but with "m" number of fully interconnected nodes. I'd love to see how others and/or Michael would go about solving it!

As per usual, a very complete discussion. Thank you, professor.

Quite clear that answer is a + const*(b - a). And just from first 2 pairs you have a + const*(b - a) = b + const*((a+b)/2 - b) => const = 2/3. And a,b can be negative.

Very pure maths approach. The applied approach is to set up the matrix iteration [x(n+2)] = [1/2 1/2] [x(n+1)] [x(n+1)] [1 0 ] [x(n) ] The eigenvalues are -1/2 and 1. The corresponding eigenvectors are [-1] , [1] [ 2] , [1] The 1-eigenvalue dominates, having the highest absolute value. And so on and so forth.

If you think, you can just do this: 1 - 1/2 + 1/4 - 1/8 + ... = 2/3. So it's 2/3 between a and b. So, (a+2b)/3.

Hello, I just found your channel and it's great! Could you perhaps cover dynamical systems theory/nonlinear dynamics and maybe some probability theory, markovian processes etc?

Very interesting sequence. I have learned s lot👍

This one is pretty quick if you know how to work with discrete calculus, all I had to do is write the recurrence relation as Δ²aₙ + 3/2*Δaₙ = 0, write the set of solutions as aₙ = C₁ * (-1/2)ⁿ + C₂, and from there just plug in a₀ and a₁ to solve for the parameters in terms of a and b. Since the limit of the first term is clearly 0, that just leaves C₂, which can be written as (a+2b)/3.

@ianrobinson8518

Жыл бұрын

Yes, that’s the way I’m familiar with. In the1800s, they called the subject Finite Differences and it was a serious subject in disciplines such actuarial work up until the advent of computers. Problems like this were bread and butter. In fact it’s just a modification of the Fibonacci series which can be generalised.

I see a recursive series like that, my mind immediately goes to the Z transform, that yields the general term for a_n, at which point the limit is trivial.

Nice, specially the calculation of the limit once you had proven its existence.

My way of solving this: It is easy to see and prove, that if starting points A and B give the sequence c1, c2, c3,... with limit C, then for any x the starting points A+x and B+x give the sequence c1+x, c2+x,... converging on C+x. Proving this from the recursive definition is trivial. Similarly, the starting values A*x and B*x give c1*x, c2*x,... converging on C*x. In other words, the location of C relative to A and B is invariant under shifting and scaling. So, we must only find the limit in a simple case, e.g. A=0, B=1. But in that case, the problem is easily solved.

I heard the v-sauce music on this one. Great title even better topic. Can’t wait to see it.

This is a very interesting result. As the sequence progresses, you can see that each term in the sequence is just a weighted average of a and b where b's weight approaches twice a's weight. Intuitively, if we let the varying weight of a be m, as we approach infinity each term gets closer and closer to [ma + 2mb]/3m = [a + 2b]/3. As we progress along, 3m alternates between being 1 more and 1 less than 2^(n-1) and the ratio 3m / 2^(n-1) ----> 1.

I used the ordinary generating function to find the n-th term of the sequence, then took the limit as n goes to infinity. I've been doing a lot of work with generating functions recently, so it's the first approach that came to mind. Very nice problem, and nice recursion.

2:20 Lateralus by Tool starts playing

Intuitive way to understand why the limit is not (a+b)/2: The next term is always between the previous two terms. This means that all the remaining terms will always be between any two consecutive terms. As a_3 = (a+b)/2, the remaining terms will stay either above (if b>a) or below (if a

An easier proof of convergence: Assume a[n-1]

You can show convergence in an easier way that allows for the broader case of a,b in R. a_n comes from the closed interval [a_(n-1), a_(n-2)], and the interval halves in size every time. The limit points will then come from a closed interval of measure 0, i.e. a single point, so the limit exists. Intuitively, you can tell that the limit will be the average of {a,b,b}, because at a_2 you take the average of {a,b}, and at a_3 you throw another b into the mix, so in the end the sequence is influenced by {a,b,b} while everything else is just the process of mixing them together.

The characteristic equation is given by r^2=(r+1)/2 which rearranges to 2r^2=r+1 which implies 2r^2-r-1=0. By inspection, r=1 is a solution, furthermore 2r^2-r-1=(r-1)(2r+1)=0 The two roots are r=1 and r=-1/2. The general solution is given by a_n=A+B*(-0.5)^n. a_0=A+B=a, a_1= A-0.5*B=b, which implies (a-B)-0.5*B=a-1.5*B=b which rearranges to a-b=1.5*B which gives B=(a-b)/1.5=2/3*(a-b), which implies A=a-(a-b)*2/3=(3a-2(a-b))/3=(3a-2a+2b)/3=(a+2b)/3, thus the general solution is given by a_n=(a+2b)/3+2/3*(a-b)*(-0.5)^n, this gives the limit (a+2b)/3

@schweinmachtbree1013

Жыл бұрын

this would be easier to read if you added some spacing, e.g. around the equals signs

I found an answer on math overflow on how to turn a recursive sequence like this one into an explicit sequence. Basically you assume that, ignoring the initial values, the function behaves like x^n and substitute it in for a[n]. You solve for the roots (in this case they’re 1 and -1/2) and then create a linear combination of x^n’s with them: a[n] = p(1)^n + q(-1/2)^n. This gives the equation 2 degrees of freedom, which we can fix using our 2 initial values. It turns out that p = a/3 - 2b/3, and q = 2a/3 - 2k/3, giving us the final explicit equation: a[n] = [(a + 2b) + (2a - 2b)(-1/2)^n]/3 I bet you can use this technique on any recursive formula with the form a[n] = j*a[n-1] + k*a[n-2] + … [edit] oop top comment did the same thing as me 😅

Video and comments display analogy with gravitational lensing for how it qualifies the notion that light takes the shortest path.

Recently I was thinking about that and how the sinc function in the uncertainty principle talks about that.

[2:47] Obviously, a_n = (xa + yb)/(x + y), where y = 2x - (-1)^n ... and x + y = 2^(n - 1) ... Induction will surely confirm this. Then y/x obviously converges to 2, and a_n to (a + 2b)/3

The description NEEDS a music, and this will be the lyrics for it. Of course, a cuban cha-cha-cha.

The analysis can be easily simplified: 1. Consider the special case of a = 0. 2. Prove that it converges and find the limit, the same way done in this video. 3. Notice that for any a, b > 0, the sequence a_n = a+b_n, where b_n is the series with b_1 = 0, b_2 = b-a.

I had a some fun with something like this a little while ago. If you define some dedekind cut C, then let a(0) be in C and a(1) not be in C. We define a(n) by: if a(n-1) is in C then a(n) is the average of a(n-1) and the previous element not in C. If a(n-1) is not in C then a(n) is the average of a(n-1) and the previous element in C. If every a in C is

By way of generating functions, for this sequence we have 2(y-a-bx)/x² = (y-a)/x+y so y = (2a+(2b-a)x)/(2-x-x²). This has radius of convergence R=1, so taking the limit x↑1 of (1-x)y approaches (a+2b)/3 (For a bit of explanation, the generating function of the sequence a(n) is y = sum a(n)xⁿ, so (1-x)y = a(0)+sum ((a(n)-a(n-1))xⁿ. As x↑1, the sum telescopes to a(∞) as we wanted

It's clear that if a, b It actually follows that a_n is in the interval with end points a_k and a_(k+1) for any n > k. This implies that |a_n-a_m| k. As |a_(k+1)-a_k| goes to zero (proved by induction), we see that the original sequence is Cauchy and thus converges.

What's intersting about this recursion is the initial relation gives no information about what the limit is. For example is it were a(n+2) = (a(n+1) + a(n))/3 then if the limit exists it can only be 0.

Yay, the intuitive guess (2/3)b + (1/3)a from shifting my hands around on my desk was right

I did it with the polynomial associated to the serie P(x)=sum(a(n)X^n). using the relation we come to P(x)=(x(a-2b)-2a)/((x-1)(x-2))=A/(x-1)+B/(x-2) assuming x

The next challenge is the same problem for geometrical average :)

@lewsouth1539

Жыл бұрын

... which converges to a^(1/3) * b^(2/3)

I first tried to reason about the sequence when a=0 and b=1. The first few terms look like 0, 1, 0.5, 0.75, 0.625 etc. What are the differences? +1, -0.5, +0.25, -0.125 etc. Nice, that's just a plain geometric series with r=-1/2. I may be misremembering the formula but my intuition says that this converges to 2/3. Well, time to watch the video and find out! (and I also speculate that the formula will be (a+2b)/3 )

Please tell me I wasn't the only one who read the title in Michael Stevens' voice!

it's interesting to show, that sequences a_n+1 = (a_n + b_n) /2 b_n+1 = sqrt(a_n*b_n) with starts values for some x: a_0 =1/sqrt(2-x^2) b_0 =sqrt(1-a_0) are converges both to complete elliptic integral K(x) like this: К(x) = pi/2*1/sqrt(2-x^2)*1/ a_inf It's funny, that this iterative scheme for elliptic integral evaluating is easer than function sin(x) calculations

a and b don't have to be nonnegative. They don't even have to be real, although the monotone sequence theorem doesn't apply in the complex numbers which don't have (>) defined.

Redefine a_n = a + (b - a) • c_n where c_0 = 0, c_1 = 1, and c_(n+2) = (c_n + c_(n+1)) / 2. It's obvious to me that c_n converges to ⅔, which can be proven a few different ways, so a_n converges to (a + 2b) / 3. Okay, so rigorously proving it might take as long as you took in this video, and all I did was take the variables a and b out of the hard part, but that allowed me to recognize a sequence I was already familiar with and saved me a lot of trouble.

I would have thought about this in termsof stochastic processes to show that a limit exist. Same theory, with a well feamed restatement of the problem would yield the limit.

The linear map f that takes a_0 to a_2 and a_1 to a_3 is a contraction map; it has a unique fixed point by Banach's theorem, which is easily calculated to be a_0+(2/3)(a_1-a_0). f is such that f(a_n)=a_{n+2} for any n, hence the subsequence a_0, a_2, a_4, ... converges to the fixed point. The given sequence is also convergent to this same limit because the joint of [a_n, a_{n+1}] for all even n is a singleton set, hence the sequence is convergent and so any subsequence converges to the same limit.

Are we guaranteed that if we have two subsequences, whose indices partition the index of the original sequence, that converge to the same value, we have a convergent sequence overall?

@adamlindstrom5750

Жыл бұрын

A good question and the answer is Yes! This holds since the definition of convergence is that for all epsilon>0 there exists an N such that |a_n -L|N. This is true for each subsequence separately so given epsilon we get two N's, N_1 and N_2. For the sequence as a whole, we pick the largest of N_1 and N_2 as N so we satisfy the condition for convergence. More or less the same argument would also work if we partitioned into any finite number of convergent subsequences.

Thank you for another great video, but I think the easiest way to show this sequence converges may be to show it is Cauchy. Taking the difference a_{n+2} - a_{n+1}, apply the recursion formula to get = { a_{n+1} - a_{n} } /2. So the difference between two terms is half the difference between the previous two. Now take two arbitrarily large terms, and the difference between them is something something triangle inequality which converges to zero.

Just noting that if we write d = (b-a), the difference between the first two values, then L = (a+2b)/3 = (3a + 2d)/3 = a + (2/3)d or two-thirds of the way from the first value to the second one. That seems quite a nice way of looking at the result to me.

Initial thoughts before starting; answer is phi/2 due to its similarity to the def. Of the goldan ratio with the fibonachi sequence.

Similar game? Michael, I want to play the same game! 11:36

CHALK

from 8:05 and onward we only talked about the case when b > a, can we say that without loss of generality the same will hold true for a > b or is that not rigorous enough?

Or you could use induction to show that a_(n+2) is in the interval [a+2b/3 - X/2^(n-1) , a+2b/3 + X/2^(n-1)] where X is constant and that would solve the problem easily

so first, a and b seem like a pain notationally just remove them, let bn=(an-a)/(b-a) so now we have the same recursion on b0=0 b1=1, we can now introduce another sequence cn=2^(n-1)bn which by some algebra solves 2c{n-1}+cn=c_{n+1} which by considering the initial conditions we solve and get cn= 1/3(2^n-(-1)^n) (i now realise i couldve just done it from the getgo but eh this is cleaner) leaving us with bn = 1/3(2-(-1)^n/2^{n-1}) which approaches 2/3 so an=a+(b-a)bn=a+2b/3-2a/3 = 1/3a + 2/3b

There must be a reason to pick a for one of the inputs and also for the series a(n) but I don't know that reason. Not a big deal but certainly not helpful

This process can be extended to a third order or tribonacci sequence where each term >2 is the sum of the three previous terms divided by 3. In this case, the limit will be (a+2b+3c)/6. Another interesting question is to ask how these limits change if we use multiples other than one in defining the recursion on the preceeding terms. In the second order case, these types of sequences are sometimes referred to as Horadam sequences.

an is between a and b, proof a+b/2 and (a+3b)/4 is between a and b The next two points is between those points because recursion and so on at every stage the next two points are between the previous two. Therefore they are always between the first 2.

Lot of clever approaches to solving the problem in the comments! Me, I just wrote a couple lines of python and let it generate the first 100 terms.

I saw someone asking this question on math stackexchange.

Your videos Mike are infinitely recursive! Their limit is e for enlightenment!

At 14:50 the conclusion that the limit exists from the two subsequences having the same limit is a bit suspicious. It is not, in general, true that if two subsequences of the sequence converge to the same limit, then the limit exists. It is true in this case, but only because the subsequences "partition" the original sequence in a way (i.e. every term of the sequence is a term of either the first or the second subsequence) and so every subsequence will be "constructed" by combining the terms of those two subsequences, which all converge to the same value. I think this maybe should have been commented on more.

@shmuels1383

Жыл бұрын

He first proved the subsequences converge, then proved their limits asre equal

@zadsar3406

Жыл бұрын

@@shmuels1383 I understand that. What I'm trying to say is that doesn't imply that the original sequence a(n) converges.

@shmuels1383

Жыл бұрын

@@zadsar3406 you're right. He needed to prove that any other converging subsequence will also approach L

@hach1koko

Жыл бұрын

@@shmuels1383 that's not needed. The only thing needed is perhaps to state the partitioning argument he implicitly used (that zad sar explained above). But imo this is such a standard result when applied to odd and even subsequences that it's a bit unnecessary here

@Leonex52

Жыл бұрын

@@hach1koko Might just use the nested closed interval theorem. The convergence is trivial

The coefficient of b is the sum of the previous coefficient of a and the numerator

I think it is much simpler to prove it is the Cauchy sequence - |a_n+1-a_n| -> 0. The sequence is halving the interval, so it is obvious. So, it is convergent.

@cparks1000000

Жыл бұрын

You need to show more than that to show that a sequence is Cauchy. Consider the sequence defined by a_n = 1 + 1/2 + ... + 1/n. This satisfies a_(n+1)-a_n = 1/(n+1) which goes to zero. It's not true that (a_n) converges though.

@MichaelRothwell1

Жыл бұрын

​​@@cparks1000000 I would say that this is easily fixed. Once you've shown that |aₙ₊₁-aₙ|=(½)ⁿ|b-a|, then it follows that for m>n |aₘ-aₙ|≤|aₙ₊₁-aₙ|+|aₙ₊₂-aₙ₊₁|+...+|aₘ₋₁-aₘ| =(½)ⁿ|b-a|+(½)ⁿ⁺¹|b-a|+...+(½)ᵐ⁻¹|b-a|

Showing convergence can be pretty short: 1. If an and an+1 are on the interval [x, y], then all am with m>=n are on [x, y]. This can be shown by taking the cases an

I put L = x * a + y * b, and then you can show that as N increases that x and y converge to 1/3 and 2/3 respectively (the same answer that Professor Penn gets)..

This one could be solved using a bit of diagrams. Let L(A, B)=|A-B| - length of a section [A,B]. Let L=L(a,b) - length of the first section. And for now let's assume that a0

@SeresHotes25

Жыл бұрын

And we can have one more cool representation of the problem. We can draw in 2D a spiral, which starts at a0, goes up and down, intersecting horizontal line at a1, goes up intersecting the line at a2, goes down intersecting the line at a3 and so on. This spiral gets smaller and smaller down to the limit point. We can create a natural formula for such spiral. We can see that |z-a0| = 2L/3 and |z-a2| = L/6. It gets 4 times smaller each full rotation. Thus, the formula is r = r0 * 4^(-phi/2Pi) or r = r0 * 2^(-phi/Pi) - each half rotation a_n gets closer to the center. We could use r0 as 2L/3.

@SeresHotes25

Жыл бұрын

Also, that's not a full proof. It's more or less a plan of proof.

This is a trivial problem in linear algebra. Adding the equation a[n+1]=a[n+1], we have (a[n+2],a[n+1])=M(a[n+1],a[n]) where M is a 2x2 matrix with constant coefficients. Now diagonalise M, and you can compute its nth power.

@ZeroPlayerGame

Жыл бұрын

Nice one! You can also completely avoid the droll limit theorems, too.

@dmytryk7887

Жыл бұрын

This was my favorite approach with problems like this. One nice aspect is: the eigenvalues are 1 and -1/2 with corresponding eigenspaces [1, 1] and [2, -1]. The starting vector has a component in each eigenspace. The [1, 1] component stays fixed since the corresponding eigenvalue is 1. The other component is scaled by -1/2 at each multiplication so -> 0 and it bounces back and forth as it vanishes.

If you instead average the last term with either _a_ or _b_ based on a coin toss, do you get a 1D fractal as per the chaos game? Or does it not work like that in 1D?

@leyasep5919

Жыл бұрын

IIRC it does. Use 3 points and you get a Sierpinsky triangle 🙂

I misread the board when I went to start the problem and thought it was a_0 = 0 🤦🏻‍♂️ although the way I solved it for that case was neat because it gave me the denominator as 2^n and the Jacobsthal numbers for the numerator, and from there I used the fact that the Jacobsthal numbers are the closest integers to (2^n)/3 to get 1/3 in the limit. Neat! :D

This is equation is just a 2nd order difference equation and hence directly solvable. So not sure why Michael has solved it like this.

@godfreypigott

Жыл бұрын

Because he has a concept in mind that he wishes to TEACH. As he has in EVERY video. People who say "I have a method - I'm not interested in another" don't properly learn maths.

Dominating comment around 3:30 is a bit strong given that 5+11=16

@0:20 - by inspection, this recursion works for any constant value of a at all. If a0≠a1, then we will get a binary chop: 0.10101010 (in binary), which means it will limit down to 2/3rds the distance between a0 and a1, aka a0 + 2/3(a1-a0), aka (a0+2a1)/3. Let's see if a) I'm right, and; b) how you are supposed to do these.

By Cantor’s nested intervals theorem, we know the sequence of intervals [a_i, a_(i + 1)] with i = 0, 1, 2,… converges to a single point. That gives convergence of the sequence quite trivially. As for finding the exact point of convergence, I suspect some sort of geometric series sum with ratio 1/2 to be the answer. Not particularly keen on working it out to specifics right now though. It’s a linear recursion, solving it shouldn’t be too hard. Then getting the answer should be easy by taking n to infinity. Decided to solve it and yeah, one of the terms in the recursion is -1/2 to the nth power so it vanishes as n goes to infinity and the other term is 1 so it remains the same, and so the coefficient of that term is the answer. It turns out being a_0 + 2/3(a_1 - a_0)

If a = 0, b = 1, then this is 1 - 1/2 + 1/4 - 1/8...you end up at 2/3 of the way from 0 to 1. So I think this ends up as 2/3 of the way from a to b: a + (2/3)(b - a) = a/3 + 2b/3

I like BOINK that sometimes you BOINK have a series that NBOINK converges to zero, and BOINK there might be distBOINKurbances along the way, but they don't BOINK matter in the end.

It is thé same as finding centre of Gravity of one mass at a and two masses at b. In a récursive way. Or mixing one measure of water of a degrees and 2 of b degree... Mixing it one by one... Alternatively..3 masses one at a and two at b have thé same Gravity centre as two masses at (a+b)/2 and one at b... And then you repeat thé same thing from thé other side... This is quite easy to catch in an équation...

@josleurs4345

5 ай бұрын

Yes it is just an average récursion of thé 3 values a,b,b... So a,b,b. Has thé same average as (a+b)/2, (a+b)/2, b and then (a+b)/2 , (a+3b)/4, (a+3b)/4. Has alsof thé same average... Só We have a_n, a_n+1 , a_n+1 a_n Will move tô thé right and An+1 Will move tô thé right or left depending on odd or even... And An and An+1 Will move tô each other... Converge tô thé average... In a way just playing with 3 weights tô determine thé center of gravity...

It is straightforward to show that |a_n-a_(n+1)| = 1/2 |a_(n-1)-a_n|, so the limit goes to 0. Hence is Cauchy and converges. The value proceeds as shown.

@danielthemaniel3856

9 ай бұрын

Or, knowing that you can move forward by considering the telescopic series a_n-a_{n-1}+a_{n-1}+a_{n-2})+...+a_3-a_2+a_2-a_1

Just imagine walking on the number line… The limit is given by: a+(b-a)*(1-1/2+1/4-1/8+…) =a+(b-a)*(1/2)/(1-1/4) =a+2(b-a)/3 =(a+2b)/3.

What level is the content of this channel ? Is this like high school or a bit higher ?

If a

Any other method?

@schweinmachtbree1013

Жыл бұрын

Yes there is a much easier method, which also removes the need for the hypotheses _a_ > 0 and _b_ > 0 (Michael's method actually works for _a_ ≥ 0 and _b_ ≥ 0, which was triggering me the whole video). The recurrence is a special case of s_2 a_(n+2) + s_1 a_(n+1) + s_0 a_n = 0, which is itself a special case of s_k a_(n+k) + s_(k-1) a_(n+k-1) + ... + s_1 a_(n+1) + s_0 a_n = 0 which is called a linear recurrence with constant coefficients. There is a standard method for solving such recurrences (which parallels the standard method for solving linear ordinary differential equations with constant coefficients, if you have taken a differential equations class in high school or university): one can easily check that if b_n and c_n are solutions of the recurrence then so is u b_n + v c_n for any real numbers u and v. Since the recurrence at hand, a_(n+2) - 1/2 a_(n+1) - 1/2 a_n = 0, has k = 2, there is some general theory which says that its "vector space of solutions is 2-dimensional", which in English means that if we can find two solutions b_n and c_n that are not "essentially the same" (linearly dependent) then u b_n + v c_n accounts for _all_ solutions, and then we can use a_0 = _a_ and a_1 = _b_ to solve for u and v. To find two such solutions we make the guess a_n = r^n: plugging this into the recurrence, which can be written as 2 a_(n+2) - a_(n+1) - a_n = 0, one quickly arrives at the equation 2r^2 - r - 1 = 0, which factorises as (r-1)(2r+1) = 0 r=1 or r=-1/2, and this means that b_n = 1^n = 1 and c_n = (-1/2)^n are two solutions - since they are not (essentially) the same (which corresponds to 2r^2 - r - 1 having distinct roots), _every_ solution of the recurrence is of the form u + v (-1/2)^n for some numbers u and v. Using a_0 = _a_ and a_1 = _b_ we have _a_ = u + v and _b_ = u - v/2, from which you can easily solve for u and v (as others in the comments section have done). From this closed form for a_n we can easily calculate the limit: since |-1/2| This method is superior because it is very general, and also it doesn't require the monotone convergence theorem (monotone sequence theorem); indeed it doesn't make use of < or ≤ (increasingness or decreasingness) at all so _a_ and _b_ can even be complex numbers. If the roots r_1 = 1 and r_2 = -1/2 had turned out to be complex (they have to be complex conjugates if the coefficients s_2, s_1, s_0 are real) then the absolute value in "|-1/2| < 1" generalises to a modulus in "|r_2| < 1". If one contemplates the general situation, one sees that if r_1 has modulus < 1 then a_n = u b_n + v c_n = u (r_1)^n + v (r_2)^n is asymptotic to v (r_2)^n (and similarly if r_2 has modulus < 1).

42

Vsuace Michael

Very good - we could call this average recursion a "Super-arithmetic mean" (SAM) - but it is nothing more than a Weighted mean (WM) with W[0] = 1 and W[1] = 2 - the entire recursion is replaced by a single weighted mean. I wonder if we could use this same method to calculate the limit of the Arithmetic-Geometric Mean (AGM) and save some computation time - after all if the SAM converges and Geometric Mean (GM) is less or equal to Arithmetic Mean (AM) according to the Mean Inequalies (GM

@ZeroPlayerGame

Жыл бұрын

No, unfortunately, AGM does not have an algebraic closed form for sure - you can use it to compute elliptic integrals, and those don't. I don't know if anyone has proven it specifically for AGM, but alas, no luck.

@alexdemoura9972

Жыл бұрын

@@ZeroPlayerGame I see. Thanks. Let's think just for a moment. Despite the GM component converging faster than AM - the square root operation (assuming two variables only: a, b > 1) is non-linear in contrast to the linear AM component. And that would be enough to make AGM a mean without algebraic form - despite AGM converges - the algebraic form for the limits of the recursions are different from each other depending on the values of a[0], b, a[1], a[2],... etc. However, since there is a convergence to some value between a and b - could we think there is a non-linear asymptotic curve - always approaching and never touching the limit value. According to you, this asymptotic curve may have a variety of forms (algebraic or not) depending on the initial values a and b making it impossible to achieve a single general algebraic form for all possible asymptotics. It is interesting, and you mentioned elliptic integrals - could we think that AGM has a non-analytical integral form? Just for comparison: Recursive Arithmetic Mean is for the circumference, as Arithmetic-Geometric Mean is for the perimeter of the ellipse. The perimeter of the ellipse can only be obtained through the (infinite) use of elliptic integrals without having a defined algebraic form - and Ramanujan's formula for this perimeter is only an approximation never reaching the exact value. By the way, Ramanujan used the Root Mean Square (RMS) between the axes for this approximation. Perhaps there is a similar algebraic form that also uses RMS to get a reasonable approximation of the AGM. What do you think? Am I hallucinating too much? Too much interaction with AI?😆😆😆 Don't bother, thanks again, Alex.

@ZeroPlayerGame

Жыл бұрын

@@alexdemoura9972 I'd assume you could draft an approximation for AGM from approximations of elliptic integrals, yeah. As for it being computationally cheaper - not so sure. AGM uses one complex operation, square root, per iteration, and it's the most optimized one of complex operations you're gonna get. And as you mention, it converges blazingly fast, you approximately double the amount of correct digits with each iteration - and there's not many digits in standard-issue computer numbers! So I imagine there wouldn't be much point to trade off accuracy for speed.

@ZeroPlayerGame

Жыл бұрын

@@alexdemoura9972 oh in fact, I just checked and Wikipedia has a closed-form expression for AGM as an elliptic integral, if you wanna tinker with that.

@alexdemoura9972

Жыл бұрын

@@ZeroPlayerGame Thanks, Alex, I found it in Wikipedia. It is not the case of trade-off - it is more in the P-NP business. Despite Ramanujan finding a very good approximation for the perimeter of the ellipse, nobody ever proved it works in all cases. Even if AGM doubles the accuracy with each interaction in all cases, I suppose nobody had proven, and we don't have a polynomial parameter to compare with - so the number of loops is undetermined - and that makes the AGM interaction an NP (or EXP) case. Let's assume two big numbers a and b, with an order of magnitude 10^N where N is a power of two to make things easy since you mentioned double accuracy per interaction. So we can only suppose N/2 interactions (or program loops) must achieve an accurate integer, plus P/2 interactions (loops) for decimals - where P is a desired precision. We can conclude that the number of interactions of AGM is divergent according to the size of N - and we don't have a polynomial algorithm to check out if it is true in all cases. Could we guarantee this behavior in all cases? Including numbers with different orders of magnitude? And for more than two numbers? - of course, they will be reduced to two AM[1] and GM[1] on the first interaction but... It is just theoretical thinking - it is interesting but I don't think that could help us to win the Clay Millenium Prize of 1 million dollars for solving the P-NP problem. Anyway, thanks again.

hey vsauce, Michael here.

17:48 I don’t know, this result feels wrong for me. (I’m not saying it is wrong!) That means the b value has more weight in the limit value 🤔

@Yoshinoyo1

Жыл бұрын

Might be because from the start, the sequence is more biased by b. a=a0 only occurs for a2=(a0+a1)/2, while b=a1 occurs twice for a2=(a0+a1)/2 and a3=(a1+a2)/2 ? And indeed, if you reverse the role of a and b, you get the opposite result, with a having more weight. Though this is only an a posteriori rough observation !

@praharmitra

Жыл бұрын

if you draw the recursive terms a0, a1, a2, a3, etc. on the real line, it will become obvious that b HAS to be weighted more.

@ramenandvitamins

Жыл бұрын

Good instinct! Symmetry arguments like this are great for reasoning about all kinds of problems. The catch here is that the recursion is not symmetric in a and b, since they appear in order!

@kostasbr51

Жыл бұрын

The result is right. The graphic reminds a ping-pong ball jumping from side to side. The limit is 'somewhere' in between. The reason that 'b' has more 'weight' is that a3 lies in the right side of the graphic, and the following terms will stay on that side. That comes from a

@johnloony68

Жыл бұрын

I started with a0=0 and a1=1, so it just went 0, 1, 0.5, 0.75, 0.625, 0.6875 etc. The other way round would have been 1, 0, 0.5, 0.25, 0.375, 0.3125 etc. The whole sequence can be scaled up or down according to whatever you choose as a0 and a1 (a bit like a temperature scale).

cool

This reminds me of the binary representation of 1/3.

Here's a very simple proof. Define a new sequence that is the difference between consecutive terms: d_n = a_n+1 - a_n = (a_n + a_n-1)/2 - a_n = -(a_n - a_n-1)/2 = -(1/2)(d_n-1) So these difference make a geometric sequence. The infinite sum of these difference must obviously be the limit of a_n minus whatever the initial value was, because d_n is a telescoping series: sum(d_n) = sum(a_n - a_n-1) = lim(a_n) - a_0 But we can also find this infinite sum using the well known formula for geometric series: sum(d_n) = d_0/(1 - (-1/2)) = (2/3)d_0 Therefore: lim(a_n) = a_0 + (2/3)(a_1 - a_0) = (a_0 + 2a_1)/3

It's bounded by , and the difference between the terms approaches zero. Simple as that, isn't it?

@godfreypigott

Жыл бұрын

How do you prove that the difference between terms approaches zero?

@atreidesson

Жыл бұрын

@@godfreypigott well, the difference between an element y and the previous element x is y-x, then the next term is (x+y)/2, (x+y)/2 - y is (x-y)/2, which is -0.5 times the difference between y and x, this applies to all continuous triples of elements sooo we know (-0.5)^n approaches zero at Infinity

Why not show cauchy criteria? A sequence starting with a,b is bounded between the two, a range of d(a,b). The sequence starting 1 later is bounded by half the range. Then find any subsequence.

tutto questo casino per una ricorrenza lineare??? a[n] =[ (-(1/2))^n ]*(2 (a - b))/3 + (a + 2 b)/3 limit(n,Infinity)a[n]= (a + 2 b)/3

I think these number theory problems start to get boring. Maybe it's better to focus on more advanced mathematics, not only highschool problems

Let M be the 2x2 matrix 1 0 1/2 1/2 Wolfram Alpha informs me that the diagonalization of this matrix is M = S J S^(-1), where J = 1/2 0 0 1, S = 0 1 1 1, S^(-1) = -1 1 1 0. This means M^n = S J^n S^(-1). The limit as n -> infinity converges to S T S^(-1) where T = lim n -> infinity J^n = 0 0 0 1, so that lim n -> infinity M^n = 1 0 1 0. This multiplied by the row vector (a b) in R^2 gives (a a). The a[0] = a element in the series dominates completely in the long run, smearing out the a[1] = b term in the series over infinity until none of it's contribution is left intact. Hope this is right, but it seems pretty basic.

@noahtaul

Жыл бұрын

It’s almost right, but the first row should be 0 1 instead of 1 0. We’re sending the pair (a,b) to (b, (a+b)/2), not (a, (a+b)/2).

@paulkohl9267

Жыл бұрын

@@noahtaul Shoot, yep, thanks, let's see then. It comes out 1/3 of a plus 2/3 of b by the same method outlined above but with the correction.

Oop, I’ve already done this one and already know the answer before watching the video :) . . . Spoiler: . (2a1+a0)/3

Wait, should we check also case 2), in which a > b? They don't seem to be the same case.