Fibonacci numbers
A pair of pages with plenty of playful problems to perplex the professional and the part-time puzzler!
The Easier Fibonacci Puzzles page
has the Fibonacci numbers in brick wall patterns, Fibonacci bee lines, seating people in a row and the Fibonacci numbers again, giving change and a game with match sticks and even with electrical resistance and lots more puzzles all involve the Fibonacci numbers!
The Harder Fibonacci Puzzles page
still has problems where the Fibonacci numbers are the answers - well, all but ONE, but WHICH one? If you know the Fibonacci Jigsaw puzzle where rearranging the 4 wedge-shaped pieces makes an additional square appear, did you know the same puzzle can be rearranged to make a different shape where a square now disappears?
For these puzzles, I do not know of any simple explanations of why the Fibonacci numbers occur - and that's the real puzzle - can you supply a simple reason why??
This, the first, looks at the Fibonacci numbers and why they appear in various "family trees" and patterns of spirals of leaves and seeds.
The second page then examines why the golden section is used by nature in some detail, including animations of growing plants.
Fibonacci numbers can also be seen in the arrangement of seeds on flower heads. The picture here is Tim Stone's beautiful photograph of a Coneflower, used here by kind permission of Tim. The part of the flower in the picture is about 2 cm across. It is a member of the daisy family with the scientific name Echinacea purpura and native to the Illinois prairie where he lives.
A scrambled version 13, 3, 2, 21, 1, 1, 8, 5 (Sloane's A117540) of the first eight Fibonacci numbers appear as one of the clues left by murdered museum curator Jacque Sauniere in D. Brown's novel The Da Vinci Code (Brown 2003, pp. 43, 60-61, and 189-192). In the Season 1 episode "Sabotage" (2005) of the television crime drama NUMB3RS, math genius Charlie Eppes mentions that the Fibonacci numbers are found in the structure of crystals and the spiral of galaxies and a nautilus shell.
The plot above shows the first 511 terms of the Fibonacci sequence represented in binary, revealing an interesting pattern of hollow and filled triangles (Pegg 2003). A fractal-like series of white triangles appears on the bottom edge, due in part to the fact that the binary representation of ends in zeros. Many other similar properties exist.
The Fibonacci numbers give the number of pairs of rabbits months after a single pair begins breeding (and newly born bunnies are assumed to begin breeding when they are two months old), as first described by Leonardo of Pisa (also known as Fibonacci ) in his book Liber Abaci. Kepler also described the Fibonacci numbers (Kepler 1966; Wells 1986, pp. 61-62 and 65). Before Fibonacci wrote his work, the Fibonacci numbers had already been discussed by Indian scholars such as Gopala (before 1135) and Hemachandra (c. 1150) who had long been interested in rhythmic patterns that are formed from one-beat and two-beat notes or syllables. The number of such rhythms having beats altogether is , and hence these scholars both mentioned the numbers 1, 2, 3, 5, 8, 13, 21, ... explicitly (Knuth 1997, p. 80).
The numbers of Fibonacci numbers less than 10, , , ... are 6, 11, 16, 20, 25, 30, 35, 39, 44, ... (Sloane's A072353). There is an interesting pattern in the number of digits of . In particular, for , 2, ..., the result are 2, 21, 209, 2090, 20899, 208988, 2089877, 20898764, ... (Sloane's A068070). As can be seen, the initial strings of digits settle down to produce the number 208987640249978733769...
Origins
The "Fibonacci" numbers first appear, under the name maatraameru (mountain of cadence), in the work of the Sanskrit grammarian Pingala (Chhandah-shāstra, the Art of Prosody, 450 or 200 BC). The Indian mathematician Virahanka gave explicit rules for the Fibonacci sequence in the 8th century. The Indian Jain philosopher Hemachandra (c.1150) (and also Gopala) revisited the problem in some detail. Sanskrit vowel sounds can be long (L) or short (S), and Hemachandra wished to compute how many cadences of a given overall length can be composed of these. If the long syllable is twice as long as the short, the solutions are:
1 mora: S (1 pattern)
2 morae: SS; L (2)
3 morae: SSS, SL; LS (3)
4 morae: SSSS, SSL, SLS; LSS, LL (5)
5 morae: SSSSS, SSSL, SSLS, SLSS, SLL; LSSS, LSL, LLS (8)
A pattern of length n can be formed by adding S to a pattern of length n−1, or L to a pattern of length n−2; thus Hemachandra showed that the number of patterns of length n is the sum of the two previous numbers in the series. Donald Knuth reviews this work in his The Art of Computer Programming as equivalent to the problem of bin packing items of length 1 and 2.
In the West, the sequence was first studied by Leonardo of Pisa, known as Fibonacci (1202). He considers the growth of an idealised (biologically unrealistic) rabbit population, assuming that:
in the first month there is just one newly-born pair,
new-born pairs become fertile from their second month on
each month every fertile pair begets a new pair, and
the rabbits never die
Let the population at month n be F(n). At this time, only rabbits who were alive at month n−2 are fertile and produce offspring, so F(n−2) pairs are added to the current population of F(n−1). Thus the total is F(n) = F(n−1) + F(n−2).
Applications
The Fibonacci numbers are important in the run-time analysis of Euclid's algorithm to determine the greatest common divisor of two integers: the worst case input for this algorithm is a pair of consecutive Fibonacci numbers.
Yuri Matiyasevich was able to show that the Fibonacci numbers can be defined by a Diophantine equation, which led to his original solution of Hilbert's tenth problem.
The Fibonacci numbers occur in a formula about the diagonals of Pascal's triangle (see binomial coefficient).
Every positive integer can be written in a unique way as the sum of one or more distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers. This is known as Zeckendorf's theorem, and a sum of Fibonacci numbers that satisfies these conditions is called a Zeckendorf representation.
Fibonacci numbers are used by some pseudorandom number generators.
A one-dimensional optimization method, called the Fibonacci search technique uses Fibonacci numbers [4].
In music Fibonacci numbers are sometimes used to determine tunings, and, as in visual art, to determine the length or size of content or formal elements. Examples include Béla Bartók's Music for Strings, Percussion, and Celesta. In addition, the syllables of the lyrics of parts of the Tool song Lateralus follow the Fibonacci sequence in each line, for instance "Black/Then/White are/All I see/In my infancy/Red and yellow then came to be".
Since the conversion factor 1.609 for miles to kilometers is close to the golden mean φ, the decomposition of distance in miles into a sum of Fibonacci numbers becomes nearly the kilometer sum when the Fibonacci numbers are replaced by their successors. This method amounts to a radix 2 number register in base φ being shifted. To go from kilometers to miles shift the register down the Fibonacci sequence instead.