Finding Terms in a Recursive Relation

Directly and Efficiently Using Matrices

By:  Theodore A. Lee, Freshman

Liberty High School

My son competed at the regional Pennsylvania Junior Academy of Science (PJAS) competition and placed “First Place!”  He went to Penn State to compete at the state level (May 12-14, 2013).

He was confident when he left for the competition.  He competed Monday May 13th and placed “FIRST Place”!  I am a proud mom.  This is the abstract from his presentation at PJAS.

Abstract

A recursive relation is a relationship between a set of two or more terms in an equation. The relationship expresses a term as a function of the preceding terms. A general linear two-termed recursive relation was used in the present study, and is given by:

an+2=  αan+1 βan                                                            (1)

where n is a whole number (n = 0, 1, 2, …) to denote the term number in the sequence, and α ≠ 0 and β ≠ 0 are any real numbers. To determine other values in the sequence in Equation (1), two initial values a0 and a1 are required. For example, the Fibonacci sequence is a set of numbers which can be generated using α =1 and β =1, given by

an+2 = an+1 + an.                                                          (2)

.

The subsequent term, say a2, in the sequence is found by summing the two preceding terms. That is, to find the sequence of numbers given by Equation (2), two initial given values are required: a0 = 1, and a1 = 1. To find a2 (use n = 0), Equation (2) is used: a2 = a1 + a0 = 1 + 1 = 2, a3 = a2 + a1 = 2 + 1 = 3, a4 = a3 + a2 = 3 + 2 = 5, and so on, so that a sequence of numbers (that is, a set of Fibonacci numbers) are generated:

{1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …}

Using the recursive relation given by Equation (1) above, one may ask: “What is the 1000th term in the above Fibonacci sequence a1000?” One approach is to determine that term by summing the preceding two terms, but this would be ‘tedious’ to do. That is, to obtain a1000 , one will need to determine a999 and a998 since a1000 = a999 + a998; but, since terms a999 and a998 are not known, one needs to find the two previous terms to those two terms, and so on until all the previous terms are established.

A way to avoid this ‘tedious’ or ‘indirect’ process of finding a1000 is to rewrite Equation (1) or (2) into a matrix form, and determine a direct formula to find the nth term an based only on the two initial values a0 and a1. A direct formula for Equations (1) and (2) were derived in this study which involved matrix exponentiation of a 2 x 2 matrix for each formula.

Although the direct formula for finding the Fibonacci sequence of values is convenient, the direct formula does incur more mathematical operations (multiplications and additions) due to matrix exponentiation compared to the recursive relation (Equation (2)). To reduce the number of operations based on the direct matrix formulae, diagonalization of a 2 x 2 matrix was achieved. This diagonalization process uses eigenvalues and eigenvectors which are incorporated into the direct matrix formula.

On the other hand, the direct formula for the general recursive relation (Equation (1)) using matrix exponentiation significantly reduces the number of operations compared to the number of operations required when using the general recursive relation. The number of operations incurred using this general recursive relation is (surprisingly) related to the sum of the sequence of Fibonacci numbers – something that was not expected prior to the study. In fact, I was thrilled to discover this!!

The presentation will address a summary of results found in this study.

[read also:  Explorations and Discoveries in Math & High School]

________________________________________________________________________

Theo Andrew is a freshman at Liberty High School.  He is on the soccer team, track team and in several clubs at his High School.  He enjoys playing the piano and violin.