Tags

, , , , , , , , , ,

This is my oldest son’s project for “PJAS” (Pennsylvania Junior Academy of Science) and for the Lehigh Science Fair.  Very imagesCAGQ6ZE6proud 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:

 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 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]

_________________________________________________________________________________________________

199734_207076775974029_5061310_nTheo 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