#1 – Introduction and Deriving the Fibonacci Sequence – 3/9/25

Paul N -

Welcome to my Senior Project! My name is Paul, and in this project, I am exploring the interconnectedness of various disciplines of mathematics by learning about these disciplines and studying the ways in which they can be related to each other. Specifically, I will be studying the fields of sequences, proofs, number theory, geometry, algebra, real analysis, complex analysis, topology, differential equations, and applied mathematics. Each week of my project will be dedicated to learning about one of these topics, though since I am exploring the interconnectedness of these fields, the structure of the course will likely end up being rather loose, and each topic will appear several times as we discuss each of the other topics.

In accordance with this structure, this week’s field of study was sequences, and though there were dozens of different sequences we studied throughout the course of the week, perhaps one of the most notable was the well-known Fibonacci sequence. For those who are unfamiliar with this sequence, the Fibonacci sequence is defined such that the first two terms are equal to one and the rest of the terms are equal to the previous two terms added to each other. In mathematical notation:

fn+2=fn+1+fn

Thus, the Fibonacci sequence’s first few terms are as follows: 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on. Our goal was to derive a formula for the Fibonacci sequence using what is commonly referred to as a generating function, or in other words, a function whose Taylor series expansion returns the sequence in question. To do this, allow us to define the following function:

f(x) = 1 + x + 2x2+3x3+5x4+8x5+13x6+…

Note that the coefficient of each term in the polynomial is equal to the nth term of the Fibonacci sequence. Then, let’s take another look at the definition of the Fibonacci sequence from before, and multiply both sides by xn:

fn+2xn=fn+1xn+fnxn

Plugging in the first few values of n, we obtain the following system of equations:

2 = 1 + 1

3x = 2x + x

5x2 = 3x2 + 2x2

8x3 = 5x3 + 3x3

13x4 = 8x4 + 5x4

And so on. Notice that, by adding this system of equations together, we get that:

(2 + 3x + 5x2 + 8x3 + 13x4 + …) = (1 + 2x + 3x2 + 5x3 + 8x4 + …) + (1 + x + 2x2 + 3x3 + 5x4 + …)

Recalling the polynomial definition of f(x) from earlier, we can rewrite this as the following:

(f(x) – x – 1)/x2 = (f(x) – 1)/x + f(x)

Rearranging for f(x), we get:

f(x) = x/(1 – x – x2)

This is our generating function, whose Taylor series expansion will allow us to find a formula for the Fibonacci sequence. To find the Taylor series expansion of this function, allow us to separate this fraction into two separate fractions using partial fractions:

x/(1 – x – x2) = A/(1 – αx) + B/(1 – βx)

For now, the values of α and β are unimportant. Now solve for A and B:

x = A(1 – βx) + B(1 – αx)

1/α = A(1 – β/α)

A = 1/(α – β)

A + B = 0

B = -A = -1/(α – β)

Now, we have obtained the following:

f(x) = (1/(1 – αx) – 1/(1 – βx))/(α – β)

Recall that the Taylor series expansion of a function of the form 1/(1 – rx) is equal to the following:

1/(1 – rx) = 1 + rx + r2x2 + r3x3 + …

Thus:

f(x) = ((1 + αx + α2x2 + α3x3 + …) – (1 + βx + β2x2 + β3x3 + …))/(α – β) = ((α – β)x + (α2 – β2)x2 + (α3 – β3)x3 + …)/(α – β)

Remember that the nth coefficient of this series is equal to the nth term of the Fibonacci sequence. Thus, we now have the Fibonacci sequence:

F(n) = (αn – βn)/(α – β)

Before we can fully understand this formula, we must find the values of α and β. This can be done as follows:

(1 – αx)(1 – βx) = 1 – (α + β)x + αβx2 = 1 – x – x2

α + β = 1

αβ = -1

β = -1/α

α – 1/α = 1

α2 – α – 1 = 0

α = (1 ± √(1 + 4))/2 = (1 ± √5)/2

β = – 2/(1 ± √5)

If we assume that α is taking the positive root of 5, then it turns out that α is equal to the golden ratio, φ:

