THE FIBONACCI NUMBERS - Whitman College

1 \Fibonaccinumbers"is usedto describe theseriesof numbersgener-atedby thepattern1;1;2;3;5;8;13;21;34;55;89;144 :::,whereeach number in thesequenceis given by thesumof theprevioustwo given byu1= 1,u2= 1 andtherecursive formulaun=un 1+un 2; n > fromthefamous\rabbitproblem"of 1228,theFibonaccinumberswereoriginallyus edto represent thenumber of pairsof rabbitsbornof onepairin a assumethata pairof rabbitsis introducedinto acertainplacein the rstmonth of rabbitswillproduceonepairof o springeverymonth,andeverypairof rabbitswillbeginto reproduceexactlytwo dies,andeverypairof ,in the rstmonth,we have onlythe rstpairof ,in thesecondmonth,we againhave onlyourinitialpairof ,by thethirdmonth,thepairwillgive birthto anotherpairof rabbits,andtherewillnowbe two ,we ndthatin monthfourwe willhave 3 pairs,then5 pairsin month ve, then8,13,21,34,..,etc,continuingin isquiteapparent thatthissequencedirectlycorrespondswitht heFibonaccisequenceintroducedabove, andindeed,thisis the rstproblemever thatwe have seenoneapplicationof theFibonaccinumbersandestablisheda basicde nition,we willgo onto examinesomeof the FIBONACCI NumbersTo beginourresearch ontheFibonaccisequence,we will rstexaminesomesim-ple,yet important actas a foundationuponwhich we canbasefutureresearch Fibonaccinumberswereproved in thebookFibonacciNumbersby ' theFibonacci NumbersThesumof the rstn FIBONACCI numberscanbe expressed asu1+u2+:::+un 1+un=un+2 1 nitionof theFibonaccisequence,we knowu1=u3 u2;u2=u4 u3;u3=u5 u4.

2 Un 1=un+1 un+2;un=un+2 un+1:We now addtheseequationsto ndu1+u2+:::+un 1+un=un+2 u2:Recallingthatu2= 1, we seethisequationis equivalent to ourinitialconjectureofu1+u2+:::+un 1+un=un+2 1: OddTermsThesumof theodd termsof theFibonacci sequenceu1+u3+u5+:::u2n 1=u2 individualterms,we seefromthede nitionof thesequencethatu1=u2;u3=u4 u2;u5=u6 u4;..u2n 1=u2n u2n 2:If we now addtheseequationstermby term,we areleftwiththerequiredresultfromabove. EvenTermsThesumof theeventermsof theFibonacci sequenceu2+u4+u6+:::u2n=u2n+1 1 , we haveu1+u2+:::+un 1+u2n=u2n+2 1:Subtractingourequationforthesumof oddterms,we obtainu2+u4+:::+u2n=u2n+2 1 u2n=u2n+1 1;as we desired. FIBONACCI NumberswithAlternatingSignsThesumof theFibonacci numberswithalternatingsignsu1 u2+u3 u4+:::+ ( 1)n+1un= ( 1)n+1un 1+ 1 ,we cansubtractoureven sumequationfromouroddsumequationto ndu1 u2+u3 u4+:::+u2n 1 u2n= u2n 1+ 1:(1)Now, addingu2n+1to bothsidesof thisequation,we obtainu1 u2+u3 u4+::: u2n+u2n+1=u2n+1 u2n 1+ 1;oru1 u2+u3 u4+::: u2n+u2n+1=u2n+ 1:(2)Combiningequations(1)and(2),we arrive at thesumof Fibonaccinumberswithalternatingsigns:u1 u2+u3 u4+:::+ ( 1)n+1un= ( 1)n+1un 1+ 1: Thus far,we have addedtheindividualtermsof simpleequationsto derive lem-masregardingthesumsof willnow usea similartechniqueto ndtheformulaforthesumof thesquaresof the SquaresThesumof thesquares of the rstnFibonacci numbersu21+u22+:::+u2n 1+u2n=unun+1 +1 uk 1uk=uk(uk+1 uk 1) =u2k:If we addtheequationsu21=u1u2;u22=u2u3 u1u2;u23=u3u4 u2u3.

