Fibonacci and Lucas Numbers with Applications, Volume 2
Description
As in Volume I, Volume II focuses on problem-solving techniques such as pattern recognition; conjecturing; proof-techniques, and applications. It offers a wealth of delightful opportunities to explore and experiment, as well as plentiful material for group discussions, seminars, presentations, and collaboration.
In addition, the material covered in this book promotes intellectual curiosity, creativity, and ingenuity.
Volume II features:
* A wealth of examples, applications, and exercises of varying degrees of difficulty and sophistication.
* Numerous combinatorial and graph-theoretic proofs and techniques.
* A uniquely thorough discussion of gibonacci subfamilies, and the fascinating relationships that link them.
* Examples of the beauty, power, and ubiquity of the extended gibonacci family.
* An introduction to tribonacci polynomials and numbers, and their combinatorial and graph-theoretic models.
* Abbreviated solutions provided for all odd-numbered exercises.
* Extensive references for further study.
This volume will be a valuable resource for upper-level undergraduates and graduate students, as well as for independent study projects, undergraduate and graduate theses. It is the most comprehensive work available, a welcome addition for gibonacci enthusiasts in computer science, electrical engineering, and physics, as well as for creative and curious amateurs.
More details
Other editions
Additional editions
Person
Thomas Koshy, PhD, is the author of eleven books and numerous articles. As a professor of Mathematics at Framingham State University in Framingham, Massachusetts, he received the Distinguished Service Award, Citation for Meritorious Service, Commonwealth Citation for Outstanding Performance, as well as Faculty of the Year. He received his PhD in Algebraic Coding Theory from Boston University, under the guidance of Dr. Edwin Weiss.
"Dr. Koshy is a meticulous researcher who shares his encyclopedic knowledge regarding Fibonacci and Lucas numbers in Fibonacci and Lucas Numbers, Volume I. In Volume II, he extends all of those wonderful ideas and identities to the Gibonacci polynomials, the "grandfathers" of the Fibonacci and Lucas polynomials. Writing in a readable style and including many examples and exercises, Koshy ties together Fibonacci and Lucas polynomials with Chebyshev, Jacobsthal, and Vieta polynomials. Once again, Koshy has compiled lore from diverse sources into one understandable and intriguing volume." Marjorie Bicknell Johnson
Content
List of Symbols xiii
Preface xv
31. Fibonacci and Lucas Polynomials I 1
31.1. Fibonacci and Lucas Polynomials 3
31.2. Pascal's Triangle 18
31.3. Additional Explicit Formulas 22
31.4. Ends of the Numbers ln 25
31.5. Generating Functions 26
31.6. Pell and Pell-Lucas Polynomials 27
31.7. Composition of Lucas Polynomials 33
31.8. De Moivre-like Formulas 35
31.9. Fibonacci-Lucas Bridges 36
31.10. Applications of Identity (31.51) 37
31.11. Infinite Products 48
31.12. Putnam Delight Revisited 51
31.13. Infinite Simple Continued Fraction 54
32. Fibonacci and Lucas Polynomials II 65
32.1. Q-Matrix 65
32.2. Summation Formulas 67
32.3. Addition Formulas 71
> 76
32.5. Divisibility Properties 82
33. Combinatorial Models II 87
33.1. A Model for Fibonacci Polynomials 87
33.2. Breakability 99
33.3. A Ladder Model 101
33.4. A Model for Pell-Lucas Polynomials: Linear Boards 102
33.5. Colored Tilings 103
33.6. A New Tiling Scheme 104
33.7. A Model for Pell-Lucas Polynomials: Circular Boards 107
33.8. A Domino Model for Fibonacci Polynomials 114
33.9. Another Model for Fibonacci Polynomials 118
34. Graph-Theoretic Models II 125
34.1. Q-Matrix and Connected Graph 125
34.2. Weighted Paths 126
34.3. Q-Matrix Revisited 127
34.4. Byproducts of the Model 128
34.5. A Bijection Algorithm 136
34.6. Fibonacci and Lucas Sums 137
34.7. Fibonacci Walks 140
35. Gibonacci Polynomials 145
35.1. Gibonacci Polynomials 145
35.2. Differences of Gibonacci Products 159
35.3. Generalized Lucas and Ginsburg Identities 174
35.4. Gibonacci and Geometry 181
35.5. Additional Recurrences 184
35.6. Pythagorean Triples 188
36. Gibonacci Sums 195
36.1. Gibonacci Sums 195
36.2. Weighted Sums 206
36.3. Exponential Generating Functions 209
36.4. Infinite Gibonacci Sums 215
37. Additional Gibonacci Delights 233
37.1. Some Fundamental Identities Revisited 233
37.2. Lucas and Ginsburg Identities Revisited 238
37.3. Fibonomial Coefficients 247
37.4. Gibonomial Coefficients 250
37.5. Additional Identities 260
37.6. Strazdins' Identity 264
38. Fibonacci and Lucas Polynomials III 269
38.1. Seiffert's Formulas 270
38.2. Additional Formulas 294
38.3. Legendre Polynomials 314
39. Gibonacci Determinants 321
39.1. A Circulant Determinant 321
39.2. A Hybrid Determinant 323
39.3. Basin's Determinant 333
39.4. Lower Hessenberg Matrices 339
39.5. Determinant with a Prescribed First Row 343
40. Fibonometry II 347
40.1. Fibonometric Results 347
40.2. Hyperbolic Functions 356
40.3. Inverse Hyperbolic Summation Formulas 361
41. Chebyshev Polynomials 371
41.1. Chebyshev Polynomials Tn(x) 372
41.2. Tn(x) and Trigonometry 384
41.3. Hidden Treasures in Table 41.1 386
41.4. Chebyshev Polynomials Un(x) 396
41.5. Pell's Equation 398
41.6. Un(x) and Trigonometry 399
41.7. Addition and Cassini-like Formulas 401
41.8. Hidden Treasures in Table 41.8 402
41.9. A Chebyshev Bridge 404
41.10. Tn and Un as Products 405
41.11. Generating Functions 410
42. Chebyshev Tilings 415
42.1. Combinatorial Models for Un 415
42.2. Combinatorial Models for Tn 420
42.3. Circular Tilings 425
43. Bivariate Gibonacci Family I 429
43.1. Bivariate Gibonacci Polynomials 429
43.2. Bivariate Fibonacci and Lucas Identities 430
43.3. Candido's Identity Revisited 439
44. Jacobsthal Family 443
44.1. Jacobsthal Family 444
44.2. Jacobsthal Occurrences 450
44.3. Jacobsthal Compositions 452
44.4. Triangular Numbers in the Family 459
44.5. Formal Languages 468
44.6. A USA Olympiad Delight 480
44.7. A Story of 1, 2, 7, 42, 429,...483
44.8. Convolutions 490
45. Jacobsthal Tilings and Graphs 499
45.1. 1 × n Tilings 499
45.2. 2 × n Tilings 505
45.3. 2 × n Tubular Tilings 510
45.4. 3 × n Tilings 514
45.5. Graph-Theoretic Models 518
45.6. Digraph Models 522
46. Bivariate Tiling Models 537
46.1. A Model for ;;n(x, y) 537
46.2. Breakability 539
46.3. Colored Tilings 542
46.4. A Model for ln(x, y) 543
46.5. Colored Tilings Revisited 545
46.6. Circular Tilings Again 547
47. Vieta Polynomials 553
47.1. Vieta Polynomials 554
47.2. Aurifeuille's Identity 567
47.3. Vieta-Chebyshev Bridges 572
47.4. Jacobsthal-Chebyshev Links 573
47.5. Two Charming Vieta Identities 574
47.6. Tiling Models for Vn 576
47.7. Tiling Models for ;;n(x) 582
48. Bivariate Gibonacci Family II 591
48.1. Bivariate Identities 591
48.2. Additional Bivariate Identities 594
48.3. A Bivariate Lucas Counterpart 599
48.4. A Summation Formula for ;;2n(x, y) 600
48.5. A Summation Formula for l2n(x, y) 602
48.6. Bivariate Fibonacci Links 603
48.7. Bivariate Lucas Links 606
49. Tribonacci Polynomials 611
49.1. Tribonacci Numbers 611
49.2. Compositions with Summands 1, 2, and 3 613
49.3. Tribonacci Polynomials 616
49.4. A Combinatorial Model 618
49.5. Tribonacci Polynomials and the Q-Matrix 624
49.6. Tribonacci Walks 625
49.7. A Bijection between the Two Models 627
Appendix 631
A.1. The First 100 Fibonacci and Lucas Numbers 631
A.2. The First 100 Pell and Pell-Lucas Numbers 634
A.3. The First 100 Jacobsthal and Jacobsthal-Lucas Numbers 638
A.4. The First 100 Tribonacci Numbers 642
Abbreviations 644
Bibliography 645
Solutions to Odd-Numbered Exercises 661
Index 725
31
Fibonacci and Lucas Polynomials I
A man may die,
nations may rise and fall,
but an idea lives on.
-John F. Kennedy (1917-1963)
The celebrated Fibonacci polynomials were originally studied beginning in 1883 by the Belgian mathematician Eugene C. Catalan, and later by the German mathematician Ernst Jacobsthal (1882-1965). They were further investigated by M.N.S. Swamy at the University of Saskatchewan, Canada. The equally famous Lucas polynomials were studied beginning in 1970 by Marjorie Bicknell of Santa Clara, California [37].
Eugène Charles Catalan (1814-1894) was born in Bruges, Belgium, and received his Doctor of Science from the École Polytechnique in Paris. After working briefly at the Department of Bridges and Highways, he became professor of mathematics at Collège de Chalons-sur-Marne, and then at Collège Charlemagne. Catalan went on to teach at Lycée Saint Louis. In 1865, he became professor of analysis at the University of Liège. He published Éléments de Géométrie (1843) and Notions d'astronomie (1860), as well as many articles on multiple integrals, the theory of surfaces, mathematical analysis, calculus of probability, and geometry. Catalan is well known for extensive research on spherical harmonics, analysis of differential equations, transformation of variables in multiple integrals, continued fractions, series, and infinite products.
M.N.S. Swamy was born in Karnataka, India. He received his B.Sc. (Hons) in Mathematics from Mysore University in 1954; Diploma in Electrical Engineering from the Indian Institute of Science, Bangalore, in 1957; and M.Sc. (1960) and Ph.D. (1963) in Electrical Engineering from the University of Saskatchewan, Canada.
A former Chair of the Department of Electrical Engineering and Dean of Engineering and Computer Science at Concordia University, Canada, Swamy is currently a Research Professor and the Director of the Center for Signal Processing and Communications. He has also taught at the Technical University of Nova Scotia, and the Universities of Calgary and Saskatchewan.
Swamy is a prolific problem-proposer and problem-solver well known to the Fibonacci audience. He has published extensively in number theory, circuits, systems, and signal processing and has written three books. He is the editor-in-chief of Circuits, Systems, and Signal Processing, and an associate editor of The Fibonacci Quarterly, and a sustaining member of the Fibonacci Association.
Swamy received the Commemorative Medal for the 125th Anniversary of the Confederation of Canada in 1993 in recognition of his significant contributions to Canada. In 2001, he was awarded D.Sc. in Engineering by Ansted University, British Virgin Islands, "in recognition of his exemplary contributions to the research in Electrical and Computer Engineering and to Engineering Education, as well as his dedication to the promotion of Signal Processing and Communications Applications."
Marjorie Bicknell-Johnson was born in Santa Rosa, California. She received her B.S. (1962) and M.A. (1964) in Mathematics from San Jose State University, California, where she wrote her Master's thesis, The Lambda Number of a Matrix, under the guidance of V.E. Hoggatt, Jr.
The concept of the lambda number of a matrix first appears in the unpublished notes of Fenton S. Stancliff (1895-1962) of Meadville, Pennsylvania. (He died in Springfield, Ohio in 1962.) His extensive notes are pages of numerical examples without proofs or coherent definitions, that provided material for further study. Bicknell developed the mathematics of the lambda function in her thesis [40].
A charter member of the Fibonacci Association, Bicknell-Johnson has been a member of its Board of Directors since 1967, as well as Secretary (1965-2010) and Treasurer (1981-1999). In 2012, she wrote a history of the first 50 years of the Association [39].
Bicknell-Johnson has been a passionate and enthusiastic contributor to the world of Fibonacci and Lucas numbers, as author or co-author of research papers, 32 of them written with Hoggatt. Her 1980 obituary of Hoggatt remains a fine testimonial to their productive association [38].
31.1 Fibonacci and Lucas Polynomials
As we might expect, they satisfy the same polynomial recurrence , where . When and ; and when and . Table 31.1 gives the first ten Fibonacci and Lucas polynomials in . Clearly, and .
Table 31.1 First 10 Fibonacci and Lucas Polynomials
1 1 2 3 4 5 6 7 8 9 10In the interest of brevity and clarity, we drop the argument in the functional notation, when such deletions do notcause any confusion. Thus will mean , although is technically a functional name and notan output value.
For the curious-minded, we add that is an even function when is odd, and an odd function when is even; and is an odd function when is odd, and even when is even.
Table 31.2 Triangular Array
Table 31.1 contains some hidden treasures. To see them, we arrange the nonzero coefficients of the Fibonacci polynomials in a left-justified array ; see Table 31.2. Column 2 of the array consists of the triangular numbers , and the th row sum is .
Let denote the element in row and column of the array. Clearly, is the coefficient of in ; so . Recall that [287].
Consequently, it can be defined recursively:
where and ; see the arrows in Table 31.2. This can be confirmed; see Exercise 31.1.
Let denote the th rising diagonal sum. The sequence shows an interesting pattern: 1, 1, 1, 2, 3, 4, ?, 9, 13, .; see Figure 31.1 We can also define recursively:
where .
Since , it follows that
For example, .
The falling diagonal sums also exhibit an interesting pattern: 1, 2, 4, 8, 16, .; see Figure 31.2. This is so, since the th such sum is given by
where .
The nonzero elements of Lucas polynomials also manifest interesting properties; see array in Table 31.3.
Table 31.3 Triangular Array
Let denote the element in row and column , where and . Then
- 1) .
- 2) , where , and .
- 3) Let denote the th rising diagonal sum. Then , and , where .
- 4) .
For example, .
In the interest of brevity, we omit their proofs; see Exercises 31.2-31.5.
Next we construct a graph-theoretic model for Fibonacci polynomials.
Weighted Fibonacci Trees
Recall from Chapter 4 that the th Fibonacci tree is a (rooted) binary tree [287]such that
- 1) both and consist of exactly one vertex; and
- 2) is a binary tree whose left subtree is and right subtree is , where . It has vertices, leaves, internal vertices, and edges.
Figure 31.3 shows the first five Fibonacci trees.
We now assign a weightto recursively. The weight of is 1 and that of is . Then the weight of is defined by , where .
For example, ; and .
Since , and , it follows by the recursive definition that , where . Clearly, gives the number of leaves of when .
Binet-like Formulas
Using the recurrence and the initial conditions, we can derive explicit formulas for both and ; see Exercises 31.6 and 31.7:
where and are the solutions of the equation and . Notice that , and .
Since and , it follows by the principle of mathematical induction (PMI) that , where ; see Exercise 31.8. Similarly .
Using the Binet-like formulas, we can extend the definitions of Fibonacci and Lucas polynomials to negative subscripts: and .
Using the Binet-like formulas, we can also extract a plethora of properties of Fibonacci and Lucas polynomials; see Exercises...
