Fibonacci Numbers & Its Closest Neighbors

Fibonacci Numbers and Its Closest Neighbors Oreste M. Ortega, Jr. Leyte Normal University Tacloban City, Philippines October 2003 Abstract This study was conducted in view of the need to developing problem-solving skills and to find relevant instructional materials and strategies. This used the problem posing approach exemplified in the work of Kenneth Shaw and Leslie Aspinwall in their article, ”The Recurring Fibonacci Sequence: Using a Pose and Probe Rubric.” The study identified relational characteristics between terms of the Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, .... The identified patterns were verified by using different Fibonacci numbers and the generalizations were confirmed using the proof by mathematical induction. This led to the derivation of Theorem 1 (General Formula) stating the established relationship between the square of any Fibonacci number, Fn , and the product of its ith -closest neighbors, Fn−i and Fn+i and Theorem 2 (The Generalization) which generalizes the difference between two Fibonacci numbers, Fn and Fn+j , and the product of their ith -closest neighbors, Fn−i and F(n+j)+i . These formulas were drawn from five Lemmas. Theorem 1 was drawn from the patterns derived from Lemmas 1 to 5 and Theorem 2 was derived from the patterns derived evident in Lemmas 6 to 10. Theorem 1 and 2 are stated as follows: Theorem 1. (General Formula) The difference between the square of a Fibonacci number, Fn2 , and the product of its th i -closest neighbors Fn−i and Fn+i is (−1)n+i Fi2 , that is, Fn2 − Fn+i Fn−i = (−1)n+i Fi2 for n > i, i = 1, 2, 3, .... Theorem 2. (The Generalization) The difference between the product of two Fibonacci numbers, Fn and Fn+j and the product of its ith -closest neighbors is (−1)n+i Fi Fi+j , that is, Fn Fn+j −Fn−i F(n+j)+i = (−1)n+i Fi Fi+j where n > 1 for i = 1, 2, 3, ... and j = 1, 2, 3, ....

1

1

Introduction

Problem solving is one of the dynamic modes for organizing learning that is consistent with a view of learning that has received renewed attention. Constructivism asserts that students build their own knowledge. This view argues that students must integrate new knowledge into existing internal structures. Students do so by exploring their own environments, manipulating objects in the environment, testing hypotheses, and drawing their own conclusion [9]. Exploring patterns is one of the problem solving strategies that students should occasionally be exposed. This strategy is also recommended by [5]. Through problem solving in mathematics, the ability of the students to observe, discover relationships, draw conclusion, and validate their findings is further enhanced with proper choice of content and problems that are well within the ability of the students to comprehend. While there are several number sequences that are associated to the real world phenomena, the Fibonacci sequence proved to have innumerable associations, not only with other sequences but with nature’s phenomenon as well. The Fibonacci sequence is a sequence of numbers that begin with 1 and 1; and every number, thereafter, is derived by adding the preceding two numbers. The first eight numbers in the sequence are 1, 1, 2, 3, 5, 8, 13, 21. The general formula for finding the nth Fibonacci number Fn is given by Fn = Fn−2 + Fn+1 . The mathematics associated with Fibonacci numbers is widespread, deep and full of mysterious patterns, the reason for the continued fascination by mathematicians. Hence it has become the subject of many mathematical investigations.

2

Results and Discussion

Investigations on the difference between the square of a Fibonacci number, Fn , and the product of its ith left and right closest neighbors, where i is the number of terms in the Fibonacci sequence to the left and to the right of Fn were the following: Fn2 − (Fn−1 )(Fn+1 ) Fn2 − (Fn−2 )(Fn+2 ) Fn2 − (Fn−3 )(Fn+3 ) .. . Fn2 − (Fn−i )(Fn+i ) Resulting the following first Lemma. Lemma 1: The difference between the square of any Fibonacci number, Fn , and the product of its first closest neighbors, Fn+1 and Fn−1 is (−1)n+1 F12 , that is, Fn2 − (Fn+1 )(Fn−1 ) = (−1)n+1 F12 for n > 1. Proof : (Mathematical Induction) For n = 2, 2