3 U2n=unun+1 un 1untermby term,we arrive at theformulawe desired. Until now, we have primarilybeenusingterm-by-termadditionto ndformulasforthesumsof willnow usethemethod of inductiontoprove thefollowingimportant +m=un 1um+unum+1 willnow beginthisproof by inductiononm. Form= 1,un+1=un 1+un=un 1u1+unu2;4 TYLERCLANCY which we canseeholdstrueto 2 alsoprovestrueforourformula,asun+2=un+1+ un=un 1+un+un=un 1+ 2un=un 1u2+unu3:Thus,we have now proved thebasisof supposeourformulato be trueform=kandform=k+ shallprove thatit alsoholdsform=k+ ,by induction,assumeun+k=un 1uk+unuk+1andun+k+1=un 1uk+1+unuk+2:If we addthesetwo equationstermby term,we obtainun+k+un+k+1=un 1(uk+uk+1) +un(uk+1+uk+2)un+k+2=un 1uk+2+unuk+3;which was ,by inductionwe have proven ourinitialformulaholdstrueform=k+ 2, andthus forallvaluesofm. erence of Squares of FIBONACCI Numbersu2n=u2n+1 u2n 1 Lemma7, letm=n. We obtainu2n=un 1un+unun+1;oru2n=un(un 1+un+1):Sinceun=un+1 un 1;we cannow rewritetheformulaas follows:u2n= (un+1 un 1)(un+1+un 1);oru2n=u2n+1 u2n 1:Thus,we canconcludethatfortwo Fibonaccinumberswhosepositionsin thesequencedi erby two, thedi erenceof squareswillagainbe a Fibonaccinumber.

4 Now thatwe have establisheda seriesof lemmasregardingthesumsof theFibonaccinumbers,we willtake a brieflookat someotherinterestingpropertiesof ' interestingconnectionwiththetriangleof binomialcoe cients knownas Pascal' 'striangletypicallytakes theform:(3)111121133114641 In thisdepictionwe have orientedthetriangleto theleftforeaseof usein 'striangle,as may alreadybe apparent, is a triangleinwhich thetopmostentryis 1 andeach followingentryis equivalent to thetermdirectlyabove plusthetermabove andto Pascal'striangletakes theform:(4)C00C01C11C02C12C22C03C13C23C3 3C04C14C24C34C44:Inthisversionof Pascal'striangle,we haveCij=k!i!(k i)!, whereirepresentsthecolumnandkrepresents therow thegiventermis , we havedesignatedthe rstrow as row 0 andthe rstcolumnas , we willnow depictPascal' 'sTrianglewithRisingDiagonalsThediagonal linesdrawnthroughthenumbersof thistrianglearecalledthe\risingdiagonals "of Pascal' ,forexample,thelinespassingthrough1;3;1 or 1;4;3 wouldbothindicatedi erent risingdiagonalsof go onto relatetherisingdiagonalsto thenumbersalonga risingdiagonalin Pascal'striangleis a FIBONACCI 1, as does rowsobviouslycorrespondto the rsttwo prove theproposition,we needsimplyto show thatthesumof allnumbersin the(n 2)nddiagonalandthe(n 1)stdiagonalwillbe equalto thesumof allnumbersin thenthdiagonalin Pascal' (n 2)nddiagonalconsistsof thenumbersC0n 3; C1n 4; C2n 5; : : :andthe(n 1)stdiagonalhasthenumbersC0n 2; C1n 3; C2n 4.

