Factorization of Recurrence Relations

Overview

Objectives/Goals The combinatorial solution to the recurrence relation a_{n} =a_{n-1} +a_{n-3} +a_{n-4} leads to the trend, a_{2n} =f_{n}^2 , where f_{n} is the n-th term in the Fibonacci sequence. This project explores the generalization of the solution to this recurrence relation to yield a new family of sequences where every k-th term is the k-th power of u_{n}: a_{kn} =u_{n}^k. u_{n} is the solution to Horadam#s second order recurrence relation of the kind u_{n}=p#u_{n-1} +q#u_{n-2}, where p, q are integers. Methods/Materials I used several techniques to investigate the factorization of these recurrence relations. First, I used diagrams to illustrate the factorization. I explored how to find the recurrence relation with even terms leading to square of generalized second-order recurrence relation through bijections and Binet-like formulas. I took the trend, described above, of squares of Fibonacci numbers for every even term and generalized it for cubes of any second-order sequence. Finally, I derived a generalized version of this sequence, with every k-th term yielding the k-th power of the generalized second-order sequence. Techniques that I used drew from number theory. I used Hadamard products, Cauchy#s residue theorem, diagrams, Binet#s formula, partial fractions, and work by Hoggart and Legendre. An understanding of recurrence relation and generating functions was paramount, as well. Results The solution to the recurrence relation was found to be a_{2n} =f_{n}^2 and a_{2n+1} =f_{n}f_{n+1}. The bijection for a_{2n} was denoted by the number of ways we can tile two rectangles of length 1xn with 1x1 square and 1x2 rectangle. This bijection was generalized to k rectangles for a_{kn} and a solution was found for its generating function through bijection as well as Binet-like formula. Conclusions/Discussion These results represent the product of a year of investigation, however, additional work is being done to explore related problems in this field, such as examining similar families for Catalan and Motzkin numbers.

Awards (1)

• Second Place

Competition history

• CSEF 2017 Mathematical Sciences · Entry S1514

Resources

• CSEF project summary ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

• All Mathematics projects
• CSEF Mathematics projects
• Every CSEF 2017 project
• CSEF Second Place winners