Exploring Fibonacci Numbers

Exploring Fibonacci Numbers 2015 1 Abstract This paper will illustrate a multitude of properties involving the Fibonacci and Lucas numbers. In an attempt to cover an array of different properties, this paper will include concepts from Calculus, Linear Algebra, and Number Theory. It will also include three distinct derivations of the Binet form for the nth Fibonacci number. To begin, a brief discussion of historical background is offered. 2 Historical Background Fibonacci was born around 1170 in Pisa, Italy. He is known throughout history by a few different nomenclatures, Leonardo Bonacci, Leonardo Pisano, Leonardo of Pisa, and most commonly Fibonacci. Below is an image of Fibonacci. 1 At the time of his birth, Pisa was a hub of trade and commerce. Fibonacci’s father, Guilielmo was a merchant and, as such, travelled throughout Mediterranean lands to conduct trade. Guilielmo brought his son with him to the northern coast of Africa in order to learn skills central to being a merchant. It was there that he was taught the Hindu-Arabic numbers, which are 1, 2, 3, 4, 5, 6, 7, 8, 9, 0. It is important to note that in Europe at the time, they solely used Roman numerals. As Fibonacci learned how to perform calculations with these foreign numbers, he integrated them into his business practices. Throughout many years of traveling as a merchant, Fibonacci grew to believe that the Hindu-Arabic numbers demonstrated superiority over Roman numerals in many ways. Motivated by this belief, he wrote Liber Abaci upon returning to Pisa. In it, Fibonacci introduced the Western world to the Hindu-Arabic numbers and elaborated on methods of calculations and example problems. Chapter twelve of Liber Abaci includes the famous “problem of the rabbits”, from which arises the Fibonacci numbers or sequence that he is so well-known for today. It is worth acknowledging that Fibonacci’s greatest contribution to mathematics was arguably influencing the switch in Europe from Roman numerals to Hindu-Arabic numbers. Interestingly, he is most commonly known today not for that reason but for the “Fibonacci numbers”, which he did not actually study in depth. Not until over 600 years after Fibonacci’s death did French mathematician, Eduard Lucas (1842-1891), take a closer look at the numbers that came from the problem of the rabbits. Lucas deemed the sequence worthy of study and named them the “Fibonacci numbers”. He also played around with changing the first numbers in the sequence, and gave us the “Lucas numbers”, which will be defined later in this paper [3]. Below is an image of Lucas. 2 3 Worldly Examples 3.1 The Problem of the Rabbits This problem revolves around breeding rabbits. It was first introduced in Fibonacci’s Liber Abaci. If a breeder begins with a pair of rabbits, male and female, how many pairs of rabbits will they have at the end of one year? To eliminate randomness, the problem follows three assumptions: 1. Each newborn pair, female and male, matures in one month then starts to breed. 2. A mature pair breeds at the beginning of each month, resulting in a newborn pair, female and male. 3. No rabbits die in the first year. Starting with one newborn pair, the distribution of rabbits for each month is as follows. Month Newborn Pairs Mature Pairs Total Pairs Jan 1 0 1 Feb 0 1 1 March 1 1 2 April 1 2 3 May 2 3 5 June 3 5 8 July 5 8 13 Aug 8 13 21 Sep 13 21 34 Oct 21 34 55 Nov 34 55 89 Dec 55 89 144 3 In any given month, the number of newborn pairs is equal to the number of mature pairs in the previous month, while the number of mature pairs is the number of total pairs in the previous month. Since total pairs is the sum of the newborn and mature pairs, then total pairs in a given month is the sum of the previous two total pairs. This leads us to the Fibonacci numbers [2]. 3.2 Honeybees Honeybees differ from rabbits becuase, for one, they can have either one or two parents. Explicitly, the males, or drones, have just one female parent. The females, either workers or queens, have two parents, one male and one female [6]. The Fibonacci numbers arise from the family tree of a single drone. Let the parent of the drone be “generation 1”, and let the grandparents be “generation 2”. Note that we are numbering the generations in the opposite way one would normally do so. Furthermore, denote the total females of a given generation n as en and the total males of generation n as mn . Then the number of males and females of the first six generations of a single drone’s lineage is given in the table below. n en mn 1 1 0 2 1 1 3 2 1 4 3 2 5 5 3 6 8 5 Since females have one parent of each sex, and males have a only one female parent, then explicitly, en+1 = en + mn and mn+1 = en . Then mn+2 = en+1 , and substitution yields mn+2 = mn+1 + mn . This recursive relationship is exactly that of the Fibonacci numbers [5]. 4 3.3 Climbing a Staircase This problem also reveals the Fibonacci numbers. The premise is a staircase with n stairs. Using either one or two stairs at a time, how many different ways are there to ascend (or descend) the stairs? Let Sn be the number of ways to climb the n stairs. Note that there are two different options to begin climbing, either climb one stair or two. After one stair, the number of different ways to climb the remaining stairs is Sn−1 . If instead we begin with two stairs, the number of different ways to climb the remaining stairs is Sn−2 [5]. Therefore the total number of ways to climb n stairs is given by Sn = Sn−1 + Sn−2 . This leads us to the definition of Fibonacci numbers. 4 The Recursive Definition To define the Fibonacci sequence, let fn denote the nth Fibonacci number. For n ≥ 0, we have 1. f0 = 0, f1 = 1 2. fn = fn−1 + fn−2 , n ≥ 2 Below is a table of the first 24 Fibonacci numbers. f0 = 0 f6 = 8 f12 = 144 f18 = 2584 f1 = 1 f7 = 13 f13 = 233 f19 = 4181 f2 = 1 f8 = 21 f14 = 377 f20 = 6765 f3 = 2 f9 = 34 f15 = 610 f21 = 10946 f4 = 3 f10 = 55 f16 = 987 f22 = 17711 f5 = 5 f11 = 89 f17 = 1597 f23 = 28657 5 5 Formula for fn : The Binet Form Any Fibonacci number can be found by adding the two numbers that preceded it in the sequence. However, say we want to find f43 . It is unlikely that we know f42 and f41 , and although finding them would be doable, it would also be cumbersome. It is therefore useful to define fn without using a recurrence relation, among other reasons. Binet √Form: Let α√and β be roots of the quadratic equation x2 = x + 1 such that α= 1+ 5 2 and β = 1− 5 2 . Then fn = αn − β n . α−β Since α and β are the roots of x2 = x + 1, some useful properties of α and β are: • αβ = −1 • α+β =1 • α2 = α + 1 • β2 = β + 1 Furthermore, lim n→∞ fn+1 = α, fn and α is known as the golden ratio. The proof of this last result is as follows. Proof. The Binet form for fn+1 and fn yields fn+1 αn+1 − β n+1 = . fn αn − β n Then since |β| < 1, it follows that lim β n+1 = lim β n = 0. n→∞ n→∞ Therefore, αn+1 αn+1 − β n+1 = lim = α. n→∞ n→∞ αn αn − β n lim 6 To see how the values α and β arise, here are three different derivations of the Binet form. 5.1 Recurrence Relation Suppose {an } is a sequence that satisfies an = an−1 + an−2 , n ≥ 2. Assume an = Arn , where A and r are nonzero constants. Substituting ai = Ari , the result is Arn = Arn−1 + Arn−2 . Dividing by A and rn−2 gives r2 − r − 1 = 0. Applying the quadratic formula yields r= −(−1) ± √ 1± 5 = . 2 Let α = √ 1+ 5 2 and β = p (−1)2 − 4(1)(−1) 2(1) √ 1− 5 2 . In place of {an }, use {fn }. Then for constants c1 and c2 , fn = c1 αn + c2 β n , n ≥ 0. Solving for c1 and c2 using initial values f0 and f1 yields 0 = f0 =c1 + c2 1 = f1 =c1 α + c2 β √  √    1+ 5 1− 5 + c2 . =c1 2 2 7 √1 5 Solving for c1 and c2 yields c1 = −1 √ . 5 and c2 = Therefore, fn can be expressed by 1 1 αn − β n fn = √ αn − √ β n = √ . 5 5 5 This concludes one proof of the Binet form. 5.2 Matrix Multiplication If fn represents the nth Fibonacci number, then " 1 1 #" # fn fn−1 1 0 " = fn+1 # . fn Letting " A= 1 1 # , 1 0 it will be shown that for n ≥ 0 " fn+1 # =A fn n " # 1 0 . To see this, note that " #" # 1 1 1 1 0 0 " = 1 1 #" # f1 1 0 f0 " #" # 1 1 f2 " = Then " # f3 f2 = 1 0 f1 = 1 1 1 0 " # f2 f1 . #2 " # 1 0 and so on. To help find An for any n requires eigenvalues and eigenvectors of matrix A. The determinant of the matrix " 1−λ 1 1 0−λ 8 # is equal to λ2 − λ − 1. Setting λ2 − λ − 1 ="0, #it follows " #that the eigenvalues are λ1 = α β α , respectively. Let and and λ2 = β with corresponding eigenvectors 1 1 " P = α β 1 # 1 , D= " # α 0 0 β . Then A = P DP −1 , and therefore An = P DP −1 P DP −1 . . . P DP −1 = P Dn P −1 . Now it is possible to solve for An : An = P Dn P −1    1 n α β α 0  α−β   = −1 1 1 0 βn α−β  −β α−β  α α−β       α β αn 0 1 −β 1     = α−β n 1 1 0 β −1 α     αn+1 − β n+1 αn − β n 1   = α−β αn − β n αn−1 + β n−1  Using the formula " # fn+1 fn =A " # n 1 0  fn = we get: 1 α−β  n α −β n  = αn − β n √ . 5 Thus, we can derive the Binet form using matrix multiplication. 9 5.3 Power Series Definition 5.1. Given a real number c and a sequence {ak }∞ k=0 of real numbers, the ex∞ P ak (x − c)k is called a power series centered at c. The numbers ak are the pression k=0 coefficients of the power series and the number c is the center of the power series [1]. Define a sequence of real numbers by a0 = 1, a1 = 1, and ak+1 = ak + ak−1 for all k ≥ 1. ∞ P ak xk for each value of x for which Note that ak = fk+1 . Define a function g by g(x) = k=0 the series converges. We first use induction to show that ak ≤ 2k for all k. Proof. For a base case, a0 = 1, 20 = 1 and 1 ≤ 1. Also for k = 1, we have a1 = 1, 21 = 2 and 1 ≤ 2. Now assume the inequality is true for n = 0, 1, . . . k. Then for k + 1, ak+1 = ak + ak−1 ≤ 2k + 2k−1 = (2 + 1)2k−1 = 3 · 2k−1 < 2k+1 . This shows that ak ≤ 2k for all k. Next will be another proof of the Binet form for fn . It will be shown that if r and s are roots of x2 + x − 1, then  1  ak = √ αk+1 − β k+1 5 for each integer k ≥ 0. First it will be shown that xg(x) + x2 g(x) = g(x) − 1 . 10 Using the fact that a0 = 1 = a1 , we have 2 xg(x) + x g(x) = x ∞ X k ak x + x 2 k=0 = = ∞ X ∞ X ak xk k=0 ak xk+1 + ∞ X k=0 k=0 ∞ X ∞ X ak−1 xk + k=1 ak xk+2 ak−2 xk k=2 = a0 x + = a1 x + ∞  X k=2 ∞ X  ak−1 + ak−2 xk ak xk k=2 = ∞ X ak xk k=1 = g(x) − 1. Then factoring xg(x) + x2 g(x) = g(x) − 1 yields g(x)(x + x2 − 1) = −1. Thus g(x) = x2 −1 . +x−1 Now let r and s be the roots of x2 + x − 1. We will use the quadratic formula to calculate values for r and s. The resulting roots of x2 + x − 1 are −1 − 2 √ 5 and −1 + 2 √ 5 . Without loss of generality, let −1 − r= 2 √ 5 −1 + s= 2 , 11 √ 5 . Note that √ √ 1 2 −1 + 5 1− 5 √ · √ = = =β r 2 −1 − 5 −1 + 5 and similarly √ 1 1+ 5 = =α. s 2 Using partial fractions, it will be shown that g(x) = −1 A B = + , (r − x)(s − x) r−x s−x where A and B are constants that depend on r and s. Multiplying to get a common denominator gives (s − x)A + (r − x)B −1 = 2 . (r − x)(s − x) x +x−1 Working with the numerator yields the system of equations sA + rB = −1 −A − B = 0 It follows that A = 1 r−s and B = −1 r−s . √ From here, it is straight forward to solve for A and B. Since r − s = − 5, it follows that A= 1 √ − 5 and 1 B=√ . 5 Recall that the formula for the sum of a geometric series of the form ∞ P a0 rk is k=0 S= a0 , 1−r where a0 is the first term and r is the common ratio. Therefore A r−x and B s−x can be rewritten as geometric sums by multiplying each by 1 in a helpful way. Explicitly, for |x| < |r|, and |x| < |s|, ∞ X 1/r A A/r A  x k · = = · . 1/r r − x 1 − x/r r r k=0 12 Similarly, ∞ X B B  x k = · . s−x s s k=0 It follows that  ∞ ∞ ∞  X A  x k X B  x k X B A g(x) = xk . + · + · = r r s s rk+1 sk+1 k=0 k=0 k=0 Then this is the Maclaurin series representation for g(x). Since the Maclaurin series representation is unique, then plugging in values for A, B, r and s yields 1 ak = √ 5 ! −β k+1 +α for each integer k ≥ 0. Since ak = fk+1 , we see that fk = αk − β k √ . 5 This concludes our final proof of the Binet form. 13 k+1 6 Properties The Fibonacci numbers have a myriad of interesting algebraic properties. Many such properties can be proven in more than one way, as with the Binet form alone. As demonstrated in this section, the recursive definition of the Fibonacci numbers lends itself well to proofs by induction. Property 6.1. For each positive integer n, f1 + f2 + · · · + fn = fn+2 − 1. Proof. This will be a proof by induction [4]. To establish a base case with n = 1, we have f1 = 1 and f3 − 1 = 2 − 1 = 1. Now, we assume the equation is true for n = 1, . . . , k and prove it true for k + 1. Using addition and our hypothesis, we get f1 + f2 + · · · + fk + fk+1 = fk+2 − 1 + fk+1 . By the recursive definition of the Fibonacci numbers, fk+1 +fk+2 −1 = fk+3 −1. Therefore, it is proven that the sum of the first n Fibonacci numbers is one less then fn+2 . Property 6.2. For each positive integer n, f1 + f3 + f5 + · · · + f2n−1 = f2n . Proof. This will be a proof by induction [4]. With n = 1 as our base case, we see that f1 = 1 = f2 . Now assume the conjecture is true for n = 1, . . . , k. If n = k + 1, then f1 + f3 + f5 + · · · + f2k−1 + f2(k+1)−1 = f2k + f2k+1 = f2k+2 = f2(k+1) . This proves that the sum of the first n odd numbered Fibonacci numbers is f2n . Alternatively, we can prove this property using the result from Property 6.1. Proof. By the recursive definition of the Fibonacci numbers, and since f1 = 1, then f1 + f3 + f5 + · · · + f2n−1 = f1 + (f1 + f2 ) + (f3 + f4 ) + · · · + (f2n−3 + f2n−2 ) = f1 + f(2n−2)+2 − 1 = f2n . 14 Property 6.3. For each positive integer n, f12 + f22 + · · · + fn2 = fn fn+1 . Proof. This will be a proof by induction [2]. When n = 1, f12 = 12 = 1 = f1 f2 . Now assume the equation is true for n = 1, . . . , k. Note that 2 2 f12 + · · · + fk+1 = f12 + · · · + fk2 + fk+1 2 = fk fk+1 + fk+1 = fk+1 (fk + fk+1 ) = fk+1 fk+2 . This proves that the sum of the squares of the first n Fibonacci numbers is equal to the product of the nth and the (n + 1)st Fibonacci numbers. Below is a geometric representation of this formula, in which the numbers represent the side length of each square: 2 . Property 6.4. For each positive integer n, f1 f2 + f2 f3 + · · · + f2n−1 f2n = f2n Proof. This will be a proof by induction [5]. For n = 1, we have f1 f2 = 1 = f22 . Now we assume the equation to be true for n = 1, . . . , k and we shall prove it true for k + 1. Using 15 the induction hypothesis, 2 f1 f2 + · · · + f2k+1 f2k+2 = f2k + f2k f2k+1 + f2k+1 f2k+2 2 = f2k + f2k f2k+1 + f2k+1 (f2k + f2k+1 ) 2 2 = f2k + 2f2k f2k+1 + f2k+1 = (f2k + f2k+1 )2 2 = f2k+2 . This shows that the sum of all products of consecutive Fibonacci numbers from 1 to 2n is the square of the 2nth Fibonacci number. Property 6.5. For each positive integer n, fn+1 fn−1 = fn2 + (−1)n . Proof. This will be a proof by induction [5]. When n = 1, f2 f0 = 0 and f12 + (−1)1 = 1 − 1 = 0. When n = 2, f3 f1 = 2 and f22 + (−1)2 = 1 + 1 = 2. Assume the equation is true for n = 1, . . . , k, where k > 2. Now if n = k + 1, we have fk+2 fk = (fk+1 + fk )fk = fk+1 fk + fk2 = fk+1 fk + fk+1 fk−1 − (−1)k = fk+1 (fk + fk−1 ) − (−1)k 2 = fk+1 + (−1)k+1 . This completes the proof. Property 6.6. For each integer n ≥ 2, fn+2 fn−2 = fn2 + (−1)n+1 . Proof. This will be a direct proof [5]. For n = 2, f4 f0 = 0 = f22 − 1. Let us also look at n = 3. We have f5 f1 = 5, and f32 + (−1)4 = 22 + 1 = 5. 16 Now assume the equation is true for some n ≥ 3. Using the result from Property 6.5, f(n+1)+2 f(n+1)−2 = fn+3 fn−1 = (fn+2 + fn+1 )(fn+1 − fn ) 2 = fn+2 fn+1 − fn+1 fn + fn+1 − fn+2 fn 2 2 = fn+1 (fn+2 − fn ) + fn+1 − (fn+1 + (−1)n+1 ) 2 2 2 = fn+1 + fn+1 − fn+1 − (−1)n+1 2 = fn+1 + (−1)n+2 This property will become useful later when looking at infinite series involving Fibonacci properties. Definition 6.1. Greatest Common Divisor If a and b are integers, then the greatest common divisor of a and b is the largest positive integer that divides both a and b. It is denoted gcd(a, b). Definition 6.2. Relatively Prime If a and b are integers such that gcd(a, b) = 1, then a and b are considered to be relatively prime. Lemma 6.7. If a and b are positive integers, and q and r are integers such that a = bq + r, then gcd(a, b) = gcd(b, r). Proof. Using substitution, we have gcd(a, b) = gcd(bq + r, b) = gcd(r, b). 17 Property 6.8. For each positive integer n, gcd(fn−1 , fn ) = 1. In words, any two consecutive Fibonacci numbers are relatively prime [2]. Proof. This will be a proof by induction on n. As a base case, note that gcd(f0 , f1 ) = gcd(0, 1) = 1. Now assume the conjecture is true for k. Then since fk+1 = fk +fk−1 and using Lemma 6.7 stated above, it follows that gcd(fk+1 , fk ) = gcd(fk , fk−1 ) = 1. This completes the proof. Therefore, every Fibonacci number is relatively prime to both its previous and subsequent Fibonacci number. This property can also be proven by contradiction. Such a proof will be left to the reader. Property 6.9. For each positive integer n, gcd(fn , fn+2 ) = 1. Proof. This will be a proof by contradiction [2]. Suppose that gcd(fn , fn+2 ) = d such that d > 1. Then by the recursive definition, we have fn+2 = fn+1 + fn , and since d|fn+2 and d|fn , then it follows that d|fn+1 . But this contradicts Property 6.8, which says that gcd(fn , fn+1 ) = 1. Therefore, gcd(fn , fn+2 ) = 1. Property 6.10. The sum of any six consecutive Fibonacci numbers is divisible by four [2]. 5 P fn+r = 4fn+4 . Explicitly, for each positive integer n, r=0 Proof. Using our recursive definition, we see that, 5 X fn+r = (fn + fn+1 ) + (fn+2 + fn+3 ) + (fn+4 + fn+5 ) r=0 = fn+2 + fn+4 + fn+4 + fn+5 = fn+2 + 2fn+4 + fn+3 + fn+4 = 4fn+4 . This shows that the sum of any six consecutive Fibonacci numbers is a multiple of four. 18 Property 6.11. The sum of any ten consecutive Fibonacci numbers is divisible by 11 [2]. 9 P Furthermore, for each positive integer n, fn+r = 11fn+6 . r=0 Proof. Similar to the previous property, we will rewrite the sum of an arbitrary ten consecutive Fibonacci numbers using the recursive definition. 9 X fn+r = (fn + fn+1 ) + (fn+2 + fn+3 ) + (fn+4 + fn+5 ) + fn+6 + fn+7 + fn+8 + fn+9 r=0 = fn+2 + fn+4 + fn+6 + fn+6 + (fn+5 + fn+6 ) + (fn+6 + fn+7 ) + (fn+7 + fn+8 ) = fn+2 + fn+4 + fn+5 + 4fn+6 + 2fn+5 + 2fn+6 + fn+6 + fn+7 = fn+2 + fn+4 + 4fn+5 + 8fn+6 = fn+2 + 3fn+5 + 9fn+6 = fn+2 + 3fn+3 + 3fn+4 + 9fn+6 = 2fn+3 + 4fn+4 + 9fn+6 = 2fn+4 + 2fn+5 + 9fn+6 = 11fn+6 This shows that the sum of any ten consecutive Fibonacci numbers is divisible by 11. n P Property 6.12. For each positive integer n, (−1)i+1 fi = (−1)n−1 fn−1 + 1. i=1 Proof. This will be a proof by induction [2]. When n = 1, we have (−1)2 f1 = 1 and (−1)0 f0 + 1 = 1. Now assume the equation is true for n = 1, . . . , k. Then k+1 X i=1 i+1 (−1) fi = k X (−1)i+1 fi + (−1)k+2 fk+1 i=1 = (−1)k−1 fk−1 + 1 + (−1)k fk+1 = (−1)k (fk+1 − fk−1 ) + 1 = (−1)k fk + 1. This completes the proof. 19 Property 6.13. For m ≥ 0 and n > 0, fm+n = fm+1 fn + fm fn−1 . Proof. First we fix m, then do a proof by induction on n [4]. For n = 1, we have fm+1 f1 + fm f0 = fm+1 . Now assume true for n = 1, . . . , k and prove true for n = k + 1. Then fm+1 fk+1 + fm fk = fm+1 (fk + fk−1 ) + fm (fk−1 + fk−2 ) = (fm+1 fk + fm fk−1 ) + (fm+1 fk−1 + fm fk−2 ) = fm+k + fm+k−1 = fm+k+1 . This completes the proof. Property 6.14. For all n ≥ 0, αn = αfn + fn−1 . Proof. To prove this we will use the Binet Form of fn and the fact that αβ = −1 and α + β = 1 [4]. αfn + fn−1 = = = = = α(αn − β n ) αn−1 − β n−1 √ √ + 5 5 n+1 n−1 n−1 α +β +α − β n−1 √ 5 αn+1 + αn−1 √ 5 n α (α + α1 ) √ 5 n α (α − β) √ 5 = αn . Property 6.15. For all n ≥ 0, β n = βfn + fn−1 . Proof. This is very similar to the previous proof, and as such shall be left out [4]. 20 7 Lucas Numbers The Lucas numbers are very similar to the Fibonacci number. Like the Fibonacci numbers, any number in the sequence is the sum of the previous two. The only difference, in fact, is the starting point. The formal recursive definition follows. Definition 7.1. For n ≥ 0, we have 1. `0 = 2, `2 = 1 2. `n = `n−1 + `n−2 , n ≥ 2 Below is a list of the first 24 Lucas numbers. `0 = 2 `6 = 18 `12 = 322 `18 = 5778 `1 = 1 `7 = 29 `13 = 521 `19 = 9349 `2 = 3 `8 = 47 `14 = 843 `20 = 15127 `3 = 4 `9 = 76 `15 = 1364 `21 = 24476 `4 = 7 `10 = 123 `16 = 2207 `22 = 39603 `5 = 11 `11 = 199 `17 = 3571 `23 = 64079 The Lucas numbers also have a nice formula for the nth Lucas numbers. The Binet form for the Lucas numbers is given below. Binet Form: For n ≥ 0, `n = αn + β n . Proof. This will be a proof by induction. As a base case, let n = 1: `1 = 1 = α + β. Then assume the formula is true for n = 1, . . . , k, where k > 1. Using the fact that 21 α2 = α + 1 and β 2 = β + 1, the following holds true: `k+1 = `k + `k+1 = αk + β k + αk−1 + β k−1 = αk−1 (α + 1) + β k−1 (β + 1) = αk−1 (α2 ) + β k−1 (β 2 ) = αk+1 + β k+1 . This shows that the nth Lucas number is the sum of αn and β n . 7.1 Properties of Lucas Numbers Property 7.1. For each positive integer n, `1 + `2 + · · · + `n = `n+2 − 3 . Proof. This proof will be left to the reader. It is smilar to that of Property 6.1 [4]. Property 7.2. For each positive integer n, `2 + `4 + `6 + · · · + `2n = `2n+1 − 1 [4]. Proof. Using Property 7.1, we have `2 + `4 + `6 + · · · + `2n = (`0 + `1 ) + (`2 + `3 ) + · · · + (`2n−2 + `2n−1 ) = 2 + `(2n−1)+2 − 3 = `2n+1 − 1. This completes the proof. Property 7.3. For each positive integer n, `1 + `3 + `5 + · · · + `2n−1 = `2n−2 − 2 [4]. Proof. This can be proven by induction or by using Property 7.1. Both will be left to the reader. 22 Property 7.4. For each positive integer n, `2n − 2(−1)n = `2n [2]. Proof. Using the Binet form of `n and the fact that αβ = −1, we get `2n − 2(−1)n = (αn + β n )2 − 2(−1)n = α2n + 2αn β n + β 2n − 2(−1)n = α2n + 2(−1)n + β 2n − 2(−1)n = α2n + β 2n = `2n . This completes the proof. 8 Properties Involving both Fibonacci and Lucas Numbers Below are various properties that encompass Fibonacci and Lucas numbers together. Property 8.1. For each positive integer n, fn+1 + fn−1 = `n . Proof. This will be a proof by induction [2]. When n = 1, we have f2 + f0 = 1 + 0 = 1 and `1 = 1. Now assume the equation is true for n = 1, . . . , k and prove it true for n = k + 1. Using the recursive definition, we get fk+2 + fk = fk + fk+1 + fk−2 + fk−1 = (fk + fk−2 ) + (fk+1 + fk−1 ) = `k−1 + `k = `k+1 . This completes the proof. Alternatively, this property can be proven using the Binet forms. Such a proof will be left to the reader. 23 Property 8.2. For each positive integer n, `n+1 + `n−1 = 5fn [2]. Proof. Using the previous result, we find that `n+1 + `n−1 = (fn+2 + fn ) + (fn + fn−2 ) = fn + fn+1 + 2fn + fn−2 = 3fn + fn + fn−1 + fn−2 = 5fn . This completes the proof. Property 8.3. For each positive integer m and n, `m+1 fn + `m fn−1 = `m+n . Proof. We fix m and prove this by induction on n [4]. When n = 1, `m+1 f1 + `m f0 = `m+1 . Now assume true for n = 1, . . . , k and prove true for n = k + 1. Then `m+1 fk+1 + `m fk = `m+1 fk + `m+1 fk−1 + `m fk−1 + `m fk−2 = `m+k + `m+k−1 = `m+k+1 . This completes the proof. Property 8.4. For each positive integer n, `m+1 `n + `m `n−1 = 5fm+n . Proof. We fix m and prove by induction on n [4]. From Property 8.2 we know that `n+1 + `n−1 = 5fn . When n = 1, we have `m+1 `1 + `m `0 = `m+1 + 2`m = `m+2 + `m = 5fm+1 . Now we assume the hypothesis is true for n = 1, . . . , k and prove it true for n = k + 1. 24 Then `m+1 `k+1 + `m `k = `m+1 `k−1 + `m+1 `k + `m `k−2 + `m `k−1 = 5fm+k−1 + 5fm+k = 5fm+k+1 . This completes the proof. Property 8.5. For each positive integer n, fn `n = f2n [2]. Proof. Using the Binet forms of fn and `n , we find that fn `n = αn − β n n α2n − β 2n √ √ (α + β n ) = = f2n . 5 5 Thus, the product of the nth Fibonacci and n Lucas numbers is f2n . 9 Divisibility Properties and Consequences This section will delve into interesting properties regarding divisibility. First, it will be shown that for nonnegative integers n and k, fn divides fkn . Proof. It was shown in Property 6.13 that for m ≥ 0 and n ≥ 1, fm+n = fm+1 fn + fm fn−1 . To prove that fn divides fkn for k ≥ 1, it is necessary to fix n and perform induction on k. First, if m = n ≥ 1, then f2n = fn+n = fn+1 fn + fn fn−1 = fn (fn+1 + fn−1 ). 25 Thus fn divides f2n , for m ≥ 1. Also f3n = fn+2n = fn+1 f2n + fn f2n−1 . Since fn divides f2n , then for n ≥ 1, fn divides f3n . Now assume that fn |fkn for k = 1, . . . j − 1. For n ≥ 1, j ≥ 1, fjn = fn+(j−1)n = fn+1 f(j−1)n + fn f(j−1)n−1 . Since fn divides f(j−1)n and fn divides fn , then fn must divide fjn . This proves that for all k > 0 fn divides fkn . Next is in interesting property regarding greatest common divisors. It will be shown that gcd(fm , fn ) = fgcd(m,n) . For example, if m = 14 and n = 21, then gcd(f14 , f21 ) = gcd(377, 10946) = 13 and fgcd(14,21) = f7 = 13. This proof requires four lemmas, two of which are Property 6.8 and Property 6.13. Lemma 9.1. For integers n and m, gcd(m, n) = gcd(m, n ± m). Proof. If q is a divisor of both m and n, then there exist integers s and t such that m = qt and n = qs. Then m ± n = qt ± qs, and therefore q is a factor of m ± n. Since this is true for any divisor of both m and n, it is true for the greatest common divisor. Now, if q is a divisor of both m and m ± n, then there exist integers s and t such that m = qt and m ± n = qs. Then since q divides both m and qs, q must divide n. This 26 completes the proof. Theorem 9.2. For nonnegative integers m and n, gcd(fm , fn ) = fgcd(m,n) . Proof. Let n = mk + r, where 0 ≤ r < m. By Property 6.13, fn = fmk+1 fr + fmk fr−1 . Therefore gcd(fm , fn ) = gcd(fm , fmk+1 fr + fmk fr−1 ) Since fm divides fkm , then gcd(fm , fmk+1 fr + fmk fr−1 ) = gcd(fm , fmk+1 fr ). Then since gcd(fm , fmk+1 ) = 1, we have gcd(fm , fmk+1 fr ) = gcd(fm , fr ). Notice that the subscripts of the Fibonacci numbers form a step in the Euclidean algorithm [5]. This shows that the Euclidean algorithm for Fibonacci numbers fm and fn goes parallel with the Euclidean algorithm for integers m and n. Therefore, if the algorithm outputs the greatest common divisor of m and n to s, or gcd(m, n) = s, then we also get gcd(fm , fn ) = fs = fgcd(m,n) . 27 10 Infinite Series An infinite series is an expression of the form ∞ X ak = a1 + a2 + a3 + a4 + · · · . k=1 The partial sums of a series are given by sn = a1 + a2 + · · · + an = n X ak . k=1 ∞ P Definition 10.1. An infinite series ak converges if its corresponding sequence sn k=1 of partial sums converges. If S is the limit of the sequence {sn }, then the series converges to S. We write ∞ P ∞ P ak k=1 ak = S and refer to S as the sum of the series [1]. k=1 Property 10.1. ∞ X k=1 1 1 = 2. f2k f2k+2 α Proof. First, it will be shown that the partial sums sn are equal to proof by induction on n. As a base case, when n = 1, then 1 X k=1 1 1 = f2k f2k+2 f2 f4 1 3 f2 = . f4 = 28 f2n f2n+2 . This will be a Now assume the conjecture is true for n = 1, . . . , j. Then using Property 6.6, j+1 X k=1 f2j 1 1 + = f2k f2k+2 f2j+2 f2j+2 f2j+4 = = f2j+4 f2j + 1 f2j+2 f2j+4 2 f2(j+1) + (−1)2(j+1)+1 + 1 f2j+2 f2j+4 = 2 f2j+2 −1+1 f2j+2 f2j+4 = f2j+2 . f2j+4 Therefore, sn = f2n f2n+2 . Now to find the value of the infinite sum, it is necessary to take the limit of the partial sum sn as n goes to infinity. Using the Binet form for fn and the fact that α2 = α + 1, 29 β 2 = β + 1 and αβ = −1, we get sn = = f2n f2n+2 α2n − β 2n α2n+2 − β 2n+2 α2n −  −1 α α2n+2 −  −1 α = = As n approaches infinity, both 1 α2n 2n 2n+2 1 α2n 1 α2 α2n − α2n+2 α2n − and 1 α2n+2 . go to zero. Therefore, lim sn = n→∞ 1 . α2 . This is just one example of Fibonacci numbers in infinite series. Furthermore, the properties included in this paper are a small proportion of those that apply to the Fibonacci numbers. These numbers arise in so many different capacities that they are beloved by many. As such, the Fibonacci Association was incorporated in 1963. Their primary publication is titled The Fibonacci Quarterly. 30 References [1] Gordon, R. Real Analysis: A First Course. Addison-Wesley, Reading, MA, 2nd ed., 2002. [2] Grimaldi, R. Fibonacci and Catalan Numbers: An Introduction. Wiley, Hoboken, NJ, 2012. [3] Posamentier, A and Lehmann, L. The Fabulous Fibonacci Numbers. Prometheus Books, Amherst, NY, 2007. [4] Robbins, N. Beginning Number Theory. Jones and Bartlett, Burlington, MA, 2nd ed., 2006. [5] Vajda, S. Fibonacci and Lucas Numbers, and the Golden Section: Theory and Applications. Dover, Mineola, NY, 1989. [6] “The Colony and its Organization”. MAAREC Mid Atlantic Apiculture Research Extension Consortium RSS. 10 May 2010. Web. 17 May 2015. 31