5 : : :We canaddthesenumbersto ndthesumC0n 2+ (C0n 3+C1n 3) + (C1n 4+C2n 4) +: : :However,forthebinomialcoe cients of Pascal'striangle,C0n 2=C0n 1= 1andCik+Ci+1k=k(k 1) (k i+1)1 2 i+k(k 1) (k i+1)(k i)1 2 i (i+1)=k(k 1):::(k i+1)1 2 i(1 +k ii+1)=k(k 1) (k i+1)1 2 i i+1+k 1i+1=(k+1)k(k 1) (k i+1)1 2 i (i+1)=Ci+1k+1:We thereforearrive at theexpressionC0n 2+C1n 2+C2n 3+: : :=C0n 1+C1n 2+C2n 3+: : :to represent thesumof termsof thenthrisingdiagonalof Pascal' ,if we lookat diagram(4)of Pascal'striangle,thiscorrespondsto ,as we know the rsttwo diagonalsareboth1, andwe now seethatthesumof allnumbersin the(n 1)stdiagonalplusthesumof allnumbersin the(n 2)nddiagonalis equalto thesumof thenthdiagonal,we have provedthatthesumof termsonthenthdiagonalis always equivalent to thenthFibonaccinumber. us look at the7th risingdiagonalof Pascal' weaddthenumbers1;5;6;and1, we ndthatthesumof termson thediagonalis13. Asweknowthatu7= 13, wecan see thatthesumof termson the7th risingdiagonalof Pascal'sTriangleis indeed equalto the7th termof theFibonacci Pascal' the FIBONACCI Numbersandthe calculatingtheratioof two successive Fibonaccinum-bers,un+1un, we ndthatasnincreaseswithoutbound,theratioa pproaches1+ !

6 1un+1un=1 + +1=un+un 1;by de nition,it followsthatun+1un= 1 +un 1un:Now, letlimn!1un+1un=L:We thenseethatlimn!1un 1un=1L:We now have thestatementlimn!1un+1un= 1 +limn!1un 1un;which is equivalent to thetheequationL= 1 +1L:Thisequationcanthenbe rewrittenasL2 L 1 = 0;which is easilysolved ,we haveL=1 p52:8 TYLERCLANCYThus,we arrive at ourdesiredresultoflimn!1un+1un=1 +p52: Evenforrelativelylow valuesofn, thisratioproducesa 1:6182;and1 +p52 1:6180:Thevalue1+p52is thepositive root of theequationx2 x 1 = 0 andis oftenreferredto as . It arisesoftenenoughin mathematicsandhassuch interestingpropertiesthatwe alsofrequentlyreferto it as thegoldenratio. We willnow applythisratioto a beginby drawinga linesegment,AB, of length1 anddividingit into two parts,ACandCB. We willdividethissegment suchthattheratioof thewholesegment to thelargerpartis equalto theratioof thelargerpartto willdenotethelengthof thelargerportionx, whilethesmallersegment willthenobviouslybe 1 x.

7 We have thus producedtheproportion:1x=x1 x;which canbe rewrittenasx2= 1 x:Byusingthequadraticformula,we ndthatthepostive root of thisequationis 1+p52, andthus theproportionof theratiosis equalto1x=2 1 +p5=2(1+p5)( 1 +p5)(1+p5)=1 +p52= :Aswe cansee,theresultingratiois thegoldenratiowe foundin ,thedivisionof thislineat pointCis now look at a regularpentagonwithitsdiagonalsforminga gure,we seem\AFDis 108 , andm\ADFis 36 . So,by thesineruleADAF=sin108 sin36 =sin72 sin36 = 2 cos36 = 21 +p54= :Obviously,AF=AC, soADAF=ADAC= ;andwe seethatthelinesegmentADis thus dividedatCas a nitionof goldensection,we know thatACCD= , andnotingthatAB=CD, we ndACAB=ABBC= :Thus,we seethatof thesegmentsBC,AB,AC, andAD, each is a rectanglein whichthesidesareto each otheras we dividethisrectangleinto squares,we willseethatthesideof each squareis alsoequivalentto a Fibonaccinumber,andthetwo smallestsquaresareof remarkablysimilarto whatis knownas a \goldensectionrectangle,"inwhich theratioof thesidesof therectangleareequalto.

