Always bringing me back

Consider the simple linear map L : x a x + b \mathcal{L} : x \rightarrow ax+b where a = 4 / 7 a=4/7 , and b = 5 b = 5 . Starting at some initial point X 0 X_0 , we move to our next point X 1 X_1 according to X 1 L ( X 0 ) X_1 \rightarrow \mathcal{L}(X_0) .

Suppose we iterate the map infinitely many times, ending up at X X_\infty , what is the value of X X_\infty ?


The answer is 11.666666667.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Pranshu Gaba
Jun 8, 2015

Solution 1: According to the definition, X 1 = L ( X 0 ) = a X 0 + b X_1 = \mathcal{L}(X_0) = aX_0 + b

X 2 = L ( X 1 ) = a X 1 + b = a ( a X 0 + b ) + b = a 2 X 0 + b ( 1 + a ) X_2 = \mathcal{L}(X_1) = aX_1 + b = a(aX_0 + b) + b = a^2X_0 + b(1 + a)

X 3 = L ( X 2 ) = a X 2 + b = a ( a X 1 + b ) + b = a 3 X 0 + b ( 1 + a + a 2 ) X_3 = \mathcal{L}(X_2) = aX_2 + b = a(aX_1 + b) + b = a^3X_0 + b(1 + a + a^2)

Observation: In general, we can write X n X_n as

X n = a n X 0 + b i = 0 n 1 a i X_n = a^n X_0 + b \sum _{i = 0} ^{n - 1} a^{i}

Now X = lim n X n = lim n ( a n X 0 + b i = 0 n 1 a i ) X_{\infty} = \displaystyle \lim _{n \to \infty} X_n = \displaystyle \lim _{n \to \infty} \left(a^n X_0 + b \sum _{i = 0} ^{n - 1} a^{i}\right)

Since a < 1 , lim n a n = 0 |a| < 1, \displaystyle \lim_{n \to \infty} a ^n = 0 . Also, lim n b i = 0 n 1 a i = b × 1 1 a \displaystyle \lim_{n \to \infty} b \sum _{i = 0} ^{n - 1} a^{i} = b \times \frac{1}{1 - a}

Therefore, X = b 1 a = 5 1 4 7 = 35 3 X_{\infty} = \frac{b}{1- a} = \frac{5}{1 - \frac{4}{7} } = \boxed{\frac{35}{3}} _\square


Solution 2: Draw graphs of L 1 : y = L ( x ) L_1 : y = \mathcal{L}(x) and L 2 : y = L 1 ( x ) L_2 : y = \mathcal{L}^{-1} (x)

Start with the point ( X 0 , L ( X 0 ) ) (X_0, \mathcal{L}(X_0)) , i.e. ( X 0 , X 1 ) (X_0, X_1) . If we take a reflection of this point off the y = x y = x line, we obtain the point ( X 1 , X 0 ) ( X_1, X_0) . Then we move parallel to the y y axis until we reach the line y = L ( x ) y = \mathcal{L}(x) . We will meet at the coordinates ( X 1 , X 2 ) (X_1, X_2) . We then move to ( X 2 , X 1 ) (X_2, X_1) and then ( X 2 , X 3 ) (X_2, X_3) . This is shown in the graph below.

graph graph

If we continue this process infinitely many times, we can show that we will be converging to a point. Because after every iteration, the area of the triangle formed by the lines L 1 , L 2 L_1, L_2 and line joining points ( X n , X n + 1 ) (X_n, X_{n+1}) and ( X n + 1 , X n ) (X_{n+1}, X_{n}) decreases and the triangle converges to a point. We then reach the point ( X , X ) (X_{\infty}, X_{\infty}) . At this point, the x x coordinate is equal to the y y coordinate is equal to X X_{\infty} , since for very large n n , X n = X n + 1 X_{n} = X_{n+1} .

We substitute x = y = X x = y = X_{\infty} in y = a x + b y = ax + b .

X = a X + b X_{\infty} = aX_{\infty} + b . Therefore X = b 1 a X_{\infty} = \frac{b}{1-a} . _\square .

Moderator note:

Always be careful when interchanging limits and summation / integration / differentiation.

For example, consider the sequence of numbers a i , j = 1 i a_{i,j} = \frac{1}{i} if j i j \leq i , 0 otherwise.

Then, lim i j a i , j = lim i 1 = 1 \lim_i \sum_j a_{i,j} = \lim_i 1 = 1 but j lim i a i , j = j 0 = 0 \sum_j \lim_i a_{i,j} = \sum_j 0 = 0 .

Hello Challenge Master,

Thanks for reviewing my solution.

I agree with you that one should be careful when interchanging limits and summation / integration / differentiation. However I did not understand the example. What does lim i 1 \lim_i 1 mean?

I don't see where I have interchanged the limits and summation in my solution. Are you referring to the step lim ( a n X 0 + b i = 0 n 1 a i ) = lim a n X 0 + lim b i = 0 n 1 a i \lim (a^n X_0 + b \sum _{i = 0} ^{n - 1} a^{i}) = \lim a^n X_0 + \lim b \sum _{i = 0} ^{n - 1} a^{i} ? I can do that because both the limits exist and are finite; am I right?

I have also added another solution (Solution 2). It seems to be much simpler. Can you review it?

Thanks

Pranshu Gaba - 6 years ago

Nice question, but why is this in the physics section.

Rohan Joshi - 4 months, 1 week ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...