A belated Happy Basanta Panchami to all! Once this blog took off, our interest in discussing new ideas grew exponentially ... or is it really exponential? Let's see.
A few days ago, Gourav Banerjee shared this recursion relation (along with the solution after we got tired of trying) with us. \[x_{n+1} = 2x_n(1-x_n).\] Although this is non-linear and looks intimidating, the solution turns out to be quite elegant. The trick is to rewrite the relation as follows. \[ 1 - 2x_{n+1} = 1 - 4x_n + 4x_{n}^{2} = (1-2x_n)^2. \]
This already looks much nicer! Taking the logarithm of both sides, \[\log (1-2x_{n+1}) = 2 \log (1-2x_n). \] Set \(b_n = \log(1-2x_n)\) ... whoa! This is a simple geometric progression, with \(b_{n+1} = 2b_n\). Thus, \(b_n = 2^nb_0\) for some initial \(b_0\), which yields \[1-2x_n = (1-2x_0)^{2^n}, \qquad x_n = \frac{1}{2} \left[1-(1-2x_0)^{2^n}\right]. \]
Looks easy, right? This is an example of the more general logistic map, \[x_{n+1} = rx_n(1-x_n).\] It's interesting to note that in general, this cannot be solved in closed form. Wolfram (2002, p. 1098) has postulated that any exact solution must be of the form \[x_n = \frac{1}{2} \left[1-f(r^nf^{-1}(1-2x_0))\right]. \] The only exact solutions known are for \(r=\pm 2\) and \(r=4\). (Wolfram 2002, p. 1098) and R. Germundsson (pers. comm., Apr. 25, 2002) have proved that no other solutions of this form are possible. In fact, this map deciphers the beautiful Bifurcation Diagram when \(\lim\limits_{n \to \infty} x_n\) is plotted against the so-called rate \(r\). (Technically, the limit of a sequence is unique. But, here in this case of \(x_n\), if it oscillates between two values for sufficiently large \(n\), then we assume two different values of limit also for single \(r.\))
What about \(r=4\)?
Let's look at what we're trying to solve. \[ x_{n + 1} = 4x_n(1 - x_n). \] This should remind you of a particular trigonometric identity: the double angle formula for the sine! \[ \sin(2\theta) = 2\sin\theta\cos\theta = 2\sin\theta\sqrt{1 - \sin^2\theta}. \] Thus, put \(x_n = \sin^2(\theta_n)\) in our recurrence relation, giving \[\sin^2\theta_{n + 1} = 4\sin^2\theta_n(1 - \sin^2\theta_n) = \sin^2(2\theta_n).\] Again, we have a solution of the form \(\theta_{n+1} = 2\theta_n\), hence \(\theta_n = 2^n\theta_0\) for some \(\theta_0\). Thus, we have \[ x_n = \sin^2(2^n\theta_0) \] Another way to motivate the same (thanks to Gourav) is by rearranging the recurrence as \[ 1 - 2x_{n + 1} = 2(1 - 2x_n)^2 - 1,\] which bears similarity with the double angle formula \[ \cos(2\theta) = 2\cos^2\theta - 1.\] Substituting \(1 - 2x_n = \cos\theta_n\) will ultimately lead to the same solution. The trigonometric substitutions are admittedly quite a leap; but mathematics is all about finding such patterns and similarities!
What about \(r=-2\)?
Here's Gourav's solution: rewrite \(x_{n + 1} = -2x_n(1 - x_n)\) as \[x_{n + 1} = 2\left(x_n - \frac{1}{2}\right)^2 - \frac{1}{2}, \qquad x_{n + 1} - \frac{1}{2} = 2\left(x_n - \frac{1}{2}\right)^2 - 1.\] Like before, this bears similarity with the double angle formula \(\cos(2\theta) = 2\cos^2\theta - 1\), hence putting \(x_n - 1/2 = \cos\theta_n\) leads to \[\cos\theta_{n + 1} = \cos(2\theta_n), \qquad \theta_n = 2^n\theta_0.\] Thus, \[x_n = \frac{1}{2} + \cos(2^n\theta_0).\] Restoring the value of \(\theta_0\), we finally obtain \[x_n = \frac{1}{2} + \cos\left(2^n\cos^{-1}\left(x_0 - \frac{1}{2}\right)\right).\] To conclude, please share your thoughts on the comment section of our posts to retain our discussion really exponential one!
Some interesting links you may miss:
Comments
Post a Comment