8 UsingFigure5, we willnow prove thatif we inscribe thelargestpossiblesquarewithinthegoldens ectionrectangle,theresultingspacewillaga inbe a was our rststipulation,obviouslyABAD= ;andAD=AE=EF; Dis a ,it followsthatEFEB=AB EBEB= 2 1:However, 2 1 = , so we ndEFEB= :Thus,we seethatwe doindeedhave shouldbe obviousthatthisprocessof breakingthegoldensectionrectangledownint o a seriesof smallersquarescancontinueinde nitely. Unlike thegoldensectionrectangle,however,we saw thattherectanglebasedonFibonaccinumbersd idnotcontinue in two successiveFibonaccinumbersconvergestowar ds , it is nota thisreason,we cannotassumetheFibonacci-basedrectanglew illcontinueinexhaustibly, as ,aswe cometo thesmallestFibonaccivalue,1, we will ndthatwe have two squaresof sidelength1, andnomoresquarescanbe shallnow goonto \prove" that64 = ,letus take an8x8squareandcutit into fourparts,as , if we rearrangethesefourpartsinto a 13x5rectangle,we seethatwe nowhave a totalof notcorrespondtoourinitialvalueof thisdilemnais appearsthatwe correctlyreallignedthefourpieces,thefact is we wereto usea largerFibonaccinumber to representthesideof oursquare,we couldseethatindeed,thereis a smallgapin theslitis so minisculeforsmallFibonaccinumbersthatit , whilea nicediversion, 'sFormulaUsingthemethod of combinatoricsandgeneratingfunctions.

9 We shallnow showthatthenthtermof theFibonaccisequencefn=(1+p52)n (1 p52)np5;which is knownas Binet'sformulain honorof themathematicianwho areprovingthisformulaby meansof generatingfunctions,it is impor-tant to rstgive a briefexplanationas to whata generatingfunctionis a functionin whichthecoe cientsof apowerseriesgivetheanswersto a of provingBinet'sformulawillthus be to ndthecoe cients of aTaylorseriesthatdirectlycorrespondto nition,we havefn=fn 1+fn 2, andin thisproof we willstartwiththetermsf0=f1= 1. To begin,we shallstartwitha basicfunctionf(x) givingthegeneralcoe cients of (x)=f0+f1x+f2x2+f3x3+: : : x f(x)= f0x f1x2 f2x3: : : x2 f(x)= f0x2 f1x3: : : :Combiningtheseequations,we ndf(x) x f(x) x2 f(x)=f0+ (f1 f0)x=f0=1:Usingbasicalgebrawe seef(x) =11 x x2= 1x2+x 1:THEFIBONACCINUMBERS13We willnow usethequadraticequationto ndtherootsofx2+x 1, which arex= 1+p52andx= 1 p52. Next,we canusethemethod of (x)= 1x2+x 1= 1(x 1+p52)(x 1 p52)=Ax 1+p52+Bx 1 p52:Solvingthisequation,we ndA= 1p5andB=1p5.

10 So,we now have theequationf(x)= 1x2+x 1= 1=p5x+1 p52+1=p5x+1+p52:We shallnow usemorecombinatoricmethods to ,it will rstbe important to notethat 1k =( 1)( 2)( 3): : :( 1 k+ 1)k!= ( 1)k:Letus now proceedto nishthisproof (x)= 1p5x+1 p52+1p5x+1+p52= 1p51Xk=0 1k xk 1 p52! 1 k+1p51Xk=0 1k xk 1 +p52! 1 k=1p51Xk=024( 1)k+1 1 p52! 1 k+ ( 1)k 1 +p52! 1 k35xk=1p51Xk=0" 21 p5 k+1 21 +p5 k+1#xk:Fromthiswork,we seethatthekthcoe cient ofxkis equalto1p5 1 +p52!k+1 1p5 1 p52!k+1:Asthisgeneratingfunctionwas calculatedfortherecursive formulafn=fn 1+fn 2, thisvaluealsocorrespondsto thekthtermof ,if we letf1=f2= 1 ratherthanf0=f1= 1, we canfurthersimplifythisequationto ourinitialformulaof14 TYLERCLANCYfn=(1+p52)n (1 p52)np5:Thus,we have proven Binet'sformulausingthemethod of combinatorics. Calculate FIBONACCI numberunis thenearestwholenumber to thenth term nof thegeometricprogressionwhose rsttermis p5andwhosecommonratiois.