Chapter 2 Fibonacci Numbers - MathWorks

1 Chapter 2 Fibonacci NumbersFibonacci Numbers introduce vectors, functions and Pisano Fibonacci was born around 1170 and died around 1250 inPisa in what is now Italy. He traveled extensively in Europe and Northern wrote several mathematical texts that, among other things, introduced Europeto the Hindu-Arabic notation for Numbers . Even though his books had to be tran-scribed by hand, they were widely circulated. In his best known book,Liber Abaci,published in 1202, he posed the following problem:A man puts a pair of rabbits in a place surrounded on all sides by a many pairs of rabbits can be produced from that pair in a year if itis supposed that every month each pair begets a new pair which from thesecond month on becomes productive?

2 Today the solution to this problem is known as theFibonacci sequence, orFibonacci Numbers . There is a small mathematical industry based on Fibonaccinumbers. A search of the Internet for Fibonacci will find dozens of Web sites andhundreds of pages of material. There is even a Fibonacci Association that publishesa scholarly journal, theFibonacci simulation of Fibonacci s problem is provided by execute the commandrabbitsand click on the pushbuttons that show up. You will see something like figure Fibonacci had not specified a month for the newborn pair to mature, hewould not have a sequence named after him. The number of pairs would simplyCopyrightc 2011 Cleve MolerMatlabR is a registered trademark of MathWorks , 2, 201112 Chapter 2.

3 Fibonacci NumbersFigure 's each month. Afternmonths there would be 2npairs of rabbits. That s alot of rabbits, but not distinctive the number of pairs of rabbits afternmonths. The key fact isthat the number of rabbits at the end of a month is the number at the beginningof the month plus the number of births produced by the mature pairs:fn=fn 1+fn initial conditions are that in the first month there is one pair of rabbits and inthe second there are two pairs:f1= 1,f2= followingMatlabfunction, stored in a ,produces a vector containing the firstnFibonacci f = Fibonacci (n)% Fibonacci Fibonacci sequence% f = Fibonacci (n) generates the first n Fibonacci = zeros(n,1);f(1) = 1;f(2) = 2;for k = 3:nf(k) = f(k-1) + f(k-2);endWith these initial conditions, the answer to Fibonacci s original question about thesize of the rabbit population after one year is given byfibonacci(12)This produces123581321345589144233 The answer is 233 pairs of rabbits.

4 (It would be 4096 pairs if the number doubledevery month for 12 months.)Let s look carefully It s a good example of how to create aMatlabfunction. The first line isfunction f = Fibonacci (n)The first word on the first line afunction, not a script. Theremainder of the first line says this particular function produces one output result,f, and takes one input argument,n. The name of the function specified on the firstline is not actually used, becauseMatlablooks for the name of the file with that contains the function, but it is common practice to have the two next two lines are comments that provide the text displayed when you ask fibonacciproducesFIBONACCI Fibonacci sequencef = Fibonacci (n) generates the first n Fibonacci 2.

5 Fibonacci NumbersThe name of the function is in uppercase because historicallyMatlabwas caseinsensitive and ran on terminals with only a single font. The use of capital lettersmay be confusing to some first-timeMatlabusers, but the convention persists. Itis important to repeat the input and output arguments in these comments becausethe first line is not displayed when you ask forhelpon the next linef = zeros(n,1);creates ann-by-1matrix containing all zeros and assigns it tof. InMatlab, amatrix with only one column is a column vector and a matrix with only one row isa row next two lines,f(1) = 1;f(2) = 2;provide the initial last three lines are theforstatement that does all the k = 3:nf(k) = f(k-1) + f(k-2);endWe like to use three spaces to indent the body offorandifstatements, but otherpeople prefer two or four spaces, or a tab.