F22 − F3 F1 = = = = =

F22 − (F1 + F2 )F1 F22 − F12 − F1 F2 F2 (F2 − F1 ) − F12 −F12 (−1)2+1 F12

Assume that (Fk )2 − Fk+1 Fk−1 = (−1)k+1 F12 . Since Fk+2 = Fk+1 + Fk and Fk−1 + Fk = Fk+1 , then (Fk+1 )2 − Fk+2 F k1 = = = = = =

(Fk+1 )2 − [Fk+1 + Fk ]Fk Fk+1 [Fk−1 + Fk ] − [Fk+1 + Fk ]Fk Fk+1 Fk−1 + [Fk Fk+1 − Fk Fk+1 ] − Fk2 Fk+1 Fk−1 − Fk2 −(−1)k+1 F12 (−1)k+2 F12

Hence, Fn2 − (Fn+1 )(Fn−1 ) = (−1)n+1 F12 for n > 1. Based on further investigations, the following lemmas were formulated. Lemma 2: The difference between the square of any Fibonacci number, Fn , and the product of its second closest neighbors, Fn+2 and Fn−2 is (−1)n+2 F22 , that is, Fn2 − (Fn+2 )(Fn−2 ) = (−1)n+2 F22 for n > 2. Lemma 3: The difference between the square of any Fibonacci number, Fn , and the product of its third closest neighbors, Fn+3 and Fn−3 is (−1)n+3 F32 , that is, Fn2 − (Fn+3 )(Fn−3 ) = (−1)n+3 F32 for n > 3. Lemma 4: The difference between the square of any Fibonacci number, Fn , and the product of its fourth closest neighbors, Fn+4 and Fn−4 is (−1)n+4 F42 , that is, Fn2 − (Fn+4 )(Fn−4 ) = (−1)n+4 F42 for n > 4. Lemma 5: The difference between the square of any Fibonacci number, Fn , and the product of its fifth closest neighbors, Fn+5 and Fn−5 is (−1)n+5 F52 , that is, Fn2 − (Fn+5 )(Fn−5 ) = (−1)n+5 F52 for n > 5. For a more clearer picture of the investigations above, the following tables were presented for a specific Fibonacci number Fn . As evident in the tables, the researcher summarized and synthesized the results and stated the general formula for the difference between the squares of the first n Fibonacci numbers and their ith closest neighbors. 3

Table 1. Rank order of Two Closest Neighbors (i) First Second Third Fourth Fifth .. .

ith Neighbors

(F6 )2

5 and 13 3 and 21 2 and 34 1 and 55 1 and 89 .. .

64 64 64 64 64 .. .

Product of ith Neighbors 65 63 68 55 89 .. .

(F6 )2 − (Fn−i Fn+i ) -1 +1 -4 +9 - 25 .. .

It is easy to recognize that the difference that were of interest in the investigations, except for the signs, are squares of the first five Fibonacci numbers. Further investigations were made on F7 = 13 to validate the above observation. Table 2. Rank order of Two Closest Neighbors (i) First Second Third Fourth Fifth .. .

ith Neighbors

(F7 )2

8 and 21 5 and 34 3 and 55 2 and 89 1 and 144 .. .

169 169 169 169 169 .. .

Product of ith Neighbors 168 170 165 178 144 .. .

(F7 )2 − (Fn−i Fn+i ) +1 -1 +4 -9 + 25 .. .

Fn2 − (Fn+1 )(Fn−1 ) = (−1)n+1 F12 f orn > 1 Fn2 − (Fn+2 )(Fn−2 ) = (−1)n+2 F22 f orn > 2 Fn2 − (Fn+3 )(Fn−3 ) = (−1)n+3 F32 f orn > 3 Fn2 − (Fn+4 )(Fn−4 ) = (−1)n+4 F42 f orn > 4 Fn2 − (Fn+5 )(Fn−5 ) = (−1)n+1 F52 f orn > 5 .. . Fn2 − (Fn+i )(Fn−i ) = (−1)n+i Fi2 for n > i where i = 1, 2, 3, ...(closest neighbors). Theorem 1. (General Formula) The difference between the square of a Fibonacci number, Fn2 , and the product of its ith closest neighbors Fn−i and Fn+i is (−1)n+i Fi2 , that is, Fn2 − Fn+i Fn−i = (−1)n+i Fi2 for n > i, i = 1, 2, 3, .... 4

