Factorizing Delayed Powers of Generalized Fibonacci Sequence

Overview

Objectives/Goals Let a_{n} denote the number of positive integers containing only the digits 1, 3, and 4, so that the sum of the digits is equal to n. Then a_{2n} is always a perfect square, for any n. (In fact, it is the square of a Fibonacci number.) It appears that the natural recurrence relation generating the a_{n} s, factors through the recurrence for the Fibonacci numbers. Hypothesis: For a second-order linear recurrence relation of the form u_{n} = (p)u_{n-1} + (q)u_{n-2}, we can create a recurrence relation which yields sequences which have an = u_{n}^(k) or n_{k}= u_{n}^(k). We can also create a closed-form generating function and a combinatorial/pictorial representation. Methods/Materials Project Materials: Computer with Matlab and Maple installed General project methods: Generating functions, recurrence relations, partial fraction expansions, Hadamard products, tilings, Cauchy's residue theorem Results First, I found the generating function of u_n = u_{n-1} + u_{n-3} + u_{n-4}. Additionally, I used the generating functions for the square and cube of Fibonacci sequence and its generating function to derive a recurrence relation for the kth power of Fibonacci sequence. Next, I investigated the kind of recurrence relations that yield square of various second order linear recurrence of the kind defined in the hypothesis, un = (p)u_{n-1} + (q)u_{n-2}. To do this, I especially used Hadamard products and Cauchy's residue theorem. Also, I used diagrams, especially tiles, to model the problem. Then, I used the findings for a new recurrence relation that can be generalized so that the kth term is the kth power of the second order linear recurrence. I found a closed-form generating function for this, specifically finding the numerator, which no one has done before. Finally, I explored different possibilities for combinatorially represent my solution, specifically a pictorial form. Conclusions/Discussion My project has strong implications for furthering the field of steganography, as the recurrence relation and generating function may be used to encrypt messages in the images better. It has potential to be used with Zeckendorf's Theorem, which states that every number can be represented using distinct Fibonacci numbers.

Competition history

• CSEF 2018 Mathematical Sciences · Entry S1507

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 2018 project