φ = (1 + √5)/2

Then:

β = -1/φ

Now, we can express our formula for the Fibonacci sequence as the following:

F(n) = (φn – (-1/φ)n)/(φ + 1/φ) = (φn – (-1/φ)n)/√5

Notice that, for plugging in for different values of n, the formula works:

F(1) = 1

F(2) = 1

F(3) = 2

F(4) = 3

F(5) = 5

And so on. Thus, we have successfully derived a formula for the Fibonacci sequence.

More Posts

Comments:

All viewpoints are welcome but profane, threatening, disrespectful, or harassing comments will not be tolerated and are subject to moderation up to, and including, full deletion.

    ryan_m
    I think that not only investigating these different fields in mathematics but also understanding their interconnectedness will give you a unique perspective of each field that few other people have. That being said, why is it important to understand and be able to derive formulas such as this one for the Fibonacci sequence, and do you expect your understanding of this specific sequence to come into play over the remaining weeks of your project?
    March 20, 2025 at 3:21 pm - Reply
    alec_b
    On a normal standard I am incredibly bad at math and a lot of times find it very difficult to follow along with difficult sequences, but The way you've broken down the steps, from defining the sequence to deriving the closed-form formula, is incredibly easy to follow. I especially enjoyed how you clearly explained the use of the generating function and partial fractions to reach the formula. It’s a smooth progression, and you made a complex topic much more accessible. I find it really interesting how the Fibonacci sequence connects to the golden ratio, and it’s cool to see how you connected these ideas. I am curious as to how you came to be so comfortable and well associated with the mathematics used such as the partial fractions? Was there a particular moment when everything clicked for you, or did you experience any challenges while connecting these ideas? Keep up the great work!
    March 20, 2025 at 10:55 pm - Reply
    Misha Patel
    The breakdown that you presented on the Fibonacci sequence was so fascinating! I loved how you carefully walked through each step, making it easy to understand even for those of us who aren't as familiar with the mathematics. It's also so interesting to see how many connections there are between very different areas of math! Is there a special topic you are excited to connect with the other topics you will be presenting? I look forward to reading more!
    March 21, 2025 at 9:20 pm - Reply
    paul_n
    Ryan: The reason that it is important to understand how to derive formulas for sequences such as the Fibonacci sequence is because it allows us to find general properties about these sequences that otherwise would not be easily noticeable, such as how the Fibonacci sequence is connected to the golden ratio. As for how I see myself using the Fibonacci sequence in the future, the Fibonacci sequence has special properties which allow us to do neat inductive proofs with it. You might find it interesting to explore how the sum of the first n terms of the Fibonacci sequence is equal to the (n+2)th term minus 1. Alec: Partial fractions was a topic that we studied in AP Calculus BC, though to be honest I was familiar with it long before taking that class. I had already been studying calculus since 9th grade outside of class, and I learned about it while learning how to take the integral of rational functions. It was difficult at first, but with practice, partial fractions and things like it become second nature. As for how I was able to make this connection between the Fibonacci sequence and the golden ratio, the main challenge was in finding the generating function; once I had done that, it was fairly easy, though incredibly tedious, to find the Fibonacci sequence. The moment where everything clicked for me was that moment when I found the generating function, since I had seen it before and immediately recognized it. I'm really glad that I was able to explain it in a way that was easy to follow!
    March 24, 2025 at 12:54 am - Reply
    paul_n
    Misha: One of the main reasons that I pursued this particular Senior Project was because I wanted to connect my strong knowledge base in calculus with other fields of mathematics that I am much weaker in, so this is the field that I am most looking forward to connecting with other topics. In learning this proof for the Fibonacci sequence, I was both able to use my knowledge of Taylor series from calculus to complete the proof AND I was able to learn about the usefulness of generating functions in finding the general formula for an unknown Taylor series, so I have expanded my knowledge of both calculus and sequences. This is ideally what I want to do for every field that I study during my Senior Project.
    March 25, 2025 at 4:22 pm - Reply

Leave a Reply

Your email address will not be published. Required fields are marked *