Why does this fraction give the Fibonacci sequence? It’s no coincidence

You may have seen one of the following viral math facts:

The first fraction seemingly gives the Fibonacci numbers. That is, the sequence of numbers that starts with 1, then 1, then each successive term is the sum of the two prior terms. So the first few Fibonacci numbers are 1,1,2,3,5,8,13,21,… Which appear on the decimal expansion of the first fraction!

The second fraction is clearer, it gives us the natural numbers in order. Finally, the third fractions gives us the square numbers, 1²=1, 2²=4, 3²=9 and so on.

Do these fractions give all Fibonacci, natural, and square numbers? Unfortunately, no. If you were to continue this fractions, you will not get more elements of the sequence with more than two digits, and eventually those decimal expressions will start repeating themselves anyway.

So what’s going on? Is this just a coincidence some bored nerd found? Is this the result of devious math goblins? Is this just a lie that Big Math ™ told us so they could sell us more math? Was it all three at once?

Well, spoiler alert, no. This is actually one result of a useful and intriguing concept in mathematics called generating functions. Using them, we can generate a lot more of these types of fractions, this post will give you tools to do this very thing. Before we dive in on what exactly that means, let’s first look more closely at those decimal expansions.

A closer look

We will start with the first fraction, that which gives the Fibonacci numbers:

Let’s rewrite it a bit, splitting it to groups of two decimal digits:

And a little bit more, this time getting rid of the decimals, and instead using fractions and powers of 100. This is much nicer than decimals and will give us a more generalized understanding later

Almost there! Now denote F_n to be the n-th Fibonacci number. We can at last rewrite this as the following:

Although our fraction only gives two digit Fibonacci numbers, we will continue this pattern for all Fibonacci numbers. That is, we will sum F_n divided by 100ⁿ for all natural n. As we will see later, this will indeed give us our original fraction. So we are left with the following infinite sum:

(Similarly, we can rewrite our two other fractions in the same way)

Now how exactly does this help us? Well, this is where generating functions come in

What are generating functions?

Our three sums from before have something in common: they all have 1/100 raised to the n-th power. Now, what happens if we replace 1/100 with another number? Well, first we got to be careful, if we say put in 2, we end up with a diverging sum. However, we still can for example put in a number x, so long as it is small enough. For our purposes, x with an absolute value strictly less than one will do the trick. So we end up with the following three functions:

You can probably tell where this is going. These are all called the generating functions of their respective sequences. All of them follow the same pattern of a sum from 0 to infinity of something times xⁿ. In general, we define the generating function of a sequence a_n by the sum of a_n times xⁿ as n ranges from 0 to infinity:

Generating functions are surprisingly very useful in a variety of problems, but for the purposes of this post we will look at how they can generate the fractions we saw before. A future post perhaps might go into how they can help in counting (combinatorical) problems. As stated before, these sums do not always converge. For our use in this post, the particular sums we will be looking at will indeed converge for x between -1 and 1. Those of you familiar with what a power series is, you can check for yourself that in our uses the sums indeed converge.

Now, say we have the generating function of a sequence of positive integers, a_n. If we put in say x=0.1, if the sum converges the first few terms of the sum will be the one digits terms of a_n in order (remember how we wrote the decimals before). If we put in x=0.01, we will get a decimal expansion that starts with the 2 digit elements of a_n. If we put in x=0.001, we get three digits and so on.

So if we know how to calculate the generating function of a_n at any value, and the result is in a form of a fraction when we put in rational values, we can generate fractions which give a_n when written as decimals.

Only one problem though, how do we calculate the generating functions?

(Assuming you do not have a math goblin to do that for you)

Calculating the generating functions

To easily calculate a generating function in a specific value, we need to find a closed form of the generating function. What this means is we want to write the generating function not as an infinite sum, but a simpler function we can easily compute, say a polynomial or a division of two polynomials.

Let’s look at an example of this. Look at the generating function of the constant sequence 1:

A lot of you will recognize this as a geometric sum. It converges only for x with an absolute value less than 1, and the formula for it is:

