**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 }*+

*β*(1)

*a*_{n}

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*_{0} and *a*_{1} 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*_{2}, 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*_{0} = 1, and *a*_{1} = 1. To find *a*_{2} (use *n* = 0), Equation (2) is used: *a*_{2} = *a*_{1} + *a*_{0} = 1 + 1 = 2, *a*_{3} = *a*_{2} + *a*_{1} = 2 + 1 = 3, *a*_{4} = *a*_{3} + *a*_{2} = 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*_{1000}?” 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*_{999} and *a*_{998 }since *a*_{1000} = *a*_{999} + *a*_{998}; but, since terms *a*_{999} and *a*_{998 }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*_{1000} 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*

_{0}and

*a*

_{1}. 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.

Daddy

said:Awesome. Daddy is proud. You found a treasure (structure of the Fibonacci set of numbers) when doing something that was completely unrelated. That’s what mathematical research is about!!!

gracejisunkim

said:very proud!

worldpark

said:Congrats on your achievement!

Pingback: Three Personas: English Class Poem | Grace Ji-Sun Kim