Proof: Step 1: Show that Fn2 − Fn+i Fn−i = (−1)n+i Fi2 for n > i is true for i = 1. For i = 1, n > 1. Let n = 2. Thus, Fn2 − Fn+1 Fn−1 = (−1)n+1 F12 . i) Show that it is true for n = 2. F22 − F3 F1 = −F12 (1)2 − (2)(1) = −(1)2 −1 = −1(T rue) ii) Assume that it is true for n = k, that is, (Fk )2 − Fk+1 Fk−1 = (−1)k+1 F12 . iii) Show that it is true for n = k + 1, that is, (Fk+1 )2 − F(k+1)+1 F(k+1)−1 = (−1)(k+1)+1 F12 (Fk+1 )2 − Fk+2 Fk = (−1)k+2 F12 Proof: Since Fk+1 = Fk + Fk−1 and Fk+2 = Fk + Fk+1 , then (Fk+1 )2 − Fk+2 Fk = = = = =

Fk+1 (Fk + Fk−1 ) − (Fk+1 + Fk )Fk Fk Fk+1 + Fk+1 Fk−1 − Fk Fk+1 − Fk2 −Fk2 + Fk+1 Fk−1 −[(−1)k+1 F12 ] (−1)k+2 F12 .

Step 2: Assume that Fn2 − Fn+k Fn−k = (−1)n+k Fk2 is true for i = k. 2 Step 3: Show that Fn2 − Fn+(k+1) Fn−(k+1) = (−1)n+(k+1) Fk+1 for n = k + 1.

Proof: Let s = k + 1. Fn2 − Fn+(k+1) Fn−(k+1) = Fn2 − Fn+s F n − s = (−1)n+s Fs2 2 = (−1)n+(k+1) Fk+1 . Therefore, Fn2 − Fn+i Fn−i = (−1)n+i Fi2 for n > i, i = 1, 2, 3, ....

3

Further Explorations

In the light of the findings made on the difference between the square of the Fibonacci number and its closest neighbors, the researcher explored further on some relationships. One investigation made was on the relation of four consecutive Fibonacci numbers. 5

Given four consecutive Fibonacci numbers Fn−1 , Fn , Fn+1 , Fn+2 , the researcher investigated the values resulting from the expression Fn Fn+1 − Fn−1 Fn+2 representing the difference between the product of two consecutive Fibonacci numbers (Fn Fn+1 ) and the product of their first closest neighbors from the left and from the right (Fn−1 Fn+2 ). It is easy to check that the difference oscillates between −1 and +1. Further exploration on the their second closest neighbors from the right and from the left, that is, Fn Fn+1 − Fn−2 Fn+3 result to −2 and +2, Fn Fn+1 − Fn−3 Fn+4 oscillates between −6 and +6, while Fn Fn+1 − Fn−4 Fn+5 resulted to −15 and +15. The results were summarized and synthesized into the following general statements: Fn Fn+1 − Fn−1 Fn+2 = ∓1 = ∓(1)(1) = ∓F1 F2 Fn Fn+1 − Fn−2 Fn+3 = ∓2 = ∓(1)(2) = ∓F2 F3 Fn Fn+1 − Fn−3 Fn+4 = ∓6 = ∓(2)(3) = ∓F3 F4 Fn Fn+1 − Fn−4 Fn+5 = ∓15 = ∓(3)(5) = ∓F4 F5 Fn Fn+1 − Fn−5 Fn+6 = ∓40 = ∓(5)(8) = ∓F5 F6 .. . Fn Fn+1 − Fn−i Fn+(i+1) = ∓Fi Fi+1 As observed from the pattern above, a rule was derived and stated as Lemma 6. Lemma 6. The difference between the product of two consecutive Fibonacci numbers, Fn and Fn+1 , and the product of their ith closest neighbors is (−1)n+1 Fi Fi+1 , that is, Fn Fn+1 − Fn−i Fn+(i+1) = (−1)n+i Fi Fi+1 , where n > 1 and for i = 1, 2, 3, .... Proof: (Mathematical Induction) Step1: For i = 1, we will show that Fn Fn+1 − Fn−1 Fn+(1+1) = (−1)n+1 F1 F1+1 = (−1)n+1 F1 F2 since Fn+1 = Fn + Fn−1 , Fn = Fn+1 − Fn−1 and Fn−1 = Fn − Fn−2 , Fn Fn+1 − Fn−1 Fn+2 = (Fn+1 − Fn−1 )Fn+1 − (Fn − Fn−2 )Fn+2 2 = Fn+1 − Fn−1 Fn+1 − Fn Fn+2 − Fn−2 Fn+2

