Zelaron Gaming Forum - Look out man, 5-0!

Quote:

Originally Posted by Demosthenes (Post 711203)

Not at all what I expected. Then I looked closer at your statement and discovered all the golden ratios. Always knew that the ratio of successive terms in the fibonacci sequence tended to the golden ratio, but didn't realize that you could actually generate fibonacci terms that way. Pretty cool.

I'm glad you liked it! Yes, linear recurrence relations like $\reverse a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_n a_{n-k}$ lend themselves well to explicit solutions by the transformation $\reverse a_n = r^n$ , but to be fair, there aren't really that many examples of them of order $\reverse \ge 2$ that are interesting. Nonlinear ones, such as the logistic map $\reverse a_n = ra_n(1-a_n),$ become very interesting and intractable very quickly, though:

https://www.youtube.com/watch?v=ovJcsL7vyrk

Personally, I think the weird connections between recurrence relations, differential equations, generating functions and derivatives are particularly fascinating. For example, the Legendre polynomials $\reverse P_n(x)$ (which have a very large number of applications in physics, probability theory, etc) can be defined in either of the following four ways:

1. In terms of a recurrence relation (with $\reverse P_0(x) = 1,\,P_1(x) = x$ ):

$\reverse (n+1) P_{n+1}(x) = (2n+1) x P_n(x) - n P_{n-1}(x)$

2. In terms of n-th derivatives:

$\reverse P_n(x) = \frac{1}{2^n n!} \frac{\mathrm{d}^n}{\mathrm{d}x^n} \left(x^2 -1\right)^n$

3. As coefficients of a series expansion (from electrostatics):

$\reverse \frac{1}{\sqrt{1-2xt+t^2}} = \sum_{n=0}^\infty P_n(x) t^n$

4. As polynomial solutions of an ordinary differential equation (which you get from solving Laplace's equation in spherical coordinates):

$\reverse (1-x^2)y''(x) - 2xy'(x) + n(n+1)y(x) = 0$

If you play around with various polynomial sequences for a while (particularly orthogonal sequences), it becomes "obvious" that there's some sort of space or operator that connects all of the above. In other words, it's a bit like there "has to be" some algorithm to convert a differential equation to a recurrence relation, or vice versa, but the general theory for that is very poorly understood.

Also, as a cool sidenote, you can use the zeros $\reverse x_1,\,x_2,\,\dots,\,x_n$ of the n-th Legendre polynomial $\reverse P_n(x)$ for numerical integration of many "nice" functions $\reverse f(x)$ :

$\reverse \int_{-1}^{1} f(x)\,\mathrm{d}x \approx \sum_{k=1}^{n} \frac{2f(x_k)}{(1-x_k^2)(P'_n(x_k))^2}$

Gauss himself came up with that one, obviously...