View in EDS HTML Full Text PDF Full Text

Fibonacci Imposters

Saved in:
Bibliographic Details
Title: Fibonacci Imposters
Language: English
Authors: Simons, C. S., Wright, M.
Source: International Journal of Mathematical Education in Science and Technology. Jul 2007 38(5):677-682.
Availability: Taylor & Francis, Ltd. 325 Chestnut Street Suite 800, Philadelphia, PA 19106. Tel: 800-354-1420; Fax: 215-625-2940; Web site: http://www.tandf.co.uk/journals/default.html
Peer Reviewed: Y
Page Count: 6
Publication Date: 2007
Document Type: Journal Articles
Reports - Evaluative
Descriptors: Mathematical Concepts, Mathematics Education, Algebra, Mathematical Applications, Sequential Approach, Validity, Mathematical Logic, Equations (Mathematics)
DOI: 10.1080/00207390701228401
ISSN: 0020-739X
Abstract: With Simson's 1753 paper as a starting point, the current paper reports investigations of Simson's identity (also known as Cassini's) for the Fibonacci sequence as a means to explore some fundamental ideas about recursion. Simple algebraic operations allow one to reduce the standard linear Fibonacci recursion to the nonlinear Simon's recursion that is equivalent to Simson's identity and then further to a nonlinear recursion dependent only on a single preceding term. This leads to a striking nonrecursive characterization of Fibonacci numbers that is much less well-known than it should be. It is then discovered that Simson's recursion itself implies a family of linear recursions and characterizes a class of generalized Fibonacci sequences.
Abstractor: Author
Number of References: 7
Entry Date: 2007
Accession Number: EJ771158
Database: ERIC
Full text is not displayed to guests.
FullText Links:
  – Type: pdflink
    Url: https://content.ebscohost.com/cds/retrieve?content=AQICAHj0k_4E0hTGH8RJwT4gCJyBsGNe_WN95AvKlDbXJGqwxwHby6K5BV4Y3If0yxYA_HyTAAAA4jCB3wYJKoZIhvcNAQcGoIHRMIHOAgEAMIHIBgkqhkiG9w0BBwEwHgYJYIZIAWUDBAEuMBEEDO6UB5ap_GD2tITO8gIBEICBmvk3c09cX2UKn27QVueq0GK6csQc6sQKujioSUQJYJSYgaYn1ygeiGMwKNWOXfs7NSLrKxLvFg5BjNN41tOpWguzqJw6CysYsPMN6InPbWwEO028DPLIzx4wwIrQKqo9pzAX2W2laD0wrcYlvc2YDtsTw5rAnuCpZBTqpUhDwU2-iJXn5vEj0CeLVf0lWWWbgUNZ4o55PSCT_0s=
Text:
  Availability: 1
  Value: <anid>AN0025902205;imt01jul.07;2019Feb27.14:40;v2.2.500</anid> <title id="AN0025902205-1">Fibonacci imposters. </title> <sbt id="AN0025902205-2">1. Introduction</sbt> <p>With Simson's 1753 paper as a starting point, the current paper reports investigations of Simson's identity (also known as Cassini's) for the Fibonacci sequence as a means to explore some fundamental ideas about recursion. Simple algebraic operations allow one to reduce the standard linear Fibonacci recursion to the nonlinear Simon's recursion that is equivalent to Simson's identity and then further to a nonlinear recursion dependent only on a single preceding term. This leads to a striking nonrecursive characterization of Fibonacci numbers that is much less well-known than it should be. It is then discovered that Simson's recursion itself implies a family of linear recursions and characterizes a class of generalized Fibonacci sequences.</p> <p>The first recursive sequence many students encounter is the famous Fibonacci sequence defined by the two initial values and the recursion . For quick reference we list the first few values of this sequence.</p> <p>Graph</p> <p>Among its many celebrated properties is Simson's identity (independently discovered by Cassini)</p> <p>Graph</p> <p>For example, if <emph>n</emph> = 6, this becomes 13 × 5 - 8<sups>2</sups> = (-1)<sups>6</sups> and we see that the square of a Fibonacci number differs by one from the product of the Fibonacci numbers adjacent to it. Simson gave a simple inductive proof of the identity in an interesting 1753 paper [<reflink idref="bib1" id="ref1">1</reflink>]. Our goal is to extend Simson's ideas to explore other sequences that behave like the Fibonacci sequence. In doing so we will rediscover some surprising results. Except for the notation, Simson's proof of the identity is essentially the same as those taught today in discrete math, number theory, and history of math courses.</p> <hd id="AN0025902205-3">Proof</hd> <p> The base case <emph>n</emph> = 2 holds as 2× 1 - 1<sups>2</sups> =(-1)<sups>2</sups>. So we assume the identity holds for a given <emph>n</emph> and we proceed to prove that</p> <p>Graph</p> <p>The left-hand side is equivalent to</p> <p>Graph</p> <p>After proving the identity, Simson proposes using it to reduce the number of preceding terms used in the recursion for the Fibonacci sequence. Starting with Simson's identity and solving for we get Simson's recursion</p> <p>Graph</p> <p>Using this recursion along with the standard Fibonacci recursion we find that</p> <p>Graph</p> <p>So that</p> <p>Graph</p> <p>This is equivalent to</p> <p>Graph</p> <p>Solving for the positive root using the quadratic formula,</p> <p>Graph</p> <p>where the ± is the sign of (-1)<emph><sups>n</sups></emph></p> <p>Equation (<reflink idref="bib3" id="ref2">3</reflink>) tells us (and told Simson) two important things. The first is that we now only need one initial value to start the Fibonacci sequence, since if we know that <emph>F</emph><subs>1</subs> = 1 then it follows that and the recursion begins. The second is that since we are dealing with an integer sequence, must be an integer. Therefore if <emph>a</emph> is a Fibonacci number then 5<emph>a</emph><sups>2</sups> ±4 must be a square (of an integer) for at least one choice of the ±. A computer search using Mathematica [<reflink idref="bib2" id="ref3">2</reflink>] for numbers with this property leads to a natural conjecture.</p> <hd id="AN0025902205-4">CONJECTURE 1.1</hd> <p>  <emph>Let <emph>a</emph> be a positive integer. Then <emph>a</emph> is a Fibonacci number if and only if at least one of 5<emph>a</emph><sups>2</sups>-4 or 5<emph>a</emph><sups>2</sups>+4 is a square.</emph></p> <p>For now we define a Fibonacci imposter to be a positive integer <emph>a</emph> such that one of 5<emph>a</emph><sups>2</sups>-4 or 5<emph>a</emph><sups>2</sups>+4 is a square but such that <emph>a</emph> is not a Fibonacci number. Therefore the conjecture holds exactly if there are no Fibonacci imposters.</p> <hd id="AN0025902205-5">2. No Fibonacci imposters?</hd> <p>It turns out that Conjecture 1.1 is true [<reflink idref="bib3" id="ref4">3</reflink>], and its proof is instructive. We prove it by combining the following two lemmas concerning the hyperbolas</p> <p>Graph</p> <hd id="AN0025902205-6">LEMMA 2.1</hd> <p>  Let <emph>x</emph> be a positive integer. 5<emph>x</emph><sups>2</sups>±4 is a square if and only if there is a positive integer <emph>y</emph> such that .</p> <hd id="AN0025902205-7">LEMMA 2.2</hd> <p>  The positive integer solutions to are Fibonacci pairs .</p> <p>Lemma 2.2 is described in [<reflink idref="bib4" id="ref5">4</reflink>], and given as an exercise in [<reflink idref="bib5" id="ref6">5</reflink>] (Chapter 3, Section 1, Exercise 32). We now prove the lemmas.</p> <hd id="AN0025902205-8">Proof</hd> <p> [Lemma 2.1] If <emph>x</emph> and <emph>y</emph> are positive integers satisfying equation (<reflink idref="bib4" id="ref7">4</reflink>) then by the quadratic formula (for positive root <emph>y</emph>)</p> <p>Graph</p> <p>So 5<emph>x</emph><sups>4</sups>±4 is a square. Furthermore if 5<emph>x</emph><sups>4</sups>±4 is a square, then we can choose <emph>y</emph> to be in order to satisfy equation (<reflink idref="bib4" id="ref8">4</reflink>).□</p> <hd id="AN0025902205-9">Proof</hd> <p> [Lemma 2.2]</p> <p>Let (<emph>x,y</emph>)=(<emph>a,b</emph>) be a positive integer solution to equation (<reflink idref="bib4" id="ref9">4</reflink>). The use of the quadratic formula in equation (<reflink idref="bib5" id="ref10">5</reflink>) shows us that <emph>b</emph>≥ <emph>a</emph>. If <emph>b</emph> = <emph>a</emph> then we have -<emph>a</emph><sups>2</sups> = ±1, so that <emph>b</emph>=a=1, which is the initial Fibonacci pair. So we now assume that <emph>b</emph>><emph>a</emph>≥ 1. Setting (<emph>x,y</emph>)=(<emph>b-a,a</emph>) gives a smaller positive integer solution to equation (<reflink idref="bib4" id="ref11">4</reflink>) since . So long as <emph>x</emph>≠ <emph>y</emph>, this procedure can be repeated to get successively smaller integer solutions. However, since we are dealing with positive integers, this repetition must terminate with a solution where <emph>y</emph> = <emph>x</emph>, and we have already seen this can only be the initial Fibonacci pair. Since this reduction implements the standard Fibonacci recursion, we find that all positive integer solutions to equation (<reflink idref="bib4" id="ref12">4</reflink>) must be Fibonacci pairs.□</p> <p>We therefore restate Conjecture 1.1 as a theorem.</p> <hd id="AN0025902205-10">THEOREM 2.3</hd> <p>  <emph>Let <emph>a</emph> be a positive integer. Then <emph>a</emph> is a Fibonacci number if and only if at least one of 5<emph>a</emph><sups>2</sups>-4 or 5<emph>a</emph><sups>2</sups>+4 is a square.</emph></p> <p>Having proven this theorem, we find that under our current definition there are no Fibonacci imposters. In order to make our search nontrivial, we must replace our definition of Fibonacci imposters with one that still satisfies Simson's recursion while yielding more than just the Fibonacci sequence.</p> <hd id="AN0025902205-11">3. Fibonacci imposter sequences</hd> <p>We now consider the family of all positive integer sequences defined by two initial values <subs>1</subs>, <subs>2</subs>, that satisfy Simson's recursion</p> <p>Graph</p> <p>Clearly the Fibonacci sequence belongs to this family, as do all of its tail sequences obtained by deleting the first 2<emph>k</emph> terms of the Fibonacci sequence. We now define a Fibonacci imposter sequence to be any other member of this family.</p> <p>Since any such Fibonacci imposter sequence consists only of positive integers a necessary, but not sufficient, condition for such a sequence is for</p> <p>Graph</p> <p>to be a positive integer. The easiest way to ensure this is to set .</p> <p>If as well, we get the Fibonacci sequence.</p> <p>If , we a get a sequence starting with</p> <p>Graph</p> <p>In fact this is known as the Pell sequence, and it also appears to satisfy the much simpler linear recursion .</p> <p>If instead , we get a sequence starting with</p> <p>Graph</p> <p>This sequence also appears to satisfy a simple linear recursion .</p> <p>In general if and then Simson's recursion (equation (<reflink idref="bib6" id="ref13">6</reflink>)) implies that the much simpler linear recursion</p> <p>Graph</p> <p>holds. Before we prove this claim, we note that something remarkable is occurring. Not only have we found some Fibonacci imposter sequences, but we see that the very nonlinear Simson's recursion (equation (<reflink idref="bib6" id="ref14">6</reflink>)) behaves in a surprisingly linear way.</p> <hd id="AN0025902205-12">Proof</hd> <p> We prove equation (<reflink idref="bib7" id="ref15">7</reflink>) by a simple induction. It holds in the base case <emph>n</emph> = 2 since . So we assume that equation (<reflink idref="bib7" id="ref16">7</reflink>) holds for a given <emph>n</emph> and proceed to find that</p> <p>Graph</p> <p>as desired.□</p> <p>We conclude by asking if we have now found all Fibonacci imposter sequences. A quick machine investigation using Mathematica [<reflink idref="bib2" id="ref17">2</reflink>] yields no small counterexamples so we make the following conjecture.</p> <hd id="AN0025902205-13">CONJECTURE 3.1</hd> <p>  <emph>The infinite positive integer sequences satisfying the Simson's recursion</emph> (<emph>equation</emph> (<reflink idref="bib6" id="ref18">6</reflink>)) <emph>are precisely those linear recursive sequences defined by</emph>, , <emph>or their tails obtained by obtained by deleting the first</emph> 2<emph>k terms</emph>.</p> <p>We have in fact almost proven this conjecture already.</p> <hd id="AN0025902205-14">Proof</hd> <p> Since we want equation (<reflink idref="bib7" id="ref19">7</reflink>), if we set <emph>n</emph> = 2 and solve for <emph>a</emph> we must have</p> <p>Graph</p> <p>This guarantees that the base case of inductive proof for equation (<reflink idref="bib7" id="ref20">7</reflink>) holds. The inductive step follows exactly as in equation (<reflink idref="bib8" id="ref21">8</reflink>). We must now prove two things.</p> <p>We must first verify that <emph>a</emph>=<emph>p/q</emph>, with <emph>p</emph> and <emph>q</emph> relatively prime, is a positive integer. It is positive by its definition in equation (<reflink idref="bib9" id="ref22">9</reflink>). Since</p> <p>Graph</p> <p>and all the terms are integers, we find that for all <emph>n</emph> ≥ 2. (In fact if we repeat this process inductively we even find that for all <emph>n</emph> ≥ 0.) However Simson's recursion (equation (<reflink idref="bib6" id="ref23">6</reflink>)) implies that the the greatest common divisor of <emph><subs>n</subs></emph> and is 1. Therefore <emph>q</emph> = 1 and <emph>a</emph> is a positive integer.</p> <p>Finally we must verify that or that if the sequence is extended backwards using the linear recursion (equation (<reflink idref="bib7" id="ref24">7</reflink>)) the first positive term is 1. So assume the sequence has been extended backwards and that is the first positive term (note that <emph>k</emph>≤ 0). We then find that and that because Simson's identity continues to hold for this extension as can be verified by modifying the proof of Simson's identity. However since the integers and , we find that <emph>k</emph> is even and (while and so by the linear recursion ).□</p> <p>We therefore restate Conjecture 3.1 as a theorem.</p> <hd id="AN0025902205-15">THEOREM 3.2</hd> <p>  The infinite positive integer sequences satisfying the Simson's recursion (equation (<reflink idref="bib6" id="ref25">6</reflink>)) are precisely those linear recursive sequences defined by , , or their tails obtained by obtained by deleting the first 2<emph>k</emph> terms.</p> <hd id="AN0025902205-16">4. Generalized Fibonacci sequences</hd> <p>Given these linear recursion properties, it is clear that these so-called Fibonacci imposter sequences are not really imposters, but are in fact generalizations of the Fibonacci sequence. They are a specialization of the well-known generalized Fibonacci sequences [<reflink idref="bib6" id="ref26">6</reflink>], [<reflink idref="bib7" id="ref27">7</reflink>] with linear recursion</p> <p>Graph</p> <p>for positive integers <emph>a</emph> and <emph>b</emph> and initial terms and . These can alternately be defined by the generalized Simson's identity</p> <p>Graph</p> <p>and its corresponding quadratic recursion. Our hunt for imposters considers the case where <emph>b</emph> = 1, however by modifying our proofs as needed the reader may obtain corresponding results and continue the search for generalized Fibonacci imposters.</p> <ref id="AN0025902205-17"> <title> References </title> <blist> <bibl id="bib1" idref="ref1" type="bt">1</bibl> <bibtext> Simson, R. 1753. An explication of an obscure passage in Albert Girard's commentary upon Simon Stevin's works. Philosophical Transactions (1683–1775), 48: 368–377.</bibtext> </blist> <blist> <bibl id="bib2" idref="ref3" type="bt">2</bibl> <bibtext> Wolfram Research, Inc.2003. Mathematica, version 5.0, Champaign, IL: Wolfram Research, Inc..</bibtext> </blist> <blist> <bibl id="bib3" idref="ref2" type="bt">3</bibl> <bibtext> Gessel, I. 1972. Fibonacci is square (problem and solution H-187). Fibonacci Quarterly, 10: 417</bibtext> </blist> <blist> <bibl id="bib4" idref="ref5" type="bt">4</bibl> <bibtext> Vajda, S. 1989. Fibonacci and Lucas Numbers, and the Golden Section, , 5th edn, New York: Ellis Horwood Ltd.</bibtext> </blist> <blist> <bibl id="bib5" idref="ref6" type="bt">5</bibl> <bibtext> Young, RM. 1992. Excursions in Calculus: An Interplay of the Continuous and the Discrete, Washington, DC: Mathematical Association of America.</bibtext> </blist> <blist> <bibl id="bib6" idref="ref13" type="bt">6</bibl> <bibtext> Benjamin, AT and Quinn, J. 2003. The Fibonacci numbers–exposed more discretely. Mathematics Magazine, 76(3): 182–192.</bibtext> </blist> <blist> <bibl id="bib7" idref="ref15" type="bt">7</bibl> <bibtext> Kalman, D and Mena, R. 2003. The Fibonacci numbers–exposed. Mathematics Magazine, 76(3): 167–181.</bibtext> </blist> </ref> <aug> <p>By C. S. Simons and M. Wright</p> <p>Reported by Author; Author</p> </aug> <nolink nlid="nl1" bibid="bib8" firstref="ref21"></nolink> <nolink nlid="nl2" bibid="bib9" firstref="ref22"></nolink>
Header DbId: eric
DbLabel: ERIC
An: EJ771158
AccessLevel: 3
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Fibonacci Imposters
– Name: Language
  Label: Language
  Group: Lang
  Data: English
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Simons%2C+C%2E+S%2E%22">Simons, C. S.</searchLink><br /><searchLink fieldCode="AR" term="%22Wright%2C+M%2E%22">Wright, M.</searchLink>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="SO" term="%22International+Journal+of+Mathematical+Education+in+Science+and+Technology%22"><i>International Journal of Mathematical Education in Science and Technology</i></searchLink>. Jul 2007 38(5):677-682.
– Name: Avail
  Label: Availability
  Group: Avail
  Data: Taylor & Francis, Ltd. 325 Chestnut Street Suite 800, Philadelphia, PA 19106. Tel: 800-354-1420; Fax: 215-625-2940; Web site: http://www.tandf.co.uk/journals/default.html
– Name: PeerReviewed
  Label: Peer Reviewed
  Group: SrcInfo
  Data: Y
– Name: Pages
  Label: Page Count
  Group: Src
  Data: 6
– Name: DatePubCY
  Label: Publication Date
  Group: Date
  Data: 2007
– Name: TypeDocument
  Label: Document Type
  Group: TypDoc
  Data: Journal Articles<br />Reports - Evaluative
– Name: Subject
  Label: Descriptors
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Mathematical+Concepts%22">Mathematical Concepts</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematics+Education%22">Mathematics Education</searchLink><br /><searchLink fieldCode="DE" term="%22Algebra%22">Algebra</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+Applications%22">Mathematical Applications</searchLink><br /><searchLink fieldCode="DE" term="%22Sequential+Approach%22">Sequential Approach</searchLink><br /><searchLink fieldCode="DE" term="%22Validity%22">Validity</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+Logic%22">Mathematical Logic</searchLink><br /><searchLink fieldCode="DE" term="%22Equations+%28Mathematics%29%22">Equations (Mathematics)</searchLink>
– Name: DOI
  Label: DOI
  Group: ID
  Data: 10.1080/00207390701228401
– Name: ISSN
  Label: ISSN
  Group: ISSN
  Data: 0020-739X
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: With Simson's 1753 paper as a starting point, the current paper reports investigations of Simson's identity (also known as Cassini's) for the Fibonacci sequence as a means to explore some fundamental ideas about recursion. Simple algebraic operations allow one to reduce the standard linear Fibonacci recursion to the nonlinear Simon's recursion that is equivalent to Simson's identity and then further to a nonlinear recursion dependent only on a single preceding term. This leads to a striking nonrecursive characterization of Fibonacci numbers that is much less well-known than it should be. It is then discovered that Simson's recursion itself implies a family of linear recursions and characterizes a class of generalized Fibonacci sequences.
– Name: AbstractInfo
  Label: Abstractor
  Group: Ab
  Data: Author
– Name: Ref
  Label: Number of References
  Group: RefInfo
  Data: 7
– Name: DateEntry
  Label: Entry Date
  Group: Date
  Data: 2007
– Name: AN
  Label: Accession Number
  Group: ID
  Data: EJ771158
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=eric&AN=EJ771158
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1080/00207390701228401
    Languages:
      – Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 6
        StartPage: 677
    Subjects:
      – SubjectFull: Mathematical Concepts
        Type: general
      – SubjectFull: Mathematics Education
        Type: general
      – SubjectFull: Algebra
        Type: general
      – SubjectFull: Mathematical Applications
        Type: general
      – SubjectFull: Sequential Approach
        Type: general
      – SubjectFull: Validity
        Type: general
      – SubjectFull: Mathematical Logic
        Type: general
      – SubjectFull: Equations (Mathematics)
        Type: general
    Titles:
      – TitleFull: Fibonacci Imposters
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Simons, C. S.
      – PersonEntity:
          Name:
            NameFull: Wright, M.
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 07
              Type: published
              Y: 2007
          Identifiers:
            – Type: issn-print
              Value: 0020-739X
          Numbering:
            – Type: volume
              Value: 38
            – Type: issue
              Value: 5
          Titles:
            – TitleFull: International Journal of Mathematical Education in Science and Technology
              Type: main
ResultId 1