6

(by Lemmas 1 and 2) 2 − Fn−2 Fn+2 = (−1)n+1 F12 − Fn2 + Fn2 − (−1)n+2 F22 + Fn+1

(by Lemma 1) = = = =

(−1)n+1 (F12 + F22 ) + (−1)n+2 F22 (−1)n+1 (F12 + F22 − F22 ) (−1)n+1 F12 (−1)n+1 F1 F2

Step 2: Assume that Fn F n + 1 − Fn−k Fn+(k+1) = (−1)n+k Fk Fk+1 is true for i = k. Step 3: Show that Fn F n + 1 − Fn−(k+1) Fn+(k+1)+1 = (−1)n+(k+1) Fk+1 F(k+1)+1 Fn F n + 1 − Fn−k−1 Fn+k+2 = (−1)n+k+1 Fk+1 Fk+2 Proof: Since Fn−k = Fn−k−1 + Fn−k−2 and Fn+k+2 = Fn+k+1 + Fn+k , Fn Fn+1 − Fn−k−1 Fn+k+2 = Fn − Fn+1 − (Fn−k − Fn−k−2 )(Fn+k+1 + Fn+k ) = Fn Fn+1 − Fn−k Fn+k+1 − Fn−k Fn+k − Fn−k−2 Fn+k+2

(by inductive hypothesis) = (−1)n+k Fk Fk+1 − Fn−k Fn+k − Fn−k−2 Fn+k+2 (by Theorem 1) = = = = = = =

2 (−1)n+k Fk Fk+1 + (−1)n+k Fk2 − Fn2 + Fn2 − (−1)n+(k+2) Fk+2 2 (−1)n+k (Fk Fk+1 + Fk2 − Fk+2 ) n+k 2 (−1) [Fk (Fk + Fk+1 ) − Fk+2 ] 2 (−1)n+k (Fk Fk+2 − Fk+2 ) n+k (−1) [−Fk+2 (Fk+2 − Fk )] (−1)n+k (−Fk+2 Fk+1 ) (−1)n+k+1 Fk+2 Fk+1

Therefore, Fn Fn+1 − Fn−i Fn+(i+1) = (−1)n+i Fi Fi+1 , where n > 1 and for i = 1, 2, 3, .... With the observations on the relationship between two consecutive Fibonacci numbers and its ith -closest neighbors, the researcher extended to discover other relationship from 7

