Problem Books in Mathematics Dorin Andrica Ovidiu Bagdasar Recurrent Sequences Key Results, Applications, and Problems Problem Books in Mathematics SeriesEditor PeterWinkler DepartmentofMathematics DartmouthCollege Hanover,NH USA Moreinformationaboutthisseriesathttp://www.springer.com/series/714 Dorin Andrica • Ovidiu Bagdasar Recurrent Sequences Key Results, Applications, and Problems 123 DorinAndrica OvidiuBagdasar DepartmentofMathematics CollegeofEngineeringandTechnology “Babes¸-Bolyai”University UniversityofDerby Cluj-Napoca,Romania Derby,UK ISSN0941-3502 ISSN2197-8506 (electronic) ProblemBooksinMathematics ISBN978-3-030-51501-0 ISBN978-3-030-51502-7 (eBook) https://doi.org/10.1007/978-3-030-51502-7 Mathematics Subject Classification: 05A18, 11B39, 11B83, 11D45, 11N37, 11N56, 11N64, 11Y55, 11Y70,40A05,40A10 ©SpringerNatureSwitzerlandAG2020 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthorsandtheeditorsaresafetoassumethattheadviceandinformationinthisbook arebelievedtobetrueandaccurateatthedateofpublication.Neitherthepublishernortheauthorsor theeditorsgiveawarranty,expressedorimplied,withrespecttothematerialcontainedhereinorforany errorsoromissionsthatmayhavebeenmade.Thepublisherremainsneutralwithregardtojurisdictional claimsinpublishedmapsandinstitutionalaffiliations. ThisSpringerimprintispublishedbytheregisteredcompanySpringerNatureSwitzerlandAG Theregisteredcompanyaddressis:Gewerbestrasse11,6330Cham,Switzerland “YourdaysincreasewitheachTomorrow” (“Cumâinezilele-t¸iadaogi”) byMihaiEminescu YourdaysincreasewitheachTomorrow, YourlifegrowslesswithYesterday, Infrontofyoutherelies,however, Foralloftheeternity:Today. These famous verses of the national poet of the Romanians capture the close connections between poetry and mathematics. Indeed, if D denotes the number n of days in someone’s life, then the equation of life described by the poet can be encodedinthefollowingwell-knownrecurrence: Dn+1−Dn−1 =Dn, whichcoincideswiththerecurrencesatisfiedbytheFibonaccinumbers. Preface Overviewand Goals This book presents the state-of-the-art results concerning recurrent sequences and their practical applications in algebra, number theory, geometry of the complex plane, discrete mathematics, or combinatorics. The purpose of this book is to familiarize more readers with recent developments in this area and to encourage furtherresearch. The content of the book is recent and reflects current research in the field of recurrent sequences. Some new approaches promoted by this book are visual representationsofrecurrencesinthecomplexplaneandtheuseofmultiplemethods forderivingnovelidentitiesornumbersequences. Thefirstpartofthebookisdedicatedtofundamentalresultsandkeyexamplesof recurrencesandtheirproperties.Wealsopresentthegeometryoflinearrecurrences in the complex plane in some detail. Here, some recent research has led to unexpecteddevelopmentswithincombinatorics,numbertheory,integersequences, andrandomnumbergeneration. Thesecond partofthebook presents123olympiad trainingproblemswithfull solutions and some appendices. These relate to linear recurrences of first, second, andhigherorders,classicalsequences,homographicrecurrences,systemsofrecur- rences,complexrecurrentsequences,andrecurrentsequencesincombinatorics. Audience This book will be useful for researchers and scholars who are interested in recent advances in the field of recurrences, postgraduate students in college or university andtheirinstructors,oradvancedhighschoolstudents. Students training for mathematics competitions and their coaches will find numerous worked examples and problems with detailed solutions. Many of these vii viii Preface problems are original, while others are selected from international olympiads or fromvariousspecialistjournals. Organizationand Features The book is organized in eight chapters and an appendix. The first six chapters are dedicated to theoretical results, examples, and applications, while the last two containolympiadproblemsaccompaniedbyfullsolutions. Chapter1presentsthefundamentalaspectsconcerningrecurrencerelations,such as explicit and implicit forms, order, systems of recurrent sequences, or existence anduniquenessofthesolution.Thechapteralsopresentssomerecurrencesequences arising in mathematical modeling, algebra, combinatorics, geometry, analysis, or iterativenumericalmethods. Chapter2isdedicatedtofirst-andsecond-orderlinearrecurrenceswithgeneral coefficients, various classical sequences and polynomials (including Fibonacci, Lucas, Pell, or Lucas–Pell), and homographic recurrences defined by linear frac- tionaltransformationsinthecomplexplane. Chapter 3 presents the arithmetic properties and trigonometric formulae for classical recurrent sequences, extending some results for Fibonacci and Lucas numbers. Chapter 4 is dedicated to ordinary and exponential generating functions for classical functions and polynomials and presents numerous new results. It also presentssomenewusefulversionsofCauchy’sintegralformula. Chapter 5 explores the dynamics of second-order linear recurrences in the complex plane, referred to as Horadam sequences. We first formulate periodicity conditions, which are then used to investigate the geometric structure and the numberofperiodicHoradampatterns.Anatlasofnon-periodicHoradampatternsis alsopresented,followedbyanapplicationtopseudo-randomnumbergenerators.We concludewithsomeexamplesofperiodicnonhomogeneousHoradamsequences. Chapter6presentsthedynamicsofcomplexlinearrecurrentsequencesofhigher order and investigates the periodicity, geometric structure, and enumeration of the periodic patterns. Some results concerning systems of linear recurrence sequences arealsoanalyzed,togetherwithapplicationstoDiophantineequations.Anatlasof complex linear recurrent patterns (both periodic and non-periodic) for third-order recurrencesisalsodiscussed,alongwithconnectionstofinitedifferences. Chapter 7 contains 123 olympiad training problems involving recurrent sequences, solved in detail in Chapter 8. Many problems are original and concern linear recurrence sequences of first, second, and higher orders, some classical sequences, homographic sequences, systems of sequences, complex recurrence sequences,andrecursionsincombinatorics. Preface ix Prerequisites Our intention was to make the book as self-contained as possible, so we have included many definitions together with examples. Chapters 1, 2, and 5 only require good understanding of college algebra, complex numbers, analysis, and basic combinatorics. For Chapters 3, 4, and 6, the prerequisites include number theory,linearalgebra,andcomplexanalysis. HowtoUsetheBook The book presents recurrent sequences in connection with a wide range of topics andisillustratedwithnumerousexamplesanddiagrams. The introductory chapter and some of the properties of first- and second-order linear recurrences (which include classical number sequences) are elementary and canbeunderstoodbyhighschoolstudents. More advanced topics such as homographic recurrences, generating functions, higher-order recurrent sequences, or systems of recurrent sequences require con- ceptsusuallycoveredincollegeorundergraduatecourses. We have also included many original and recent results on arithmetic and trigonometric properties of classical sequences, new applications of Cauchy’s integral formula in the study of polynomial coefficients, or the complex recurrent patternsappliedinpseudo-randomnumbergeneration,whichexposethereaderto thestateoftheartinthefield. The collection of problems with full solutions illustrates the wide range of topicswhererecurrentsequencescanbefoundandrepresentsanidealmaterialfor preparingstudentsforOlympiads. Thebookalsoincludes177referencesandanindexwhichwillhelpthereaders tofurtherinvestigatekeynotionsandconcepts. Acknowledgements We would like to thank Dr George Ca˘ta˘lin T¸urcas¸ and Remus Miha˘ilescu, for checkingthedocumentcarefullyandprovidingfeedback. We are indebted to the anonymous referees for their constructive remarks and suggestions,whichhelpedustoimprovethequalityofthemanuscript. Specialthankstoourfamilies,fortheircontinuousanddiscretesupport. Cluj-Napoca,Romania DorinAndrica Derby,UK OvidiuBagdasar May2020 Contents 1 IntroductiontoRecurrenceRelations ..................................... 1 1.1 RecursiveSequencesofOrderk....................................... 2 1.2 RecurrentSequencesDefinedbyaSequenceofFunctions .......... 3 1.3 SystemsofRecurrentSequences ...................................... 3 1.4 ExistenceandUniquenessoftheSolution ............................ 4 1.5 RecurrentSequencesArisinginPracticalProblems.................. 6 1.5.1 ApplicationsinMathematicalModeling ..................... 6 1.5.2 Algebra......................................................... 8 1.5.3 Combinatorics ................................................. 9 1.5.4 Geometry....................................................... 11 1.5.5 Analysis........................................................ 12 1.5.6 IterativeNumericalMethods.................................. 14 2 BasicRecurrentSequences ................................................. 19 2.1 First-OrderLinearRecurrentSequences.............................. 19 2.2 Second-OrderLinearRecurrentSequences........................... 26 2.2.1 HomogeneousRecurrentSequences.......................... 26 2.2.2 NonhomogeneousRecurrentSequences ..................... 34 2.2.3 Fibonacci,Lucas,Pell,andPell–LucasNumbers............ 38 2.2.4 ThePolynomialsU (x,y)andV (x,y) ..................... 48 n n 2.2.5 PropertiesofFibonacci,Lucas,Pell,andLucas–Pell Numbers ....................................................... 58 2.2.6 Zeckendorf’sTheorem........................................ 65 2.3 HomographicRecurrences............................................. 67 2.3.1 KeyDefinitions................................................ 67 2.3.2 HomographicRecurrentSequences .......................... 68 2.3.3 RepresentationTheoremsforHomographicSequences..... 72 2.3.4 ConvergenceandPeriodicity.................................. 74 2.3.5 HomographicRecurrenceswithVariableCoefficients ...... 77 xi