6 You can also put the entire constructionon one line if you provide a comma after the first particular function looks a lot like functions in other programming lan-guages. It produces a vector, but it does not use any of theMatlabvector ormatrix operations. We will see some of these operations is another Fibonacci function, Its output is simply thenthFibonacci f = fibnum(n)% FIBNUM Fibonacci FIBNUM(n) generates the nth Fibonacci n <= 1f = 1;elsef = fibnum(n-1) + fibnum(n-2);endThe statementfibnum(12)producesans =2335 Thefibnumfunction isrecursive. In fact, the termrecursiveis used in botha mathematical and a computer science sense. In mathematics, the relationshipfn=fn 1+fn 2is arecursion relationIn computer science, a function that callsitself is arecursive recursive program is elegant, but expensive.

7 You can measure executiontime withticandtoc. Trytic, fibnum(24), tocDonottrytic, fibnum(50), tocFibonacci Meets Golden RatioThe Golden Ratio can be expressed as an infinite continued fraction. = 1 +11 +11+11+ .To verify this claim, suppose we did not know the value of this fraction. Letx= 1 +11 +11+11+ .We can see the first denominator is just another copy ofx. In other 1 +1xThis immediately leads tox2 x 1 = 0which is the defining quadratic equation for ,Ourexmfunctiongoldfractgenerates aMatlabstring that represents thefirstnterms of the Golden Ratio continued fraction. Here is the first section ofcode = '1';for k = 2:np = ['1 + 1/(' p ')'];enddisplay(p)We start with a single 1 , which corresponds ton = 1. We then repeatedly makethe current string the denominator in a longer is the output fromgoldfract(n)whenn = + 1/(1 + 1/(1 + 1/(1 + 1/(1 + 1/(1 + 1/(1))))))6 Chapter 2.

8 Fibonacci NumbersYou can see that there aren-1plus signs andn-1pairs of matching ndenote the continued fraction truncated afternterms. nis a rationalapproximation to . Let s express nas a conventional fracton, the ratio of twointegers n=pnqnp = 1;q = 0;for k = 2:nt = p;p = p + q;q = t;endNow compare the results produced bygoldfract(7)andfibonacci(7). Thefirst contains the fraction 21/13 while the second ends with 13 and 21. This is notjust a coincidence. The continued fraction for the Golden Ratio is collapsed byrepeating the statementp = p + q;while the Fibonacci Numbers are generated byf(k) = f(k-1) + f(k-2);In fact, if we let ndenote the golden ratio continued fraction truncated atnterms,then n=fnfn 1In the infinite limit, the ratio of successive Fibonacci Numbers approaches the goldenratio:limn!

9 1fnfn 1= .To see this, compute 40 Fibonacci = 40;f = Fibonacci (n);Then compute their = f(2:n)./f(1:n-1)This takes the vector containingf(2)throughf(n)and divides it, element byelement, by the vector containingf(1)throughf(n-1). The output begins ends you see why we chosen = 40? Computephi = (1+sqrt(5))/2r - phiWhat is the value of the last element?The first few of these ratios can also be used to illustrate the rational ratr(1:10)ans =23/25/38/513/821/1334/2155/3489/55 The population of Fibonacci s rabbit pen doesn t double every month; it ismultiplied by the golden ratio every Analytic ExpressionIt is possible to find a closed-form solution to the Fibonacci number recurrencerelation. The key is to look for solutions of the formfn=c n8 Chapter 2.

10 Fibonacci Numbersfor some constantscand . The recurrence relationfn=fn 1+fn 2becomesc n=c n 1+c n 2 Dividing both sides byc n 2gives 2= + ve seen this equation in the Chapter on the Golden Ratio. There are two possiblevalues of , namely and 1 . The general solution to the recurrence isfn=c1 n+c2(1 ) constantsc1andc2are determined by initial conditions, which are nowconveniently writtenf0=c1+c2= 1,f1=c1 +c2(1 ) = of the exercises asks you to use theMatlabbackslash operator to solve this2-by-2 system of simultaneous linear equations, but it is may be easier to solve thesystem by hand:c1= 2 1,c2= (1 )2 these in the general solution givesfn=12 1( n+1 (1 )n+1).This is an amazing equation. The right-hand side involves powers and quo-tients of irrational Numbers , but the result is a sequence of integers.