the difference between the product of Fn and Fn+2 , Fn and Fn+3 , Fn and Fn+4 and Fn and Fn+5 and the product of its ith -closest neighbors, where n > 2 and i = 1, 2, 3, .... The following lemmas were observed: Lemma 7. The difference between the product of the two Fibonacci numbers, Fn and Fn+2 , where n > 2 and their ith -closest neighbors is (−1)n+i Fi Fi+2 , that is, Fn Fn+2 − Fn−i Fn+(i+1) = (−1)n+i Fi Fi+2 where n > 2 and for i = 1, 2, 3, .... Lemma 8. The difference between the product of the two Fibonacci numbers, Fn and Fn+3 , where n > 3 and their ith -closest neighbors is (−1)n+i Fi Fi+3 , that is, Fn Fn+3 − Fn−i Fn+(i+1) = (−1)n+i Fi Fi+3 where n > 3 and for i = 1, 2, 3, .... Lemma 9. The difference between the product of the two Fibonacci numbers, Fn and Fn+4 , where n > 4 and their ith -closest neighbors is (−1)n+i Fi Fi+4 , that is, Fn Fn+4 − Fn−i Fn+(i+1) = (−1)n+i Fi Fi+4 where n > 4 and for i = 1, 2, 3, .... Lemma 10. The difference between the product of the two Fibonacci numbers, Fn and Fn+5 , where n > 5 and their ith -closest neighbors is (−1)n+i Fi Fi+5 , that is, Fn Fn+5 − Fn−i Fn+(i+1) = (−1)n+i Fi Fi+5 where n > 5 and for i = 1, 2, 3, .... Finally, the above generalizations were synthesized into what seemed to be a general formula. Fn Fn+1 − Fn−i Fn+(i+1) = (−1)n+i Fi Fi+1 Fn Fn+2 − Fn−i Fn+(i+2) = (−1)n+i Fi Fi+2 Fn Fn+3 − Fn−i Fn+(i+3) = (−1)n+i Fi Fi+3 Fn Fn+4 − Fn−i Fn+(i+4) = (−1)n+i Fi Fi+4 Fn Fn+5 − Fn−i Fn+(i+5) = (−1)n+i Fi Fi+5 .. . Fn Fn+j − Fn−i Fn+(i+j) = (−1)n+i Fi Fi+j where n > 1 for i = 1, 2, 3, ... and j = 1, 2, 3, .... Based on the above presentation, the researcher inferred his generalization on the Fibonacci numbers and its their closest neighbors. This is Theorem 2. Theorem 2. (The Generalization) The difference between the product of two Fibonacci numbers, Fn and Fn+j , and the product of their ith closest neighbors is (−1)n+i Fi Fi+j that is Fn Fn+j − Fn−i Fn+(i+j) = (−1)n+i Fi Fi+j where n > 1 for i = 1, 2, 3, ... and j = 1, 2, 3, .... Proof: (Mathematical Induction on j) Step 1. Show that for j = 1, Fn Fn+1 − Fn−i F(n+1)+i = (−1)n+i Fi Fi+1 is true. Proof: (induction on i)

8

i. Show that it is true for i = 1, that is, Fn Fn+1 − Fn−1 F(n+1)+1 = (−1)n+1 F1 F1+1 = (−1)n+1 F1 F2 . Since Fn+1 = Fn + Fn−1 , Fn Fn+1 − Fn−1 Fn+2 = (Fn+1 − Fn−1 )Fn+1 − (Fn − Fn−2 )Fn+2 2 = Fn+1 − Fn−1 Fn+1 − Fn Fn+2 − Fn−2 Fn+2

(by Lemmas 1 and 2) 2 = (−1)n+1 F12 − Fn2 + Fn2 − (−1)n+2 F22 + Fn+1 − Fn−2 Fn+2

(by Lemma 1) = = = =

(−1)n+1 (F12 + F22 ) + (−1)n+2 F22 (−1)n+1 (F12 + F22 − F22 ) (−1)n+1 F12 (−1)n+1 F1 F2

ii. Assume that it is true for i = k, that is, Fn Fn+1 − Fn−k F(n+k)+1 = (−1)n+k Fk Fk+1 . iii. Show that it is true for n = k + 1, that is, Fn Fn+1 − Fn−(k+1) Fn+(k+1)+1 = (−1)n+(k+1) Fk+1 F(k+1)+1 Fn Fn+1 − Fn−k−1 Fn+k+2 = (−1)n+k+1 Fk+1 Fk+2 . Since Fn−k = Fn−k−1 + Fn−k−2 , Fn Fn+1 − Fn−k−1 Fn+k+2 = Fn Fn+1 − (Fn−k − Fn−k−2 )(Fn+k+1 + Fn+k ) = Fn Fn+1 − Fn−k Fn+k+1 − Fn−k Fn+k − Fn−k−2 Fn+k+2

