just an average recursion...OR IS IT?

Comments · 224

• AN

  @anthonator1033 · 3 years ago

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

  174

• FA

  @fahrenheit2101 · 3 years ago

  Intuitively: <br>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. <br>Brackets will indicate the location of the walker. <br>(A) ---------------------------- B <br>Their next destination is B (a_2) <br>A ----------------------------- (B) <br>Then they need to go halfway between A and B, so they walk backwards to the midpoint. <br>A ------------ (C) ----------- B <br>Now they need to go halfway between the midpoint and B, so they go halfway back to B. <br>A ---------------- C ----- (D) ------ B <br>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. <br>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 <br>x - 1/2x + 1/4x - 1/8x +..... = x (1 - 1/2 + 1/4 - 1/8 +....) = 2/3 x (using the formula for geometric series) <br> <br>Now I&apos;ll watch the video (hopefully 2/3 was right...)<br>Hmm, in terms of a and b, that should be...<br>a + 2/3(b-a) = 1/3(3a+2b-2a) = 1/3(a+2b), which is the video answer. Nice!

  189

• TI

  @timseytiger9280 · 3 years ago

  Dominating comment around <a href="https://www.youtube.com/watch?v=EBdEMIJK6aY&amp;t=210">3:30</a> is a bit strong given that 5+11=16

  12

• CM

  @cmilkau · 3 years ago (edited)

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

  45

• GA

  @GandalfTheWise0002 · 3 years ago (edited)

  Here&apos;s an alternative method by solving directly for &nbsp;a[n] = 1/3 (a + 2b + &nbsp;(-1)^n 2^(1 - n) (a - b) ). &nbsp; &nbsp;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. &nbsp; 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. &nbsp;The limit &nbsp;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.

  96

• CA

  @caiotmz · 3 years ago

  <a href="https://www.youtube.com/watch?v=EBdEMIJK6aY&amp;t=140">2:20</a> Lateralus by Tool starts playing

  2

• JE

  @JeanYvesBouguet · 3 years ago

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

  21

• PE

  @pederolsen3084 · 3 years ago (edited)

  An easier proof of convergence: &nbsp;Assume a[n-1]&lt;a[n], then a[n-1]&lt;a[n+1]&lt;a[n] since a[n+1] is an average. &nbsp;Moreover a[n+1]&lt;a[n+2]&lt;a[n] by the same argument and the length of the interval is halved each time since (a[n]-a[n+1]) = a[n] - (a[n]-a[n-1])/2 = (a[n-1]-a[n])/2. &nbsp;Thus we have a sequence bounded by nested intervals that is shrinking exponentially fast.

  2

• RE

  @redpepper74 · 3 years ago (edited)

  I found an answer on math overflow on how to turn a recursive sequence like this one into an explicit sequence. <br><br>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: <br>a[n] = [(a + 2b) + (2a - 2b)(-1/2)^n]/3<br><br>I bet you can use this technique on any recursive formula with the form a[n] = j*a[n-1] + k*a[n-2] + …<br><br>[edit] oop top comment did the same thing as me 😅

  2

• LA

  @lambertch · 2 months ago

  As someone said in the comments, “set up the matrix”, i.e., this is a second order linear dynamical system in discrete time, and you solve for the “initial state response” by finding its eigenvalues and eigenvectors.

  3

• SU

  @Sugarman96 · 3 years ago

  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.

  17

• GU

  @GuzmanTierno · 3 years ago

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

  6