Fractions with Special Digit Sequences
This page discusses fractions whose decimal expansion has a nice pattern or a recognizable sequence. Some oft-seen examples include:
1/99 = 0.0101010101...
1/998 = 0.001 002 004 008 016 032 064... (the powers of 2)
1/9801 = 0.0001020304...
1/9899 = 0.00 01 01 02 03 05 08 13 21 34 55... (Fibonacci numbers)
I follow my own personal history with these numbers, and explain how to find the fraction for a given sequence, including much of the "dark art" of generating functions.
Contents
A Simple Way to Find a Magic Fraction
A More Fundamental Understanding
Working It Out Through Algebra
Through the Looking Glass: Generating Functions
The Lucas Numbers: Generating Function from Polynomial Arithmetic
Using Bitwise Binary Operations
Generating Functions Through Derivatives
Preface
For many years I was unable to use "generating functions" because, in all the instructional material on the topic, nobody gave an algorithm that takes the generating function as input, and produces the terms of the integer sequence as output. I gave up, considering the G.F. to be worthless if it could not actually be used to generate the sequence. If a writer had bothered to mention Taylor series, or to explain that I should consider successive derivatives of the function evaluated at x=0, I would have understood immediately.
This page attempts to counteract Munafo's Laws of Mathematics by approaching generating functions by starting with a phenomenon that is familiar to most folks who play with numbers long enough: nifty repeating digit patterns.
Outline
I explain how I stumbled across a few of the simpler fractions like the examples shown above, then show how one can easily discover such fractions by computing, for example, "1/0.001003006010015021028" to discover that 1/997002999 gives the triangle numbers.
I then do an analysis of the 1/89 Fibonacci property in other bases, to show that it's always 1/(b2-b-1). The insight that b can be exchanged with 1/x shows that our fractions are just an infinite polynomial (a power series) evaluated very close to 0. This serves as the conceptual bridge to generating functions.
I then go into a cookbook-style presentation of examples showing how to use algebra on power series to find the generating functions (and thus, the fractions) for many types of sequences; later examples also use simple calculus (derivatives). Examples also make use of the online resources Wolfram Alpha and The Online Encyclopedia of Integer Sequences.
The magic of 1/7
Some fractions can be written exactly with a finite number of digits (a "terminating decimal"): 1/2 = 0.5, 1/4 = 0.25. Others go on forever (a repeating decimal): 1/3=0.333333..., 1/6=0.166666... All of these can be said to be fairly "simple".
The smallest number that doesn't give a simple fraction is 7:
1/7 = 0.142857142857... 4/7 = 0.571428571428...
2/7 = 0.285714285714... 5/7 = 0.714285714285...
3/7 = 0.428571428571... 6/7 = 0.857142857142...
I have highlighted 6 digits in each of these to show the "magic" property of 1/7: All of these fractions have the same set of 6 digits in the same order. They differ only in which of the 6 digits comes first.
If you consider the process of long division, you will see that 6 is the most number of digits that any of these fractions could have. Consider 1/7 for example:
10/7 is 1 with a remainder of 3,
30/7 is 4 with a remainder of 2,
20/7 is 2 with a remainder of 6,
60/7 is 8 with a remainder of 4,
40/7 is 5 with a remainder of 5, and
50/7 is 7 with a remainder of 1.
The remainder must be a number from 0 to 6, because we're dividing by 7 and the remainder is always smaller than the divisor. The remainder cannot be 0 because that would make a terminating decimal, and no number has a terminating decimal unless its prime factorisation is all 2's and 5's. So there can only be 6 different remainders in a long division when dividing by 7, and 1/7=0.142857 uses all 6 of them.
In general, the repeating decimal of a number 1/N must repeat every N-1 digits, or fewer. The numbers N for which it is the maximum N-1 digits are called "primes P with 10 as a primitive root", or primes P such that 10 is a primitive root modulo P. The next one after 7 is 17, because 1/17 has a 16-digit repeating decimal:
1/17 = 0.05882352941176470588235294117647...
After 7 and 17, we have 19, 23, 29, 47, 59, 61, 97, and so on (Sloane's sequence A1913).
The Simplest Sequences
An integer sequence can be as simple as the "all zero sequence" A0004: 0,0,0,0,0,... or as elusive as A2410 related to the unsolved Riemann hypothesis: 14, 21, 25, 30, 33, 38, ...
In repeating decimals the simplest sequence is the "all 1's sequence" A0012: 1,1,1,1,1,1,1,1,... This is the repeating decimal of 1/9: 0.11111111... Those who experiment with a pocket calculator usually try 1/99 and discover it has a similar decimal expansion: 0.0101010101... We're essentially doing the same thing in "base 100". Base 100 would be just like base 10 except that it uses 100 "digits" going from 00 to 99. Imagine doing 1/99 as a long division problem with the digits paired up:
00.01 01 01 ... ________________ 99 ) 01.00 00 00 - 99 ------- 01 00 - 99 -------- 01 00 - 99 -------- (etc.)Unsurprisingly, 1/999 is 0.001001001... and so on.
With enough curiosity and/or free time, one might try looking at all fractions of the form 1/N. This soon reveals other 6-digit repeating decimals related to 1/7 and 1/13 (including 1/21 = 0.047619047619... and 1/39 = 025641025641...) and the 2-digit patterns related to 1/11 (like 1/22 = 0.04545454545...). Also of interest are 1/27 = 0.037037037... and 1/37 = 0.027027027... (see my numbers pages entry for 999). Probably the most interesting of these are 1/49 = 0.02 04 08 16 32... (which we will get to later) and 1/81 = 0.0123456790123456790...
The digits of 1/81 are almost like the non-negative integers (A1477) but 8 is missing, and of course it goes from 9 back to 0 (no 10, 11, etc.). But actually 8 is there, and 10 and the higher integers are there too. To see them, we have to visualise 1/81 as a sum like this:
0.0 0.01 0.002 0.0003 0.00004 0.000..5 0.000...6 0.000... 7 0.000... 8 0.000... 9 0.000... 10 0.000... 11 0.000... 12 0.000... 13 0.000... 14 ... ... ... + 0.000... ... ---------------------------- 0.01234679012345679012...Each integer is shifted one digit further to the right, so the 9 and 10 add up like "90+10" generating a carry that adds to the 8, making a 9 in the digit after ...567.
I first noticed (on a pocket calculator) that 1/9 is 0.11111111... and the obvious thing (obvious to me anyway) was to try dividing this by 9, and I got 0.0123456790123...
Since 81 is 92, one might think of looking at the reciprocal of 992. You get a pleasant result:
1/9801 = 0.0001 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27...
Here we have the integers again, but there is enough room for 9, 10, 11, and all two-digit numbers up to 98 to appear intact. As you might expect, 1/998001 gives 0.000001 002 003 004 005..., with 3 digits for each integer.
The Fibonacci Reciprocals
I learned about the above from books and my own experimentation on a pocket calculator. A little while later, perhaps in high school I read about 1/89 = 0.011235955...
89 is a Fibonacci number, and the digits of 1/89 start with the first few Fibonacci numbers: 0, 1, 1, 2, 3, 5. The rest of the digits are Fibonacci numbers too, added together like this:
0.0 0.01 0.001 0.0002 0.00003 0.000..5 0.000...8 0.000...13 0.000... 21 0.000... 34 0.000... 55 0.000... 89 0.000... 144 0.000... 233 0.000... 377 ... ... ... + 0.000... ... ---------------------------- 0.01123595505617977528...The fact that 89 itself is a Fibonacci number is a happy coincidence, which we'll investigate further below. Just like with 1/9801 and 1/998001, there are longer versions of the "Fibonacci reciprocal":
1/9899 = 0.0001 01 02 03 05 08 13 21 34 55...
1/998999 = 0.000001 001 002 003 005 008 013 021 034 055 089 144 233 377...
How did I find those? I could try a bunch of things on a calculator to see what seems to give the right answer, but there are much more direct ways to do it.
A Simple Way to Find a Magic Fraction
The connection between 89 and these longer numbers 9899 and 998999 might be obvious, but suppose we didn't know it? They could be found pretty easily just by assuming that there is a "Fibonacci fraction" and performing the division in reverse:
1/0.0001010203050813213455 = 9899.00000000000000886455...
We can use the same trick to find other magic fractions. The Fibonacci numbers are an exponential sequence; how about a fraction that gives us the powers of 2?
1/0.01020408163264 = 98.000000000125...
It looks like 1/98 would give us the powers of 2. Similar experiments show that 1/998, 1/9998 and so on also work. Each of these gives more powers of 2 (assuming you have a high-precision calculator to get lots of digits), making it pretty clear it is not just a coincidence.
Since 1/8 is also of the form 1/(10N-2), its digits should also be the powers of 2. And in fact, 0.1 + 0.02 + 0.004 + 0.0008 + 0.00016 + 0.000032 + ... = 0.125 exactly.
Similarly, for the powers of 3:
1/0.0103092781 = 97.00000235...
and similar calculations show that 1/(10N-3) will have the powers of 3 in its digits, for example 1/97:
1/97 = 0.01 03 09 27 83...
It would seem that the very first fraction we looked at, 1/7 = 0.142857142..., also gives the powers of 3. To see it you can do this:
0.1 0.03 0.009 0.0027 0.00081 0.000243 0.00..729 0.00..2187 0.00...6561 0.00...19683 ... ... + 0.000... ... ----------------- 0.142857142...Polynomial functions like the triangle numbers (x2+x)/2 (OEIS sequence A0217) seem to be likely candidates for this sort of analysis.
1/0.001003006010015021028 = 997.00299900000000003582...
suggests 997002999 as a possible denominator, and indeed
1/997002999 = 0.000000001 003 006 010 015 021 028 036...
This doesn't work all the time. If you try it with the odd numbers 2x+1:
1/0.001003005007009011013015 = 997.0039960039960039960...
it's clear we have a repeating decimal, so the desired fraction has something other than 1 in the numerator. In this case we can use a new trick: adding two sequences together. If we already know that 1/998001 gives the integers starting from 0 as 0.000001002003004005006..., then 1000/998001 shifts the decimal point over 3 places, to give the integers starting with 1: 1000/998001 = 0.001002003004005006007... Since the odd numbers are of the form x + (x+1), we can add these together:
|
A More Fundamental Understanding
Returning to the first Fibonacci example 1/89, I wondered if there were a "fundamental reason" why it is 1/89 and not some other fraction. A simple experiment is to use the simple test to find the "Fibonacci fraction" in other bases. We use base 10, but there must be Fibonacci fractions in other bases. Using something like the Unix program bc, it is easy to do calculations in any base. Fairly easily I found that:
in base 5, the Fibonacci fraction is 1/19 = 0.0112...5
in base 6, it is 1/29 = 0.0112...6
in base 7, it is 1/41 = 0.01123...7
in base 8, it is 1/55 = 0.01123...8
in base 9, it is 1/71 = 0.01123...9
in base 10, it is 1/89 = 0.011235...
and so on. It soon became clear that
in base b, it is 1/(b2-b-1) = 0.0112358...b
So the special thing about 89 is that it is 100-10-1.
Another fact that became clear through similar experiments was that the fractions b/(b2-b-1) and b2/(b2-b-1) work equally well. For example in base 10 we have 100/89 = 1.1235... which is just the same digits with the decimal point shifted over.
It's nice to have an explanation for the "89 coincidence" and see that the same fractions happen in other bases than decimal, and there is a similar "55 coincidence" for base 8. But there remains the question of what the relationship is between the Fibonacci sequence and the fractions 1/(b2-b-1), b2/(b2-b-1), etc.
Working It Out Through Algebra
Let's use "base 100", which is just base 10 taken two digits at a time. We already know the answer is 1/9899 or 100/9899 or 10000/9899, but let's imagine we don't know this and try to find the fraction from its "Fibonacci decimal expansion". We'll use N to refer to the unknown numerator, and D to refer to the denominator:
N/D = 0.01 01 02 03 05 08 13 21...
Dividing by 100 will give us the same thing shifted 2 digits to the right:
N/100D = 0.00 01 01 02 03 05 08 13...
Multiplying by 100 will give us the same thing shifted 2 digits to the left:
100N/D = 1.01 02 03 05 08 13 21 34...
We also know (from the definition of Fibonacci numbers) that we can subtract two Fibonacci numbers and get another Fibonacci number. So we can subtract N/D from 100N/D and get:
99N/D = 1.00 01 01 02 03 05 08 13...
the thing on the right is just 1 plus N/100D. So we can write:
99N/D = 1 + N/100D
N/D is a fraction, and like any fraction we get the same value by multiplying the numerator and denominator by any arbitrary number (for example, 1/2 = 3/6 = 7/14, and so on). So we really don't need two variables N and D, it's just their ratio we're trying to find. It will help to try to get one in terms of the other.
First get everything over the same denominator:
9900N/100D = (100D + N)/100D
Multiply by 100D:
9900N = 100D + N
Combine the N's:
9899N = 100D
Dividing both sides by D, then by 9899, gives us the ratio N/D:
N/D = 100/9899
which of course is the fraction and decimal we started with:
N/D = 100/9899 = 0.01 01 02 03 05 08 13 21...
A Proof For Any Base
The previous example was for base 100, but it doesn't have to be just for a specific number base. We can do the same thing in any base b.
Using F0, F1, F2, F3, etc. to represent the Fibonacci numbers 0, 1, 1, 2, ..., we start with
N/D = F0.F1F2F3F4F5F6F7F8...
and we can work through the entire solution as above. "100" is b, "99" is b-1, "9900" is b2-b, and "9899" becomes b2-b-1. We end up with the answer:
N/D = b/(b2-b-1) = F0.F1F2F3F4F5F6F7F8...
It will also be useful to multiply both sides by b2, or equivalently by 1/b-2. This gives us
Nb2/D = b/(1-b-1-b-2)
Through the Looking Glass: Generating Functions
Let's convert the symbolic digits "F1.F1F2F3F4F5F6..." into what they really represent, using the standard definition of positional notation (also called "place value"):
F0.F1F2F3F4F5F6...
= F0 + F1b-1 + F2b-2 + F3b-3
+ F4b-4 + F5b-5 + F6b-6 + ...
This is a sort of "polynomial" with negative exponents. Let's put this into the solution we worked out above, for any base b:
b/(b2-b-1) = F0 + F1b-1 + F2b-2 + F3b-3 + F4b-4 + F5b-5 + F6b-6 + ...
Those negative exponents are a bit odd. But b is a variable, so we can change it. The nice thing about variables is that they can have values that wouldn't be convenient to work with directy.
What if the "base" is something small, like 1/10 or 1/100? We don't normally think of numbers as being in "base 1/100", but with a variable b and Fi for all the "digits", it doesn't really matter. Let's define x = 1/b, then we can turn all the negative exponents on the right-hand-side into positive powers of x. The left side has to change too, so we get:
x-1/(x-2-x-1-1) = F0 + F1x + F2x2 + F3x3 + F4x4 + F5x5 + F6x6 + ...
The part on the right is called a power series. We don't want any negative exponents. It's easy to get rid of the negative powers of x on the left-hand-side: just multiply by x2/x2:
x/(1-x-x2) = F0 + F1x + F2x2 + F3x3 + F4x4 + F5x5 + F6x6 + ...
We now have something that might be familiar to some readers, who may have learned about Taylor series approximations. The thing on the right is an infinite polynomial in x with coefficients F0, F1, F2 and so on. The thing on the left is a function of x (that's not just a normal polynomial).
If this is true, then the Fibonacci numbers are the coefficients of the Taylor series expansion of x/(1-x-x2). Let's see if this is true. Using the excellent website Wolfram Alpha, put this into the box:
Series[x/(1-x-x^2), {x,0,8}]
You'll get:
x + x2 + 2 x3 + 3 x4 + 5 x5 + 8 x6 + 13 x7 + 21 x8 ...
where the coefficients of x are the Fibonacci numbers. What Wolfram Alpha is telling us is that for values of x near 0, the value of this (infinite) polynomial is close to the value of 1/(1-x-x^2). For example if x=0.2, x/(1-x-x2) is about 0.263157... and the first part of the polynomial (x+x2+2x3+3x4+5x5+8x6) adds up to 0.262912.
Since we defined x to be 1/b, where b is the base of the decimal fraction, let's go back to our original b=100 fraction. That means x is 1/100 or 0.01.
Putting 0.01 in for x, you can see that:
x/(1-x-x2) = 0.01/(1-0.01-0.0001) = 0.01/(0.9899) = 100/9899
There's our fraction 100/9899, the same that we worked out with algebra, and the same that we originally guessed by from putting 1/0.0001010203050813213455 into a calculator.
Going back to the original base 10, let x be 0.1, and we get:
x/(1-x-x2) = 0.1/(1-0.1-0.01) = 0.1/(0.89) = 10/89
10/89 is 0.112359..., which is the same as 1/89 shifted over 1 digit.
More Examples of Series Expansions and Repeating Decimals
Here's another example. We'll use Wolfram Alpha again, and give it a request in plainer language:
Taylor series for 1/(1-x)
You get the polynomial:
1 + x + x2 + x3 + x4 + x5 + O(x6)
(Taylor series converges when |x|<1)
The coefficients are the "all 1's sequence" A0012: 1,1,1,1,1,1,1,1,... which is the repeating decimal of 1/9, mentioned above. The last bit "O(x6)" means that all other terms are x6 or higher powers of x. There is a small note to remind you that this works only when x is close to zero, which is the case for all of our examples: In base 10, b = 10 and x = 1/b = 0.1.
So the value of 1/(1-x) is 1/(1-0.1) = 1/0.9 = 10/9. For base 100, we let x = 0.01 and we get 1/(0.99) = 100/99 = 1.0101010101...
If we use 1/(1-2x) instead:
Series[1/(1-2x), {x,0,8}]
we get:
1 + 2x + 4x2 + 8x3 + 16x4 + 32x5 + 64x6 + 128x7 + 256x8 + . . .
where the coefficients are A0079, the powers of 2. Predictably, if we set x = 1/b = 0.01, the value of 1/(1-2x) is 1/0.98 = 100/98 = 50/49. We can subtract 1 = 49/49 to get the simple fraction mentioned near the beginning of this article, 1/49 = 0.02 04 08 16 32...
If 1/9 is 0.111111... and 1/81 is 0.0123456..., you might guess that the sequence of positive integers A0027 comes from 1/(1-x)2, and you'd be right:
Series[1/(1-x)^2, {x,0,8}]
1 + 2x + 3x2 + 4x3 + 5x4 + 6x5 + 7x6 + 8x7 + 9x8 + . . .
using x = 1/b = 0.01, 1/(1-x)^2 is 1/0.9801 = 10000/9801 = 1.02 03 04 05 06 07... The decimal is shifted 4 digits as compared to the original example 1/9801.
To get the even numbers A5843 we can just double the fraction that gives us the positive integers: 20000/9801 = 2.04 06 08 10 12 14...
Similarly, for multiples of 3 we just use 30000/9801 = 3.06 09 12 15 18 21... 9801 is a multiple of 3, so this one can be reduced to 10000/3267.
Here is a less obvious example:
Series[x*(1+x)/(1-x)^3, {x,0,8}]
x + 4x2 + 9x3 + 16x4 + 25x5 + 36x6 + 49x7 + 64x8 + . . .
This is sequence A0290, the squares. Using x = 0.01 again, the fraction is x(1+x)/(1-x)3 = 0.0101/0.970299 = 10100/970299 = 0.01 04 09 16 25 36...
If you do a Taylor (or Maclaurin) series expansion of a function F(x) and get a sequence of coefficients Si, then F(x) is said to be the "generating function" of the sequence Si.
The application of generating functions specifically to decimal expansions of fractions is discussed by Smoak [1] using the Fibonacci fractions 1/89, 1/9899, etc. and explaining them in terms of the generating function 1/(1-x-x2). (This differs from the more commonly accepted generating function x/(1-x-x2); this is directly related to the fact that Smoak defines F0=1, F1=1, F2=2, and so on; while the standard Fibonacci definition (see OEIS A0045) starts with F0=0, F1=1, F2=1.)
Reversing the Process
We have now established that:
- If Si is a sequence of integers, and
- If b is the base (usually a power of 10, like 100 for the case of 2 digits per number), and
- If x is 1/b, and
- If F(x) is a function in x (such as a ratio of polynomials), and
- If the Taylor series expansion for F(x) is F(x) = S0 + S1x + S2x2 + S3x3 + ...
- Then the fraction represented by the value of F(x)=F(1/b) will have the members of the sequence Si in its decimal expansion.
What remains is to find a way of converting any sequence Si into the "generating function" F(x) that we can use to find the fraction.
This task can be very difficult, and there is no general solution that will work for all sequences, or even for all well-defined sequences. There is no generating function for the prime numbers, for example.
There are specific rules for certain types of sequences. From the above examples you can see that 1/(1-Nx) gives the powers of N, and N/(1-x)2 gives the multiples of N. The rule that generalises N, N2, N3 and so on uses Eulerian numbers, which aren't particularly obvious but at least have been figured out.
The Lucas Numbers: Generating Function from Polynomial Arithmetic
Mishima [3] uses the Lucas numbers in an example showing how to find the generating function for a sequence. We start with just the sequence:
Li = 2, 1, 3, 4, 7, 11, 18, ... (OEIS A0032)
and the recurrence relation definition:
Ln = Ln-1 + Ln-2
Make the sequence into a polynomial with each Ln as a coefficient of xn:
Li = 2 + x + 3x2 + 4x3 + 7x4 + 11x5 + 18x6 + ...
Perform algebraic transformations on this, such that the definition of the sequence can be invoked to cancel out the infinite series of powers of x. In this particular case we can multiply by x and by x2. The purpose is to shift the coefficients over to higher powers of x:
x Li = 0 + 2x + x2 + 3x3 + 4x4 + 7x5 + 11x6 + ...
x2 Li = 0 + 0x + 2x2 + x3 + 3x4 + 4x5 + 7x6 + ...
Line up the original and the transformed versions so that all powers of x are above one another:
|
Now the definition of the sequence can be used to make most of the terms cancel out. For any given n, we have Ln-1 and Ln-2 in the same column as Ln. Since Ln = Ln-1 + Ln-2, subtracting the second and third row from the first row will usually give 0. For example, in the x3 column we get 4x3-3x3-x3 = 0. All that remains is:
Li - xLi - x2Li = 2 + x - 2x = 2 - x
Solve for Li:
(1-x-x2) Li = 2-x
Li = (2-x) / (1-x-x2)
Now we have a generating function for the Lucas numbers. This can be verified directly by typing Series[(2-x)/(1-x-x^2),{x,0,8}] into Wolfram Alpha, or by making a fraction by setting x to 0.01:
x=0.01
(2-x)/(1-x-x2) = 1.99/0.9899
= 19900/9899 = 2.01 03 04 07 11 18 29...
If you compare this to the process I used above for the Fibonacci numbers, you can see that the manipulation of decimal fractions, like computing 1.0102030508132134... - 0.0101020305081321..., was essentially the same technique.
Using Bitwise Binary Operations
An unusual formula for generating Fibonacci numbers is:
Fn = (4 << n*(3+n)) / ((4<<2*n)-(2<<n)-1) mod (2<<n)
In this formula the division is "integer division", i.e. a/b = Floor[a/b], and the unusual operator "<<" is bitwise shift, which is merely the multiplication of an integer by 2i for some natural number i. The numbers being shifted are powers of 2, so the formula is equivalent to:
Fn = Floor[2n2+3n+2 / (22n+2-2n+1-1)] mod (2×2n+1)
The formula is effectuvely computing 1/(1-x-x2) with x equal to 2n+1, which is always larger than Fn. It uses "integer division" to discard the less-significant digits (containing Fn+1 and later Fibonacci numbers) and using the mod relation to throw out the higher digits (containing Fibonacci numbers F1 through Fn-1).
It is not particularly practical because you need a lot of binary digits to calculate a Fibonacci number this way. If integers are 64 bits, then when n is as small as 7, n2+3n+2 is big enough that the calculation would overflow.
Polynomial Division
Polynomials can be divided by one another by a method much like long division. Here is a traditional long division problem, dividing 10 by 89:
0 0.1 1 2 3 5 ... ________________ 89 ) 1 0.0 0 0 0 0 - 8 9 ------- 1 1 0 - 8 9 -------- 2 1 0 - 1 7 8 -------- 3 2 0 - 2 6 7 -------- 5 3 0 - 4 4 5 -------- (etc.)As discussed above, fractions like 10/89 or 100/9899 can be thought of as a polynomial fraction x/(1-x-x^2), where x is a negative power of 10, like 1/10 or 1/100.
So let's try long division on polynomials! Because x is very small (close to zero), 1 is bigger than x which is bigger than x2, so it makes sense to think of 1 as the "biggest digit of the divisor", and when computing the quotient, we'll start with the constant term, then the x term, then the x2 term, and so on.
Consider the Li we just computed above as a ratio 2-x (the dividend) divided by 1-x-x2 (the divisor) :
2 + x +3x^2 +4x^3 +7x^4 + ... ______________________________________ 1-x-x^2 ) 2 - x 2 -2x -2x^2 ------------ x +2x^2 x - x^2 - x^3 --------------- 3x^2 + x^3 3x^2 -3x^3 -3x^4 ----------------- 4x^3 +3x^4 4x^3 -4x^4 -4x^5 ------------------ 7x^4 +4x^5 7x^4 -7x^5 -7x^6 ------------------ 11x^5+11x^6 (etc.)There are the Lucas numbers in the coefficients of the quotient: 2 + 1x + 3x2 + 4x3 + 7x4 + ...
If we think of x as being larger than 1, then we would set up the long division like so:
x^-1 -3x^-2 +4x^-3 -7x^-4 ------------------------------------- -x^2-x+1 ) -x +2 -x -1 + x^-1 ------------- 3 - x^-1 3 3x^-1 -3x^-2 ----------------- -4x^-1 +3x^-2 -4x^-1 -4x^-2 +4x^-3 ---------------------- 7x^-2 -4x^-3 7x^-2 +7x^-3 -7x^-4 --------------------- -11x^-3 +7x^-4 (etc.)Here the coefficients are 1, -3, 4, -7, ... and obey the relation: An = An-2 - An-1. Continuing the sequence, we get: 1, -3, 4, -7, 11, -18, 29, -47, 76. It's like the Lucas numbers but with alternating signs.
A curious thing happens if we subtract one quotient from the other:
2 + x + 3x2 + 4x3 + 7x4 + ...
- ( x-1 - 3x-2 + 4x-3 - 7x-4 + ... )
= ... + 7x-4 - 4x-3 + 3x-2 - x-1
+ 2 + x + 3x2 + 4x3 + 7x4 + ...
Combining the polynomials in this manner we get an integer sequence that is infinite in both directions: the Lucas numbers extended to negative indices:
..., 47, -29, 18, -11, 7, -4, 3, -1, 2, 1, 3, 4, 7, 11, 18, 29, 47, ...
This "extended" sequence obeys the same rule as the original: for all n, An = An-1 + An-2. The only difference is that now n can be any integer, not just a positive integer.
Generating Function Methods
In this section I summarise several techniques for taking an integer sequence with a known closed-form formula and deriving a generating function for it. Several new integer sequences will be used as examples.
Powers of N
For powers of x, the same polynomial arithmetic method may be used. Take the powers of 2 for example:
Pi = 1 + 2x + 4x2 + 8x3 + 16x4 + ...
2x Pi = 0 + 2x + 4x2 + 8x3 + 16x4 + ...
Pi - 2x Pi = 1
(1 - 2x) Pi = 1
Pi = 1/(1-2x)
The similar method works for the powers of 3 giving 1/(1-3x) and so on.
Powers of 1 (the All-Ones Sequence)
By the same method, the "powers of 1" are easily shown to be 1/(1-x), which will be useful elsewhere.
Adding Two Sequences
Two generating functions can be directly added together to get the generating function of a sequence that is the sum of two other sequences. So the sequence 2, 3, 5, 9, 17, 33, ... which is 1 plus the powers of 2, has the generating function:
1/(1-x) + 1/(1-2x)
To add these together we can convert both fractions to the same denominator, which gives (1-2*x)+(1-x)/((1-x)(1-2x)) = (2-3x)/(1-3x+2x2). If x=0.01 we get 1.97/0.9702 = 19700/9702 = 2.0305091733...
Generating Function for the Integers
To derive the generating function for A0027 = 0, 1, 2, 3, 4, 5, ... requires the addition rule. Let Oi be the all-ones sequence with generating function 1/(1-x), and Ii be the sequence of integers.
Ii = 0 + x + 2x2 + 3x3 + 4x4 + 5x5 + ...
x Ii = 0 + 0x + x2 + 2x3 + 3x4 + 4x5 + ...
Oi = 1 + x + x2 + x3 + x4 + x5 + ...
We subtract xIi and Oi from Ii to get:
Ii - x Ii - Oi = -1
and we can substitute the generating function for Oi which we already know to be 1/(1-x):
(1-x) Ii - 1/(1-x) = -1
(1-x) Ii = 1/(1-x) - 1 = (1-(1-x))/(1-x) = x/(1-x)
Ii = x/(1-x)2
To get a fraction we can use x = 0.01, so x/(1-x)2 = 0.01/0.9801; shifting the decimal points in numerator and denominator gives
100/9801 = 0.01 02 03 04 05 06 07...
Since the "(1-x)" part is being squared, we can also use (x-1), which makes a bit more sense if x is a power of 10: x = 100 gives x/(x-1)2 = 100/992 = 100/9801.
Multiplication by a Constant
The even numbers are just 2 times the integers, and the generating function for them is just 2 times the generating function for the integers:
2x/(x-1)2
Again using x=100, we get the rational fraction:
200/9801 = 0.02 04 06 08 10 12 14...
The numerator is not 1 or another power of 10, but if we want it to be a power of 10, we can simply multiply by 5/5 to get 1000/49005, and so:
1/49005 = 0.00002 04 06 08 10 12 14...
For the multiples of 3 we just take our x/(x-1)2 and multiply by 3 instead of 2:
3x/(x-1)2
Using x=100 to get a rational fraction, this is
300/9801 = 0.03 06 09 12 15 18 21...
It is not in reduced form, but 9801 is divisible by 3, so 300/9801 can be reduced to 100/3267, and then
1/3267 = 0.0003 06 09 12 15 18 21...
I'll give one more example for the multiples of 7. The generating function is
7x/(x-1)2
As always x needs to be a power of 10; let's also set it up so we can reduce the fraction. That means we want x-1 to be a multiple of 7. That works when x is 106, so the multiples of 7 are given by
7000000/999998000001 = 0.000007 000014 000021 000028...
The numerator and denominator can both be divided by 7, and then the whole thing divided by 1000000, to get
1/142856857143 = 0.000000000007 000014 000021 000028...
How did I know to use 106? I could have checked all values of 10n-1 to find one that is a multiple of 7, but in this case I knew 6 would work because 1/7 = 0.142857 has a 6-digit repeating decimal. These facts are related, and you can see why: the repeating decimal with a 6-digit cycle means that if you do long division to compute 1000000/7, you'd get some string of 6 digits (142857 to be exact) as the quotient with 1 left over; therefore 1000000-1 must be a multiple of 7.
The techniques in the previous three examples can be combined to find a number of the form 1/N whose reciprocal's digits give the multiples of any desired positive integer. For example, to get the multiples of 82 we start with 82/9992 (cannot reduce) -> 82/999992 = 82/9999800001 -> 2/243897561 -> 10/1219487805 -> 1/1219487805 = 0.000000 00082 00164 00246 00328 00410 00492 00574...
Odd Numbers
For the odd numbers we can add the all-ones sequence Oi to the even numbers. The generating function is:
1/(1-x) + 2x/(1-x)2 = (1-x)/(1-x)2 + 2x/(1-x)2 = ((1-x)+2x)/(1-x)2 = (1+x)/(1-x)2
as a fraction, using x=0.01 we get (1+x)/(1-x)2 = 1.01/0.9801 which converts easily into
101/9801 = 0.01 03 05 07 09 11 13 15...
To get a fraction that can be reduced to a form "1/N", we would need (x-1)2 to be a multiple of (x+1). Note that the divisors of (x-1)2 are the same as the divisors of (x-1). But x is a power of 10, so both (x+1) and (x-1) are odd, and they differ by only 2: so any prime that divides into one cannot divide into the other. So there is no fraction 1/N that will give the odd numbers in its decimal expansion.
The Squares
The squares are the sequence 1, 4, 9, 16, 25, 36, 49, ... (OEIS A0290). I gave its generating function without explanation earlier, but now we can derive it using techniques already shown. Let Si be the squares, Oi be the odd numbers, and note that the difference between two squares is an odd number.
Si = 0 + x + 4x2 + 9x3 + 16x4 + 25x5 + ...
x Si = 0 + 0x + x2 + 4x3 + 9x4 + 16x5 + ...
Oi = 1 + 3x + 5x2 + 7x3 + 9x4 + 11x5 + ...
x Oi = 0 + x + 3x2 + 5x3 + 7x4 + 9x5 + ...
This time xSi plus xOi is exactly equal to Si:
Si - xSi - xOi = 0
Since Oi is known we can solve for Si:
(1-x)Si = xOi = x(1+x)/(1-x)2
Si = x(1+x)/(1-x)3
and this is indeed the generating function I gave earlier.
To make this into a fraction whose decimal expansion has the squares as its digits, let x be 10-N for some N. For example, set N=2 to get 2 digits for each square, then x=1/100:
x(1+x)/(1-x)3 = (1/100)(101/100)(99/100)-3
= (1003 101) / (1002 993)
= 10100/970299
= 0.01 04 09 16 25 36 49 64 8201...
The Cubes
Deriving the generating function for the cubes A0578 is similar but lengthier process requiring that we first derive generating functions for two other sequences (one approach is to derive A8458 followed by A3215). The answer turns out to be x(1+4x+x2)/(1-x)4. Using x=0.0001 we can express the sequence as the decimal fraction x(1+4x+x2)/(1-x)4 = 0.000100040001/0.9996000599960001 = 1000400010000/9996000599960001 = 0.0001 0008 0027 0064 0125...
Generating Functions Through Derivatives
Tom Davis [2] uses calculus to derive the generating functions for the squares.
The Squares, More Directly
Deriving the generating function for the squares can be done much more quickly if you know how to take the derivative of a polynomial. Starting with the generating function for A0027:
Ii = x/(1-x)2
= 0 + x + 2x2 + 3x3 + 4x4 + 5x5 + ...
We just need to take the derivative with respect to x:
d/dx Ii = d/dx x/(1-x)2
= d/dx ( 0 + x + 2x2 + 3x3 + 4x4
+ 5x5 + ... )
To take the derivative of x/(1-x)2 we can expand the denominator to (1-2x-x2) and use the quotient rule:
d/dx x/(1-x)2
= ((1-2x-x2) - x(-2-2x)) / (1-2x-x2)2
= (1 - 2x - x2 + 2x + 2x2) / (1-x)4
= (1-x2) / (1-x)4
= (1-x) (1+x) / (1-x)4
= (1+x) / (1-x)3
The derivative of the infinite polynomial can be worked out term by term. For example the derivative of the 2x2 term is 4x. We get:
1 + 4x + 9x2 + 16x3 + 25x4 + ...
This polynomial has the squares A0290 as coefficients, so (1+x) / (1-x)3 must be its generating function. But all the terms are off by one: we want 0 + x + 4x2 + ... To get this we simply multiply both sides by x:
x(1+x)/(1-x)3 = 0 + x + 4x2 + 9x3 + 16x4 + 25x5 + ...
This is the same answer as in the first derivation.
The Cubes, Much More Directly
Using the same differentiation method we can get the generating function for the cubes. Again we expand the numerator and denominator of x(1+x)/(1-x)3 and use the quotient rule:
d/dx (x+x2)/(1-3x+3x2-x3)
= ((1-3x+3x2-x3)(1+2x) - (x+x2)(-3+6x-3x2))
/ (1-x)6
= (1 - 3x + 3x2 - x3 + 2x - 6x2 + 6x3 - 2x4
+ 3x - 6x2 + 3x3 + 3x2 - 6x3 + 3x4)
/ (1-x)6
= (1 + 2x - 6x2 + 2x3 + x4) / (1-x)6
= (1 + 4x + x2) / (1-x)4
The last step requires factoring the polynomial 1+2x-6x2+2x3+x4, which can be done with the aid of Wolfram Alpha or symbolic maths software. The derivative of the infinite polynomial is again quite easy to do, and again the result is off by one term, so we need to multiply both sides by x.
Using Maxima
Some folks prefer to use a program running on their own computer rather than a web site like Wolfram Alpha. I personally use Maxima (or by its older name, Macsyma) for work like this. They have similar syntax; both accept something like "factor(1+2*x-6x^2+2x^3+x^4)" but in Maxima you need to put a semicolon on the end.
Beyond the cubes the expanding and factoring gets to be a bit unwieldy to do by hand, so I'll use Maxima. Here I repeat the derivation for the cubes, then for the 4th powers A0583 and the 5th powers A0584:
(%i1) x*factor(ratsimp(diff(x*(1+x)/(1-x)^3, x))); 2 x (x + 4 x + 1) (%o1) ---------------- 4 (x - 1) (%i2) x*factor(ratsimp(diff(%,x))); 2 x (x + 1) (x + 10 x + 1) (%o2) - ------------------------- 5 (x - 1) (%i3) x*factor(ratsimp(diff(%,x))); 4 3 2 x (x + 26 x + 66 x + 26 x + 1) (%o3) --------------------------------- 6 (x - 1)In the second of these, Maxima has factored the numerator x(1+11x+11x2+x3). The minus sign in front can be eliminated by changing the denominator (x-1)5 to (1-x)5. As a rational fraction, using x=1/10000, we get:
x(1+11x+11x2+x3)/(1-x)5
= 0.0001001100110001/0.99950009999000049999
= 1001100110001/99950009999000049999
= 333700036667/33316669999666683333
= 0.0000 0001 0016 0081 0256 0625 1296 2401 4096...
Similarly the fraction for the 5th powers works out to 100260066002600010000/999400149980001499940001.
Some readers might be curious as to where those numbers 11, 26 and 66 "come from". The coefficients of all the polynomials derived in this way are called "Eulerian numbers" (OEIS sequence A8292) and they can be arranged in a triangle:
1 1 1 1 4 1 1 11 11 1 1 26 66 26 1 1 57 302 302 57 1 . . . . . . .Using the OEIS
The techniques described so far can be used to derive the generating function, and therefore a rational fraction, for a large variety of integer sequences including constants raised to the power of N, N raised to a constant power, linear homogeneous recurrence relations with constant coefficients (like the Fibonacci and Lucas sequences), and any linear combination of two or more of the above.
However, many of these would take a lot of work to derive — but many sequences have already been analyzed by others, and their generating functions have been worked out. These can often be found in the Online Encyclopedia of Integer Sequences.
Let's find the fraction whose digits will give us the 4th powers: 1, 16, 81, 256, 625, 1296, ... We already did that above, but we used software because it would have been a lot of work to do by hand.
Looking up the 4th powers on OEIS we find A0583. In the FORMULA section we find G.f.: x*(1+11*x+11*x^2+x^3)/(1-x)^5. which tells us that the generating function is x(1+11x+11x2+x3)/(1-x)5.
Let's try one that doesn't fit any of the forms we discussed so far. This sequence might be called "three steps forward, two steps back":
0,3,1,4,2,5,3,6,4,7,5...
I looked it up on OEIS and found a sequence, with a generating function:
OEIS: A84964
FORMULA G.F.: (2-2x+x2)/((1-x)(1-x2))
Letting x=0.01:
(2-2x+x2)/((1-x)(1-x2))
= (2-0.02+0.0001) / ((1-0.01)(1-0.0001))
= 1.9801 / 0.989901
= 1980100 / 989901
= 2.00 03 01 04 02 05 03 06 04 07 05 08 06...
When looking for generating functions on OEIS, note that there are different types of generating function. The ones labelled "G.f." or "O.g.f." ("ordinary" generating function) will often work this way, so long as the terms of the sequence are positive and small enough so that they don't overlap each other in the decimal expansion.
Some more examples:
The sequence 2n + 3n is: 2, 5, 13, 35, 97, 275, 793, 2315, ... (OEIS A7689). The OEIS gives us a generating function, (2-5x)/((1-2x)(1-3x)); using the 4-digit base b=10000, x=0.0001 and the fraction comes out to 19995/99950006 = 0.0002 0005 0013 0035 0097 0275...
A slightly different version is 2n + 3(n-1), or more precisely 2n+3n/3-0n/3. This is OEIS A85279: 1, 3, 7, 17, 43, 113, 307, 857, 2443, ..., its generating function is (1-2x-2x2)/((1-2x)(1-3x)), which produces the fraction 99979998/99950006 = 1.0003 0007 0017 0043 0113 0307...
Both of these involve the denominator 99950006 = 9998*9997 which is 10000-2 times 10000-3.
Sequence A1169 counts "board-pile polyominoes", which are shapes made up of square blocks, in which the entire shape is edge-contiguous (you can travel from any block to any other using a succession of king's moves) and each row is continguous (no holes in the middle of a row). The sequence starts: 1, 2, 6, 19, 61, 196, 629, 2017, ... and its generating function is x(1-x)3/(1 - 5x + 7x2 - 4x3). We can easily find the fraction 999700029999/999500069996 = 1.0002 0006 0019 0061 0196 0629 2017...
Sequence A2212 counts "restricted hexagonal polyominoes", and begins: 1, 1, 3, 10, 36, 137, 543, 2219, ... OEIS gives several generating functions, most of which are infinite series or recursively defined; but one G.f. is simply (1-x-√1-6x+5x^2)/(2x). Using x=0.0001 as usual, we get (1-0.0001-√1-0.0006+0.00000005)/0.0002 = (0.9999-√0.99940005)/0.0002 = (9999-√99940005)/2 = 1.0001 0003 0010 0036 0137 0543 2219...
In the original generating function, 1-6x+5x2 can be factored into (1-x)(1-5x), and that large number 99940005 is 9995×9999. Instead of (9999-√99940005)/2 we could write (9999-√9995×9999)/2.
Generating functions labelled "E.g.f." (exponential generating function) need to be done a different way, but with somewhat more effort. For example, a value could be converted to a mixed radix numeral system in which each place has a value 10-kn/n!, for some positive integer k. For example, if k is 5, 10k=100000, and the "digits" of the mixed radix system would have values: 1, 1/105, 1/2(×1010), 1/6(×1015), 1/24(×1000), etc.
For example, the number of permutations of n objects is n! (n factorial): 1, 1, 2, 6, 24, 120, 720, 5040, 40320, ... (A0142). Its generating function is an exponential generating function, and is simply 1/(1-x). Letting x=0.00001, we get 1/(1-x)=1.0000100001000010000100001... which is certainly not the factorials. But that's what the digits look like in "base 100000". If we instead express it as a + b/10000 + c/(100002×2!) + d/(100003×3!) + ... where a, b, c, d are successive "digits" in a mixed-radix place value system, then 1/(1-x) would look like:
1/(1-x) = 1. 1 2 6 24 ...
Some sequences have both ordinary and exponential generating functions. We saw earlier that the powers of 2 have O.g.f. 1/(1-2x). The powers of 2 also have an E.g.f., which is e2x. Again letting x=0.00001, e2x is 1.000020000200001333340000026666755555809524444445855382.... Converting to a mixed radix system with place-values of 10-5n/n! we get
e2x = 1. 2 4 8 16 ...
That's not immediately evident, but we can extract the digits one at a time. Here is e2x again, with digits in groups of 5:
1.00002 00002 00001 33334 00000 26666 75555 58095...
Remove the 1 at the start, then multiply the rest by 1:
0.00002 00002 00001 33334 00000 26666 75555 58095...
Remove the first "2", and multiply the rest by 2:
0.00000 00004 00002 66668 00000 53333 51111 16190...
Remove the "4" and multiply the rest by 3 (so that the remainder is now scaled by 3! = 6). You can see a "2.666..." get turned into 8:
0.00000 00000 00008 00004 00001 60000 53333 48571...
Remove the "8" and multiply the rest by 4 (so that the remainder is now scaled by 4! = 24):
0.00000 00000 00000 00016 00006 40002 13333 94285...
In the next step, a "6.4" multiplied by 5 becomes 32, and so on.
Non-Rational Fractions
As seen in that last example, some integer sequences have generating functions that do not work out to a rational fraction, but still produce a special decimal expansion. Probably the most commonly-encountered example is the Catalan number sequence A0108: 1, 1, 2, 5, 14, 42, 132, ... This sequence has the generating function (1-√1-4x)/2x. So if x=0.0001, (1-√1-4x)/2x is (1-√0.9996)/0.0002 = (10000-√99960000)/2 = 5000 - √24990000 = 1.0001 0002 0005 0014 0042 0132...
Dividing by 100 and noticing that 2499 = 502-1 = (50-1)(50+1), we get the far easier to remember:
50 - √49×51 = 0.01 0001 0002 0005 0014 0042 0132 0429...
which is easily converted to versions giving blocks of 6 or 8 digits:
500 - √499×501 = 0.001 000001 000002 000005 000014 000042 000132 000429 001430 004862 016796...
5000 - √4999×5001 = 0.0001 00000001 00000002 00000005 00000014 00000042 00000132 00000429 00001430 00004862 00016796 00058786 00208012 00742900 02674440...
See also the separate page Power Series for the Square Root of a Polynomial
Another example found in OEIS is sequence A0957, "Fine's sequence ... number of ordered rooted trees with n edges having root of even degree.". The sequence starts: 0, 1, 0, 1, 2, 6, 18, 57, 186, 622, 2120, ... and its generating function is given as "(1-sqrt(1-4*x))/(3-sqrt(1-4*x))". Indeed, using x=0.0001 as before and computing (1-√1-4x)/(3-√1-4x) gives
(1-√1-4x)/(3-√1-4x) = (1-√0.9996)/(3-√0.9996)
= (100-√9996)/(300-√9996)
= (50-√2499)/(150-√2499)
= (50-√49×51)/(150-√49×51)
= 0.0001 0000 0001 0002 0006 0018 0057 0186 0622 2120 ...
or in 6-digit blocks:
(500-√499×501)/(1500-√499×501) = 0.000001 000000 000001 000002 000006 000018 000057 000186 000622 002120...
To go into more depth with generating functions, try these resources:
- Wikipedia, Examples of generating functions.
- Dr. Gary MacGillivray (at University of Victoria), Notes on Generating Functions
- MIT 6.042J or 18.062J (Mathematics for Computer Science), Generating Functions (lecture notes with exercises)
- Hilbert S. Wilf (at Univ. Pennsylvania), generatingfunctionology.
Footnotes
[1] James Smoak, A Magic Trick from Fibonacci, College Math. Journal 34(1) pp 58-60 (2003).
[2] Tom Davis, Fractions and Decimals, 2005.
[3] Hisanori Mishima, Remarkable patterns (web page)
This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2022 Mar 28.
s.30