Difference between revisions of "MILS 03A"

From Math Images
Jump to: navigation, search
m (Removing all content from page)
Line 1: Line 1:
= Fibonacci Numbers =
{{Image Description
|ImageName=Fibonacci numbers in a sea shell
|ImageIntro=The spiral curve of the Nautilus sea shell follows the pattern of a spiral drawn in a Fibonacci rectangle, a collection of squares with sides that have the length of Fibonacci numbers.
|ImageDescElem=The Fibonacci sequence is the sequence <math>1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots,</math> where the first two numbers  are 1s and every later number is  the sum of the two previous  numbers. So, given two <math>1</math>'s as the first two terms, the next terms of the sequence follows as : <math>1+1=2, 1+2=3, 2+3=5, 3+5=8, \dots</math>
The Fibonacci numbers can be discovered in nature, such as the spiral of the Nautilus sea shell, the petals of the flowers, the seed head of a sunflower, and many other parts. For more information about Fibonacci patterns in nature, see [[#Fibonacci_Numbers_in_Nature| Fibonacci Numbers in Nature]].
{{Anchor|Reference=2|Link=[[Image:Rabbit.png|Image 2|thumb|300px|right]]}}
The Fibonacci sequence was studied by Leonardo of Pisa, or Fibonacci (1770-1240). In his work Liber Abacci, he introduced a problem involving the growth of the rabbit population. The assumptions were
*There is one pair of baby rabbits placed in an enclosed place on the first day of January.
*This pair will grow for two months before reproducing.  Then, beginning on March 1, it will produce a new pair of rabbits on the first day of every month.
*Each new pair will similarly mature for two months and then start producing a new pair of rabbits every month, beginning on the first day of their third month
*The rabbits never die
The problem was to find out how many pairs of rabbits there will be after one year.
On January 1st, there is only 1 pair. On February 1st, the rabbits are still maturing, so they don't reproduce.  There is still just 1 pair of rabbits.  On March 1st, the rabbits reproduce, so the population is now 2 pairs of rabbits.
Now fast forward to at any later month, say, June.  As you can see in [[#2|Image 2]], the population in June includes all 5 pairs of rabbits that were already alive in May.  The population on June 1st also includes 3 pairs of new born rabbits, because the 3 pairs that were already alive in April are old enough to reproduce.
This means that on June 1st, there are 5 + 3 = 8 pairs of rabbits.  This same reasoning can be applied to any month (except January or February), so the population of rabbits pairs in any month equals the sum of the number of rabbit pairs in the two previous months. 
This pattern is exactly the rule that defines the Fibonacci sequence.  As you can see in the image, the population by month begins: 1, 1, 2, 3, 5, 8, ..., which is the same as the beginning of the Fibonacci sequence.  The population continues to match the Fibonacci sequence no matter how many months out you go.
An interesting fact is that this problem of rabbit population was not intended to explain the Fibonacci numbers. This problem was originally intended to introduce the Hindu-Arabic numerals to Western Europe, where people were still using Roman numerals, and to help people practice addition. It was coincidence that the number of rabbits followed a certain pattern which people later named as the Fibonacci sequence.
=Fibonacci Numbers in Nature=
{{SwitchPreview|ShowMessage=Click To Show More|HideMessage=Click to Hide|PreviewText=Fibonacci numbers appear in the arrangement of leaves...|FullText=
{{Anchor|Reference=3|Link=[[Image:fibonacileaf.png|Image 3|thumb|120px|right]]}}
===Leaf Arrangement===
Fibonacci numbers appear in the arrangement of leaves in certain plants. Take a plant, locate the lowest leaf and number that leaf as 0. Number the leaves by order of creation starting from 0, as shown in [[#3|Image 3]]. Then, count the number of leaves you encounter until you reach the next leaf that is directly above and pointing in the same direction as the lowest leaf, which is the leaf with number 8 in this image. The number of leaves you pass, in this case, 8, will be a Fibonacci number.
Moreover, the number of rotations you make around the stem until you reach that leaf will also be a Fibonacci number. You make rotations up the stem by following ascending order of the leaf's number. In [[#3|Image 3]], for example, if you follow the red arrows, the number of rotations you make until you reach leaf number 8 will be 5, which is a Fibonacci number.
{{Anchor|Reference=5|Link=[[Image:goldenrectangle copy.jpg|Image 5|thumb|300px|right]]}}
Fibonacci numbers can be seen in nature through spiral forms that can be constructed by Fibonacci rectangles as shown in [[#5|Image 5]]. Fibonacci rectangles are rectangles in which the ratio of the length to the width is the proportion of two consecutive Fibonacci numbers.
One way we can build Fibonacci rectangles is by first drawing two squares with length 1 next to each other. Then, we draw a new square with length 2 that is touching the sides of the original two squares. We draw another square with length 3 that is touching one unit square and the latest square with length 2. With each new square, a new Fibonacci rectangle is created. Its length is equal to the sum of the lengths of the latest two squares, and its width is equal to the length of the most recent square.
After building Fibonacci rectangles, we can draw a spiral in the squares, each square containing a quarter of a circle. Such spiral is called the Fibonacci spiral, and it can be seen in sea shells, snails, the spirals of the galaxy, and other parts of nature, as shown in [[#6|Image 6]] and [[#7|Image 7]].
{{Anchor|Reference=6|Link=[[Image:shell.jpg|Image 6|thumb|170px|left]]}}
{{Anchor|Reference=7|Link=[[Image:galaxy.jpg|Image 7|thumb|250px|none]]}}
|ImageDesc===Symbolic Definition of Fibonacci Sequence==
The Fibonacci sequence is the sequence <math>F_1, F_2, F_3, \ldots, F_n, \ldots</math> where
:<math>F_n = F_{n-1} + F_{n-2}    \quad  \hbox{ for } n>2</math>,
:<math>F_1 = 1,\ F_2 = 1</math>.
The Fibonacci sequence is <balloon title="load:recursive">recursively defined</balloon><span id="recursive" style="display:none">A recursively defined sequence is one in which each term is defined by preceding terms in the sequence. For instance, <math>x_n=(x_{n-1})^2-3x_{n-2}</math> is recursively defined.</span> because each term is defined in terms of its two immediately preceding terms.
Here are some interesting identities.  These can be proven using [[Induction|mathematical induction]].
===Sum of first <math>n</math> Fibonacci numbers===
One identity of the Fibonacci numbers is that the sum of first<math>n</math> Fibonacci numbers is one less than the value of the <math>{(n+2)}^{\rm th}</math> Fibonacci number:
:{{EquationRef2|Eq. (1)}}<math>F_1+F_2+\dots+F_n=F_{n+2}-1</math>
For example, the sum of first <math>5</math> Fibonacci numbers is :
:<math>F_1+F_2+F_3+F_4+F_5= 1 + 1 + 2 + 3 +5=12=F_7-1</math>
The example is demonstrated below. The total length of red bars that each correspond to <math>F_1, F_2, F_3, F_4, F_5</math> is one unit less than the length of <math>F_7</math>.
[[image:identity1.gif|thumb|Image 9|none|600px]]
===Greatest Common Divisor===
This identity says that the greatest common divisor of two Fibonacci numbers is the Fibonacci number whose <balloon title="load:indexDef">index</balloon><span id="indexDef" style="display:none">The index of a Fibonacci number is its position in the sequence.  For example, the seventh Fibonacci has an index of 7 and the eighth Fibonacci has an index of 8.</span> is the greatest common divisor of the indices of the original two Fibonacci numbers. In other words,
:<math>\gcd(F_n,F_m) = F_{\gcd(n,m)}</math>.
For instance,
:<math> \gcd(F_9,F_6)=\gcd(34,8)=2=F_{\gcd(9,6)}</math>.
The last step above follows from the fact that <math> \gcd(9,6) = 3 </math>, and <math> F_3 = 2 </math>.
In the special case where <math> F_n</math> and <math> F_m</math> are consecutive Fibonacci numbers, this property says that
:<math>\gcd(F_n, F_{n+1})=F_{\gcd(n,n+1)}=F_1=1</math>.
That is, <math>F_n</math> and <math>F_{n+1} </math>, or two consecutive Fibonacci numbersare always <balloon title="Two integers are relatively prime if their greatest common divisor is 1"> relatively prime</balloon>.
For information about other identities of Fibonacci numbers, go to [http://mathworld.wolfram.com/FibonacciNumber.html Wolfram MathWorld Fibonacci Number]
==Binet's Formula for Fibonacci Numbers==
Binet's Formula gives a formula for the <math>n^{\rm th}</math> Fibonacci number as :
:<math>F_n=\frac{{\varphi}^n-{\bar{\varphi}}^n}{\sqrt5} </math>.
Here, <math>\varphi=\frac{1 + \sqrt{5}}{2}</math> and <math> \bar{\varphi}=\frac{1-\sqrt{5}}{2}</math>.
These two numbers are the solutions to the equation
{{EquationRef2|Eq. (5)}}<math> x^2=x+1</math>.
A proof is given below, although it does not provide any insight into how Binet (or anyone else) would come up with this formula.  It only verifies that it is correct.
Define <math>B_n</math> by the equation:
:<math>B_n=\frac{{\varphi}^n-{\bar{\varphi}}^n}{\sqrt5} </math>.
We will know Binet's formula is correct if we can show that all the values of <math>B_n</math> are the same as the Fibonacci numbers.  In order to do this, we will first show that <math>B_n</math> follows the same recursive rule as the Fibonacci numbers, by verifying the formula:
:<math>B_n=B_{n-1}+B_{n-2}\quad\hbox{ for } n>2</math>
To verify this formula, note that according to the definition of <math>B_n</math>:
{{EquationRef2|Eq. (6a)}}<math>B_{n-1}+B_{n-2} = \frac{{\varphi}^{n-1}-{\bar{\varphi}}^{n-1}}{\sqrt5}+ \frac{{\varphi}^{n-2}-{\bar{\varphi}}^{n-2}}{\sqrt5} </math>
{{EquationRef2|Eq. (6b)}}<math> = \frac{({\varphi}^{n-1}+{\varphi}^{n-2})-({\bar{\varphi}}^{n-1}+{\bar{\varphi}}^{n-2})}{\sqrt5}</math>
{{EquationRef2|Eq. (6c)}}<math>=\frac{({\varphi}+1){\varphi}^{n-2}-(\bar{\varphi}+1){\bar{\varphi}}^{n-2}}{\sqrt5}</math>.
Because <math>\varphi</math> and <math>\bar{\varphi}</math> are the two roots of {{EquationNote|Eq. (5)}}, the above equation becomes:
{{EquationRef2|Eq. (6d)}}<math>B_{n-1}+B_{n-2}=\frac{{{\varphi}^2}{\varphi}^{n-2}-{{\bar{\varphi}}^2}{\bar{\varphi}}^{n-2}}{\sqrt5}</math>
{{EquationRef2|Eq. (6e)}}<math>=\frac{{\varphi}^n-{\bar{\varphi}}^n}{\sqrt5}</math>
{{EquationRef2|Eq. (6f)}}<math>=B_n</math>, as desired.
Now we know that <math>B_n</math> follows the recursive rule of the Fibonacci numbers.  If we plug <math> n=1 </math> and <math> n=2 </math> to the formula that defines <math> B_n </math>, we see that <math> B_1 = 1 </math>, and <math> B_2 = 1 </math>.
Thus, <math>B_n</math> has the same recursive formula as the Fibonacci numbers and it has the same starting two values, so this formula really is a correct formula for the Fibonacci numbers.
Maurer, Stephen B & Ralston, Anthony. (2004) Discrete Algorithmic Mathematics. Massachusetts : A K Peters.
Posamentier, Alfred S & Lehmann Ingmar. (2007) The Fabulous Fibonacci Numbers. New York : Prometheus Books.
Vorb'ev, N. N. (1961) Fibonacci Numbers. New York : Blaisdell Publishing Company.
Hoggatt, Verner E., Jr. (1969) Fibonacci and Lucas Numbers. Boston : Houghton Mifflin Company.
Knott, Ron. (n.d.). The Fibonacci Numbers and Golden Section in Nature. Retrieved from http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibnat.html
Wikipedia (Golden Ratio). (n.d.). Golden Ratio. Retrieved from http://en.wikipedia.org/wiki/Golden_ratio.
Fibonacci Numbers in Nature & the Golden Ratio. (n.d.). In World-Mysteries.com. Retrieved from http://www.world-mysteries.com/sci_17.htm
Wikipedia (Mandelbrot Set). (n.d.). Mandelbrot Set. Retrieved from http://en.wikipedia.org/wiki/Mandelbrot_set.
Devaney, Robert L. (2006) Unveiling the Mandelbrot Set. Retrieved from http://plus.maths.org/issue40/features/devaney/.
Weisstein, Eric W. (n.d.). Mandelbrot Set. In MathWorld--A Wolfram Web Resource. Retrieved from http://mathworld.wolfram.com/MandelbrotSet.html.
|Field=Number Theory

Revision as of 10:06, 30 June 2011