Fibonacci Numbers And The Golden Ratio
Fibonacci Numbers and theGolden RatioLecture Notes forJeffrey R. Chasnov
The Hong Kong University of Science and TechnologyDepartment of MathematicsClear Water Bay, KowloonHong Kongc 2016-2019 by Jeffrey Robert ChasnovCopyright This work is licensed under the Creative Commons Attribution 3.0 Hong Kong License. To view a copy of thislicense, visit http://creativecommons.org/licenses/by/3.0/hk/ or send a letter to Creative Commons, 171 SecondStreet, Suite 300, San Francisco, California, 94105, USA.
PrefaceView the promotional video on YouTubeThese are my lecture notes for my online Coursera course, Fibonacci Numbers and the Golden Ratio.These lecture notes are divided into chapters called Lectures, and each Lecture corresponds to a videoon Coursera. I have also uploaded the Coursera videos to YouTube, and links are placed at the top ofeach Lecture.Most of the Lectures also contain problems for students to solve. Less experienced students mayfind some of these problems difficult. Do not despair! The Lectures can be read and watched, and thematerial understood and enjoyed without actually solving any problems. But mathematicians do liketo solve problems and I have selected those that I found to be interesting. Try some of them, but if youget stuck, full solutions can be read in the Appendix.My aim in writing these lecture notes was to place the mathematics at the level of an advancedhigh school student. Proof by mathematical induction and matrices, however, may be unfamiliar toa typical high school student and I have provided a short and hopefully readable discussion of thesetopics in the Appendix. Although all the material presented here can be considered elementary, Isuspect that some, if not most, of the material may be unfamiliar to even professional mathematicianssince Fibonacci numbers and the golden ratio are topics not usually covered in a University course. SoI welcome both young and old, novice and experienced mathematicians to peruse these lecture notes,watch my lecture videos, solve some problems, and enjoy the wonders of the Fibonacci sequence andthe golden ratio.For your interest, here are the links to my other online courses. If you are studying differentialequations, you may want to browseDifferential Equations for EngineersIf your interests are matrices and elementary linear algebra, have a look atMatrix Algebra for EngineersAnd for a course on multivariable calculus, tryVector Calculus for Engineersiii
ContentsIFibonacci: It’s as Easy as 1, 1, 2, 311The Fibonacci sequence52The Fibonacci sequence redux7Practice quiz: The Fibonacci numbers93The golden ratio114Fibonacci numbers and the golden ratio135Binet’s formula15Practice quiz: The golden ratio19IIIdentities, Sums and Rectangles216The Fibonacci Q-matrix257Cassini’s identity298The Fibonacci bamboozlement31Practice quiz: The Fibonacci bamboozlement35Sum of Fibonacci numbers37910 Sum of Fibonacci numbers squared39Practice quiz: Fibonacci sums4111 The golden rectangle4312 Spiraling squares45III49The Most Irrational Number13 The golden spiral53v
CONTENTSvi14 An inner golden rectangle5715 The Fibonacci spiral61Practice quiz: Spirals6316 Fibonacci numbers in nature6517 Continued fractions6718 The golden angle7119 The growth of a sunflower75Practice quiz: Fibonacci numbers in nature77Appendix78A Mathematical induction81B Matrix algebra83B.1 Addition and Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .83B.2 Determinants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .84C Problem and practice quiz solutions87
Part IFibonacci: It’s as Easy as 1, 1, 2, 31
3In this week’s lectures, we learn about the Fibonacci numbers, the golden ratio, and their relationship.We conclude the week by deriving the celebrated Binet’s formula, an explicit formula for the Fibonaccinumbers in terms of powers of the golden ratio and its reciprical.
4
Lecture 1The Fibonacci sequenceView this lecture on YouTubeFibonacci published in the year 1202 his now famous rabbit puzzle:A man put a male-female pair of newly born rabbits in a field. Rabbits take a month tomature before mating. One month after mating, females give birth to one male-female pairand then mate again. No rabbits die. How many rabbit pairs are there after one year?To solve, we construct Table 1.1. At the start of each month, the number of juvenile pairs, adultpairs, and total number of pairs are shown. At the start of January, one pair of juvenile rabbits isintroduced into the population. At the start of February, this pair of rabbits has matured. At the startof March, this pair has given birth to a new pair of juvenile rabbits. And so able 1.1: Fibonacci’s rabbit population.We define the Fibonacci numbers Fn to be the total number of rabbit pairs at the start of the nthmonth. The number of rabbits pairs at the start of the 13th month, F13 233, can be taken as thesolution to Fibonacci’s puzzle.Further examination of the Fibonacci numbers listed in Table 1.1, reveals that these numbers satisfythe recursion relationFn 1 Fn Fn 1 .(1.1)This recursion relation gives the next Fibonacci number as the sum of the preceeding two numbers.To start the recursion, we need to specify F1 and F2 . In Fibonacci’s rabbit problem, the initial monthstarts with only one rabbit pair so that F1 1. And this initial rabbit pair is newborn and takes onemonth to mature before mating so F2 1.The first few Fibonacci numbers, read from the table, are given by1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, . . .and has become one of the most famous sequences in mathematics.5
LECTURE 1. THE FIBONACCI SEQUENCE6Problems for Lecture 11. The Fibonacci numbers can be extended to zero and negative indices using the relation Fn Fn 2 Fn 1 . Determine F0 and find a general formula for F n in terms of Fn . Prove your result usingmathematical induction.2. The Lucas numbers are closely related to the Fibonacci numbers and satisfy the same recursionrelation Ln 1 Ln Ln 1 , but with starting values L1 1 and L2 3. Determine the first 12 Lucasnumbers.3. The generalized Fibonacci sequence satisfies f n 1 f n f n 1 with starting values f 1 p andf 2 q. Using mathematical induction, prove thatf n 2 Fn p Fn 1 q.(1.2)Ln Fn 1 Fn 1 .(1.3)4. Prove that5. Prove thatFn 1 L n 1 ) .(L5 n 16. The generating function for the Fibonacci sequence is given by the power series f (x) Fn xn .n 1Assuming the power series converges, prove thatf (x) Solutions to the Problemsx.1 x x2
Lecture 2The Fibonacci sequence reduxView this lecture on YouTubeWe can solve another puzzle that also leads to the Fibonacci sequence:How many ways can one climb a staircase with n steps, taking one or two steps at a time?Any single climb can be represented by a string of ones and twos which sum to n. We define an asthe number of different strings that sum to n. In Table 1, we list the possible strings for the first fivevalues of n. It appears that the an ’s form the beginning of the Fibonacci sequence.To derive a relationship between an and the Fibonacci numbers, consider the set of strings that sumto n. This set may be divided into two nonoverlapping subsets: those strings that start with one andthose strings that start with two. For the subset of strings that start with one, the remaining part of thestring must sum to n 1; for the subset of strings that start with two, the remaining part of the stringmust sum to n 2. Therefore, the number of strings that sum to n is equal to the number of stringsthat sum to n 1 plus the number of strings that sum to n 2. The number of strings that sum ton 1 is given by an 1 and the number of strings that sum to n 2 is given by an 2 , so thata n a n 1 a n 2 .And from the table we have a1 1 F2 and a2 2 F3 , so that an Fn 1 for all positive integers n.n12345strings111, 2111, 12, 211111, 112, 121, 211, 2211111, 1112, 1121, 1211, 2111, 122, 212, 221an12358Table 2.1: Strings of ones and twos that add up to n.7
LECTURE 2. THE FIBONACCI SEQUENCE REDUX8Problems for Lecture 21. Consider a string consisting of the first n natural numbers, 123 . . . n. For each number in the string,allow it to either stay fixed or change places with one of its neighbors. Define an to be the number ofdifferent strings that can be formed. Examples for the first four values of n are shown in Table 2.2.Prove that an Fn 1 .n1234strings112, 21123, 132, 2131234, 1243, 1324, 2134, 2143an1235Table 2.2: Strings of natural numbers obtained by allowing a number to stay fixed or change placeswith its neighbor.2. Consider a problem similar to that above, but now allow the first 1 to change places with the lastn, as if the string lies on a circle. Suppose n 3, and define bn as the number of different strings thatcan be formed. Show that bn Ln , where Ln is the nth Lucas number.Solutions to the Problems
Practice quiz: The Fibonacci numbers1. In Fibonacci’s rabbit problem, the number of adult rabbit pairs in the fifth month isa) 1b) 2c) 3d) 52. The Fibonacci number denoted as F 5 isa) -8b) -5c) 5d) 83. Which of the following statements are true:A. Ln Fn 2 3Fn 1B. Ln Fn 1 Fn 1a) A onlyb) B onlyc) Both A and Bd) Neither A nor BSolutions to the Practice quiz9
10LECTURE 2. THE FIBONACCI SEQUENCE REDUX
Lecture 3The golden ratioView this lecture on YouTubeyxFigure 3.1: The golden ratio satisfies x/y ( x y)/x.We now present the classical definition of the golden ratio. Referring to Fig. 3.1, two positive numbersx and y, with x y are said to be in the golden ratio if the ratio between the larger number and thesmaller number is the same as the ratio between their sum and the larger number, that is,x yx .yx(3.1)Denoting Φ x/y to be the golden ratio, (Φ is the capital Greek letter Phi), the relation (3.1) becomesΦ 1 1,Φ(3.2)or equivalently Φ is the positive root of the quadratic equationΦ2 Φ 1 0.(3.3)Straightforward application of the quadratic formula results in Φ 5 1 1.618.2The negative of the negative root of the quadratic equation (3.3) is what we will call the golden ratioconjugate φ, (the small Greek letter phi), and is equal to φ 5 1 0.618.2The relationship between the golden ratio conjugate φ and the golden ratio Φ, is given byφ Φ 1,or using (3.2),φ 1.Φ11
LECTURE 3. THE GOLDEN RATIO12Problems for Lecture 31. The golden ratio Φ and the golden ratio conjugate φ can be defined as Φ 5 1,2 φ 5 1.2From these definitions, prove the following identities by direct calculation:(a) φ Φ 1,(b) φ 1/Φ,(c) Φ2 Φ 1,(d) φ2 φ 1,2. Prove that the golden ratio satisfies the Fibonacci-like relationshipΦ n 1 Φ n Φ n 1 .3. Prove that the golden ratio conjugate satisfiesφ n 1 φ n φ n 1 .Solutions to the Problems
Lecture 4Fibonacci numbers and the goldenratioView this lecture on YouTubeThe recursion relation for the Fibonacci numbers is given byFn 1 Fn Fn 1 .Dividing by Fn yieldsFn 1F 1 n 1 .FnFn(4.1)We assume that the ratio of two consecutive Fibonacci numbers approaches a limit as n . Definelimn Fn 1 /Fn α so that limn Fn 1 /Fn 1/α. Taking the limit, (4.1) becomes α 1 1/α, thesame identity satisfied by the golden ratio. Therefore, if the limit exists, the ratio of two consecutiveFibonacci numbers must approach the golden ratio for large n, that is,limn Fn 1 Φ.FnThe ratio of consecutive Fibonacci numbers and this ratio minus the golden ratio is shown in Table4.1. The last column appears to be approaching zero.n12345678910Fn 1 61.6182Fn 1 /Fn Φ 0.61800.3820 0.11800.0486 0.01800.0070 0.00260.0010 0.00040.0001Table 4.1: Ratio of consecutive Fibonacci numbers approaches Φ.13
14LECTURE 4. FIBONACCI NUMBERS AND THE GOLDEN RATIOProblems for Lecture 41. Assuming limn Fn 1 /Fn Φ, prove thatlimk Fk n Φn .Fk2. Using Φ2 Φ 1, prove by mathematical induction the following linearization of powers of thegolden ratio:Φn Fn Φ Fn 1 ,(4.2)where n is a positive integer and F0 0.3. Using φ2 φ 1, prove by mathematical induction the following linearization of powers of thegolden ratio conjugate:( φ)n Fn φ Fn 1 ,where n is a positive integer and F0 0.Solutions to the Problems(4.3)
Lecture 5Binet’s formulaView this lecture on YouTubeThe Fibonacci numbers are uniquely determined from their recursion relation,Fn 1 Fn Fn 1 ,(5.1)and the initial values, F1 F2 1. An explicit formula for the Fibonacci numbers can be found, andis called Binet’s Formula.To solve (5.1) for the Fibonacci numbers, we first look at the equationx n 1 x n x n 1 .(5.2)This equation is called a second-order, linear, homogeneous difference equation with constant coefficients, and its method of solution closely follows that of the analogous differential equation. The ideais to guess the general form of a solution, find two such solutions, and then multiply these solutionsby unknown constants and add them. This results in a general solution to (5.2), and one can then solve(5.1) by satisfying the specified initial values.To begin, we guess the form of the solution to (5.2) asxn λn ,(5.3)where λ is an unknown constant. Substitution of this guess into (5.2) results inλ n 1 λ n λ n 1 ,or upon division by λn 1 and rearrangement of terms,λ2 λ 1 0.Use of the quadratic formula yields two roots, both of which are already familiar. We have 1 5 Φ,λ1 2 1 5λ2 φ,2where Φ is the golden ratio and φ is the golden ratio conjugate.We have thus found two independent solutions to (5.2) of the form (5.3), and we can now use thesetwo solutions to find a solution to (5.1). Multiplying the solutions by constants and adding them, we15
LECTURE 5. BINET’S FORMULA16obtainFn c1 Φn c2 ( φ)n ,(5.4)which must satisfy the initial values F1 1 and F2 1. The algebra for finding the unknown constantscan be made simpler, however, if instead of F2 , we use the value F0 F2 F1 0.Application of the values for F0 and F1 results in the system of equations given byc1 c2 0,c1 Φ c2 φ 1.We use the first equation to write c2 c1 , and substitute into the second equation to getc1 (Φ φ) 1.Since Φ φ 5, we can solve for c1 and c2 to obtain c1 1/ 5, c2 1/ 5.(5.5)Using (5.5) in (5.4) then derives the surprising formulaFn known as Binet’s formula.Φn ( φ)n ,5(5.6)
17Problems for Lecture 51. Prove Binet’s formula (5.6) by mathematical induction.2. Use Binet’s formula to prove the limitlim Fn 1 /Fn Φ.n 3. Use the linearization formulasΦn Fn Φ Fn 1n( φ) Fn φ Fn 1(5.7)(5.8)to derive Binet’s formula.4. Use the generating function for the Fibonacci sequence x Fn xn 1 x x2n 1to derive Binet’s formula.5. Determine the analogue to Binet’s formula for the Lucas numbers, defined asL n 1 L n L n 1with the initial values L1 1 and L2 3. Again it will be simpler to define the value of L0 and use itand L1 as the initial values.6. Use Binet’s formula for Fn and the analogous formula for Ln to show that Ln 5FnΦ .2nSolutions to the Problems
18LECTURE 5. BINET’S FORMULA
Practice quiz: The golden ratio1. Define the golden ratio Φ and the golden ratio conjugate φ by Φ 5 1,2 φ 5 1.2Select all that are true.a) φ Φ 1b) Φ 1/φc) φ2 φ 1d) Φ2 Φ 12. The analogue to Binet’s formula for the Lucas numbers is given bya) Ln Φn ( φ)nb) Ln Φn ( φ)n 5c) Ln Φn ( φ)n 5d) Ln Φn ( φ)n3. Select all that are true.a) Φn Fn Φ Fn 1b) Φn Fn Φ Fn 1c) φn Fn φ Fn 1d) ( φ)n Fn φ Fn 1Solutions to the Practice quiz19
20LECTURE 5. BINET’S FORMULA
Part IIIdentities, Sums and Rectangles21
23In this week’s lectures, we learn about the Fibonacci Q-matrix and Cassini’s identity. Cassini’s identityis the basis for a famous dissection fallacy colorfully named the Fibonacci bamboozlement. A dissection fallacy is an apparent paradox arising from two arrangements of different area from one set ofpuzzle pieces. We also derive formulas for the sum of the first n Fibonacci numbers, and the sum ofthe first n Fibonacci numbers squared. Finally, we show how to construct a golden rectangle, and howthis leads to the beautiful image of spiraling squares.
24
Lecture 6The Fibonacci Q-matrixView this lecture on S1321O2134N3455D5589J89144Table 6.1: Fibonacci’s rabbit population consists of juveniles and adults.Consider again Fibonacci’s growing rabbit population of juvenile and adult rabbit pairs shown inTable 6.1. Let an denote the number of adult rabbit pairs at the start of month n, and let bn denote thenumber of juvenile rabbit pairs. The number of adult pairs at the start of month n 1 is just the sumof the number of adult and juvenile pairs at the start of month n. The number of juvenile pairs at thestart of month n 1 is just the number of adult pairs at the start of month n. This can be written as asystem of recursion relations given bya n 1 a n bn ,bn 1 a n ;or in matrix form asa n 1! bn 11110!an!bn.(6.1)The matrix in (6.1) is called the Fibonacci Q-matrix, defined asQ 1110!.(6.2)Repeated multiplication by Q advances the population additional months. For example, advancing kmonths is achieved byan k!bn k Qkan!bn.Powers of the Q-matrix are related to the Fibonacci sequence. Observe what happens when wemultiply an arbitrary matrix by Q. We have1110!abcd! a cb dab!.Multiplication of a matrix by Q replaces the first row of the matrix by the sum of the first and second25
LECTURE 6. THE FIBONACCI Q-MATRIX26rows, and the second row of the matrix by the first row.If we rewrite Q itself in terms of the Fibonacci numbers asQ F2F1F1F0!,and then make use of the Fibonacci recursion relation, we find2Q 11101110!F2F1F1F0F3F2F2F1! F3F2F2F1F4F3F3F2!.In a similar fashion, Q3 is given by3Q !! !,and so on. The self-evident pattern can be seen to benQ Fn 1FnFnFn 1!.(6.3)
27Problems for Lecture 61. Prove (6.3) by mathematical induction.2. Using the relation Qn Qm Qn m , prove the Fibonacci addition formulaFn m Fn 1 Fm Fn Fm 1 .(6.4)3. Use the Fibonacci addition formula to prove the Fibonacci double angle formulasF2n 1 Fn2 1 Fn2 ,F2n Fn ( Fn 1 Fn 1 ) .4. Show thatF2n Ln Fn .Solutions to the Problems(6.5)
28LECTURE 6. THE FIBONACCI Q-MATRIX
Lecture 7Cassini’s identityView this lecture on YouTubeLast lecture’s result for the Fibonacci Q-matrix is given bynQ Fn 1FnFnFn 1withQ 1110!,(7.1)!.(7.2)From the theory of matrices and determinants (see Appendix B), we know thatdet AB det A det B.Repeated application of this result yieldsdet Qn (det Q)n .(7.3)Applying (7.3) to (7.1) and (7.2) results directly in Cassini’s identity (1680),Fn 1 Fn 1 Fn2 ( 1)n .(7.4)Examples of this equality can be obtained from the first few numbers of the Fibonacci sequence1, 1, 2, 3, 5, 8, 13, 21, 34, . . . . We have2 5 32 1,3 8 52 1,5 13 82 1,8 21 132 113 34 212 1.Cassini’s identity is the basis of an amusing dissection fallacy, called the Fibonacci bamboozlement,discussed in the next lecture.29
LECTURE 7. CASSINI’S IDENTITY30Problems for Lecture 71. Prove Cassini’s identity by mathematical induction.2. Using the Cassini’s identity (7.4) and the Fibonacci addition formula (6.4), prove Catalan’s identityFn2 Fn r Fn r ( 1)n r Fr2 .Solutions to the Problems(7.5)
Lecture 8The Fibonacci bamboozlementView this lecture on YouTubeCassini’s identityFn 1 Fn 1 Fn2 ( 1)ncan be interpreted geometrically: Fn 1 Fn 1 is the area of a rectangle of side lengths Fn 1 and Fn 1 ,and Fn2 is the area of a square of side length Fn . Cassini’s identity states that the absolute difference inarea between th
The golden ratio View this lecture on YouTube x y Figure 3.1: The golden ratio satisfies x/y (x y)/x. We now present the classical definition of the golden ratio. Referring to Fig.3.1, two positive numbers x and y, with x y are said to be in the golden
Silat is a combative art of self-defense and survival rooted from Matay archipelago. It was traced at thé early of Langkasuka Kingdom (2nd century CE) till thé reign of Melaka (Malaysia) Sultanate era (13th century). Silat has now evolved to become part of social culture and tradition with thé appearance of a fine physical and spiritual .
May 02, 2018 · D. Program Evaluation ͟The organization has provided a description of the framework for how each program will be evaluated. The framework should include all the elements below: ͟The evaluation methods are cost-effective for the organization ͟Quantitative and qualitative data is being collected (at Basics tier, data collection must have begun)
̶The leading indicator of employee engagement is based on the quality of the relationship between employee and supervisor Empower your managers! ̶Help them understand the impact on the organization ̶Share important changes, plan options, tasks, and deadlines ̶Provide key messages and talking points ̶Prepare them to answer employee questions
Dr. Sunita Bharatwal** Dr. Pawan Garga*** Abstract Customer satisfaction is derived from thè functionalities and values, a product or Service can provide. The current study aims to segregate thè dimensions of ordine Service quality and gather insights on its impact on web shopping. The trends of purchases have
On an exceptional basis, Member States may request UNESCO to provide thé candidates with access to thé platform so they can complète thé form by themselves. Thèse requests must be addressed to esd rize unesco. or by 15 A ril 2021 UNESCO will provide thé nomineewith accessto thé platform via their émail address.
The Fibonacci-based numeral framework N(Fm, {0, 1}) is the numeral framework that utilizes Fibonacci arrangement as the premise. The meaning of the Fibonacci grouping [3] is given in Eq. 2. A number v is spoken to as the summation of some Fibonacci numbers, and no Fibonacci number is in the summation more that once, as demonstrated in Eq. 2 .
Fibonacci is s famous mathematical sequence. Each number within the sequence is a sum total of the two preceding numbers: 1, 1, 2, 3, 5, 8, 13 and so on. The Fibonacci sequence is key to calculating retracement lines. This is achieved through Fibonacci ratios. There are three Fibonacci ratios that traders need to be aware of: 61.8% (any
Fibonacci trading in Forex To draw Fibonacci, we need to select a swing move. Additionally, we have to try to do that in the right direction. That is why it is crucial to understand price behaviour, trends, swings. . Fibonacci trading is a technique, where you are using tools based on Fibonacci numbers to predict possible turning points.