(by inductive hypothesis) = (−1)n+k Fk Fk+1 − Fn−k Fn+k − Fn−k−2 Fn+k+2

9

(by Theorem 1) = = = = = = =

2 (−1)n+k Fk Fk+1 + (−1)n+k Fk2 − Fn2 + Fn2 − (−1)n+(k+2) Fk+2 2 ) (−1)n+k (Fk Fk+1 + Fk2 − Fk+2 n+k 2 (−1) [Fk (Fk + Fk+1 ) − Fk+2 ] 2 (−1)n+k (Fk Fk+2 − Fk+2 ) (−1)n+k [−Fk+2 (Fk+2 − Fk )] (−1)n+k (−Fk+2 Fk+1 ) (−1)n+k+1 Fk+2 Fk+1

Step 2. Assume that Fn Fn+k − Fn−i F(n+k)+i = (−1)n+i Fi Fi+k is true for j = k. Step 3. Show that t is true for j = k + 1, that is, Fn Fn+(k+1) − Fn−i Fn+(k+1)+i = (−1)n+i Fi Fi+(k+1) . Since Fn+k+1 = Fn+k + Fn+k−1 and Fn+i+k+1 = Fn+i+k Fn+i+k−1 , Fn Fn+(k+1) − Fn−i Fn+i+(k+1) = Fn (Fn+k + Fn+k−1 ) − Fn−i (Fn+i+k + Fn+i+k−1 ) = Fn Fn+k + Fn Fn+k−1 − Fn−i Fn+i+k − Fn−i Fn+i+k−1 = (Fn Fn+k − Fn−i Fn+i+k ) + (Fn Fn+k−1 − Fn−i Fn+i+k−1 )

(by inductive hypothesis) = (−1)n+i Fi Fi+k + Fn Fn+(k−1) − Fn−i Fn+i+(k−1)

(by inductive hypothesis) = = = =

(−1)n+i Fi Fi+k + (−1)n+i Fi Fi+(k−1) (−1)n+i (Fi Fi+k + Fi Fi+(k−1) ) (−1)n+i [Fi (Fi+k + Fi+(k−1) )] (−1)n+i Fi Fi+k+1

Therefore,Fn Fn+j − Fn−i Fn+(i+j) = (−1)n+i Fi Fi+j where n > 1 for i = 1, 2, 3, ... and j = 1, 2, 3, ....

10

Bibliogarphy [1] Bradley, Sean Generalized Fibonacci Sequence Mathematics Teachers, 93 (Oct. 2000), pp. 604-606. [2] Brown, Stephen I. and Marion I. Walter The Art of Problem Posing 2nd ed. Hillsdale, Lawrence Ealbaum Associates, 1993 [3] Ibe, Milagros D. Advanced Topics in Mathematics for Teachers University of the Philippines Open University, 1997 [4] Kelly, Lucille A. A Generalization of the Fibonacci Formulae Mathematics Teacher, 75 (Nov. 1982), pp.664-665. [5] Marasigan, Jose and Jose M. Bernales Proceedings 1994 Annual Convention, Mathematical Society of the Philippines, 18 (Jan. 1995) [6] Niven, Ivan and H. S. Zuckerman An Introductio to the Theory of Numbers John Wiley and Sons, 1980 [7] Shaw, Kenneth L. and L. Aspinwall The Recurring Fibonacci Sequence: Using a Poseand-Probe Rubric Mathematics Teacher, 92 (March 1999), pp. 192-196. [8] Stepelman, Posamentier. Teaching Secondary School Mathematics 2nd ed. A Bell and Howell Company, 1986 [9] Troutman, Andrea P. and Betty K. Lichtenberg. Mathematics a Good Beginning Brooks/Cole Publishing Compny, 1995 [10] Vorob’ev, Nikolai N. Fibonacci Numbers Blaisedell, 1961 [11] Wilson, Robin Introductory to Graph Theory 2nd ed. Academic Press, 1979

11