**Tags**

equation, Lehigh Science Fair, Liberty High School, Math, Matrices, Pennsylvania Junior Academy of Science, real number, Recursive relation, science, Theodore A. Lee, whole number

**This is my oldest son’s project for “PJAS” (Pennsylvania Junior Academy of Science) and for the Lehigh Science Fair**. **Very proud of his work and accomplishments. I used to be a Math Star way back in Highschool but I absolutely don’t have a clue what this is all about……**

*“Finding Terms in a Recursive Relation Directly and Efficiently Using Matrices”*

By Theodore A. Lee

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 formulae for Equations (1) and (2) are convenient, the direct formulae do incur significantly more mathematical operations (multiplications and additions) due to matrix *exponentiation* compared to the recursive relation. To reduce the number of operations based on the direct matrix formulae, diagonalization (or factorization) of the 2 x 2 matrix was achieved. This diagonalization process uses *eigenvalues and eigenvectors* which are incorporated into the direct matrix formulae.

It was found that the number of operations required to find any term in the recursive relation based on the direct matrix formulae using diagonalization incurs almost the same number of operations in determining terms based on the ‘tedious’ recursive relation.

The presentation will address a summary of discoveries found in the study, and present important results of my project.

[read also: High School: A New Beginning]

_________________________________________________________________________________________________

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.

Worldpark

said:This looks very fascinating!

karen

said:Theo,

You are BRILLIANT!!!!

Keep up the great work!!!

I am sooooo proud of you!

Emo from Toronto

gracejisunkim

said:He placed first place!!

Wendy Mao

said:Great job Theo! Congratulations on first place, that’s excellent!

gracejisunkim

said:Thank you….so happy for him.

Lee

said:A natural … great work!!

Pingback: Theodore A. Lee: Finding Terms in a Recursive Relation | Grace Ji-Sun Kim