Theodore A. Lee: Finding Terms in a Recursive Relation

Tags

competition, first place, Liberty High School, Math, Penn State University, PJAS, science, Theodore A. Lee

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:

a_n+2=  αa_n+1 + βa_n                                                            (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 a₀ and a₁ are required. For example, the Fibonacci sequence is a set of numbers which can be generated using α =1 and β =1, given by

a_n+2 = a_n+1 + a_n.                                                          (2)

.

The subsequent term, say a₂, 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: a₀ = 1, and a₁ = 1. To find a₂ (use n = 0), Equation (2) is used: a₂ = a₁ + a₀ = 1 + 1 = 2, a₃ = a₂ + a₁ = 2 + 1 = 3, a₄ = a₃ + a₂ = 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 1000^th term in the above Fibonacci sequence a₁₀₀₀?” One approach is to determine that term by summing the preceding two terms, but this would be ‘tedious’ to do. That is, to obtain a_{1000 ,} one will need to determine a₉₉₉ and a₉₉₈ since a₁₀₀₀ = a₉₉₉ + a₉₉₈; but, since terms a₉₉₉ and a₉₉₈ 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 a₁₀₀₀ is to rewrite Equation (1) or (2) into a matrix form, and determine a direct formula to find the n^th term a_n based only on the two initial values a₀ and a₁. 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.

Advertisement