Recurrence Relations
This past weekend, I participated in the 33rd annual Westmont Mathematics Field Day at Westmont College. The competition was broken into three categories: a written test, a speed math college bowl, and a chalk talk. The calk talk was centered around “Recurrence Relations“ this year. Only learning about the competition two weeks prior, Zander Henson, Ethan Bergman, John Chung, and I all frantically searched the web for related topics about recurrence. Of course, I would have loved to relate recurrence to manifolds and topology, but it was a little more complicated than we all thought. Instead, we landed on finding the explicit form of a recurrence relation using linear algebra, and finally generalizing the project.
First, we had to really understand what a recurrence relation is. Fundamentally, recurrence is any output reliant on some previous terms. In mathematics, this is most famous in the Fibonacci sequence or the Catalan numbers. The next term of the Fibonacci sequence, for example, is the sum of the previous two, with initial conditions of 0 and 1. This would be a second-order recurrence relation since it is only defined by some function of two terms.
Recurrence relations are then further divided into homogenous and non-homogenous relations. Homogenous relations are only defined by some function of previous terms. Non-homogenous, however, have some function of n defining terms. When that f(n) is just a polynomial, it is easy to convert the relation into a homogenous form by subtracting the previous terms until f(n) = 0. See below for an example of that:
an = an-1 + 2an-2 + 3n
- (an-1 = an-2 + 2an-3 + 3n -3)
...an = 2an-1 - 2an-3 - 2an-4
If the f(n) value is not a polynomial, it becomes harder to solve into a homogenous form, and you should instead solve for a homogenous and particular solution.
Recurrence is great when finding the relationship between numbers, but becomes wildly inefficient in solving for larger term numbers or computing. Luckily, any recurrence relation can also be represented in an explicit form. Through linear algebra, we can derive the basic steps for solving homogenous relations for their explicit forms.
Our chalk talk used the Fibonacci Sequence as an example. First, we have to represent our Fibonacci sequence as a linear transformation of some vector. Using the first two terms, 0 and 1, this 2x2 linear transformation matrix comes out to:
For all future calculations, this will just be referred to as “A”. This matrix is just the linear transformation to get from a vector to the first two terms. The next step is finding the eigen values associated with this matrix. This is where the linear algebra first begins. For any matrix, the eigenvalue, λ, is just a scalar that changes the magnitude of the vectors in that space and not the direction. This woule be represented in the equation Ax = λx where A was our matrix and x are the eigen vectors for our matrix. Each matrix has it own eigenvalues that keep these conditions true. We don’t know the eigenvectors yet, and we only care about non-trivial solutions, so we can rearrange the equation to be 0 = det(A - λI), where I is the identity matrix. Using our own Matrix, A, we find the two eigenvalues to be:
(1 + √5 )/2
(1 - √5 )/2
We used φ and σ respectively. Next we can find those eigenvectors we were just missing. Using the same equation, we can multiply the top rows of all the matrices and all the bottom rows to obtain the two equations:
x + y = λx
x = λy
Solving these two equations, we get the two vectors: (φ , 1) and (σ, 1).
Next, remember that any n-dimensional vector can be represented by a linear combination of n vectors, we find the constants for our vectors. Those two constants come out to:
Now we have all of the pieces of the equation we need to solve! Remembering back to our original equation, we can rearrange it and substitute so it is represented will all of our known values: c: constants, λ: eigenvalues, x: eigen vectors
Vn = An-1v1
= An-1(c1x1 + c2x2)
= (c1λ1n-1x1 + c2λ2n-1x2)
When we substitute in what we found previously, we are left with the equation below:
We are done! This is the explicit form for the Fibonacci Sequence, also known as Binet’s Formula. Combining vectors and matrices through linear algebra, you can apply this to any homogenous recursive relation.
At the end of the competition day, Professor Russel Howell gave his own Chalk Talk on recursive relations. He used the Towers of Hanoi as his example, writing a code to solve the tower for any “n“ number of rings. Because every move of the rings is reliant on the previous moves, it is easy for a computer to handle this software. He also mentioned the Fibonacci sequence, using his own code, and said it would take 1.2 trillion years to calculate over 1,000 digits recursively. The Binet Formula above, however, would take a computer less than a minute to find any large term number. Recursion is useful in computers, density models, even quantum physics. In a later post, I hope to cover how it can relate to topology as well. For now, though, I think it is really cool that we have a set process to find the explicit form of any recursive sequence and to find any term value without having to find that many terms before it.