(For those unfamiliar with this fact, there are lots of wonderful proofs of it on the web, here is one of them)

So we obtained a closed form of the sum, which we can now calculate for a given x.

Okay, let’s move on to a more complicated example, the generating function for a_n=n+1. Although it is a bit different from what we said before, it will still give us a fraction with a decimal expansion that has the natural numbers in order:

Wait, before we go any further, a warning. A lot of the steps we do here are not 100% formal, and do require more rigorous explanation to explain why they are possible. We will skip these explanations as they are not very important for our discussion and the techniques we use are valid regardless.

Look at the expression (n+1)xⁿ. If it looks familiar, it’s because it is the derivative of xⁿ⁺¹! So, in a move that will probably trigger some mathematicians, let’s integrate each term in the sum:

Notice now that when we calculate the integrals inside the sum, we go back to the geometric series!

So, if we take the derivative of each side, we will get a closed form for our generating function from the start:

Now we can calculate the value of the generating function at any x with ease! In particular, for the case we cared about from before, x=1/100, inputting it in the function on the right gives 10,000/9801=1.02030405… That is almost what we had in the beginning except a factor of 10. Similarly, should we input 1/1,000 instead, we will get 1,000,000/998001, which if you recall from before, will give us a decimal with all three digit or less natural numbers, that is 1.002003004…..

Note now, if we take the derivative for the generating function of n, we get that each term in the sum is n² times x^n-1. So, that is the generating function of (n+1)². So if we know a closed form of the generating function for n, which we can easily deduce from our previous example, we can get a generating function for (n+1)² (e.g the square numbers). That allows as to get the decimal with the square numbers as its digits

That’s two of our fractions taken care of. So what about the Fibonacci numbers? Well that will be a bit more tricky. We do not have a nice general formula for Fibonacci numbers which will lead us, say, to the geometric sum like before. Instead, we will make clever use of the recursive definition of the Fibonacci sequence

Generating function of the Fibonacci sequence

Finding out what the generating function of the Fibonacci unlike before will not require derivatives and integrals. Instead, we can find it algebraically in a couple of beautifully clever steps. First of all, let’s remember how the Fibonacci sequence, F_n, is defined. (For the purposes of this discussion, n starts at 0)

That is, the first two elements are 1, and after that each element is equal to the sum of the two previous ones. This is called a recursive definition, a definition where later terms of the sequence are defined by previous ones. We seek to find a closed form for the generating function:

Here is the idea for how to evaluate this expression. We will split the terms F_n in the sum to the sum of the two previous elements. Then, we get a sum of two series, which we will try to rewrite using G(x). Finally, we will solve for G in terms of x and thus get our function.

Onward to the first step! Note that we need to deal with the first two terms separately as they have their own definition:

The sum at the top right starts at 2 as we took out the first two terms. Then for ease we shifted the sum to start instead at 0 but go over indexes n+2. Now we can rewrite F_n+2 as the sum of the two previous terms:

Almost there! The two sums at the bottom are almost like the generating function, but they have terms xⁿ⁺² instead of xⁿ. We can get rid of that by taking the unnecessary powers of x out of the sum:

Finally, we rewrite all of this in terms of G(x). The first sum at the bottom row goes over n+1 and not n, so we will need to get rid of the 0th term in G(x). In other words, we write G(x)-1 and not G(x) there:

Remember, all of this was equal to G(x), so we now get an equation only in terms of G and x:

Finally, we solve for G(x), and get that generating function of the Fibonacci numbers is:

Q.E.D

Now do it yourself!

So hopefully this post made it clearer how you get these fractions at all. In fact, try to come up with a fun fraction yourself! Choose a sequence of integers, say cubes of natural numbers or powers of two, or even one defined recursively. Try to compute it’s generating function and use it to find a fun fraction whose decimal expression gives that sequence. If you feel like it, comment with your result!

Alternatively, you can just google the generating function for the sequence you chose…. Even better, you can ask one of those math goblins if you have one