If you evaluate the fraction 100/9801 on a calculutor, the resulting number shows a regular pattern:
\(\displaystyle \frac{100}{9801} = 0.01\ 02\ 03\ 04\ 05\ 06\ 07\ 08\ 09\ 10\ 11\ 12 \ldots\)
Though a calculator doesn’t have enough digits to show it, this pattern goes all the way to 97, but then it skips 98 before it rolls over and repeats:
\(\displaystyle \frac{100}{9801} = 0.01\ 02\ 03\ 04\ 05 \ldots 96\ 97\ 99\ 00\ 01\ 02\ 03 \ldots\)
Of course, this pattern can’t be a coincidence, and there must be some underlying reason for it. This article will explain it and demonstrate even more sophisticated patterns you can produce. We’ll start with elementary techniques and eventually show its connection with concepts from higher mathematics.
Shift, subtract, solve
Let’s review how one can convert an infinite decimal to a fraction. To convert the decimal 0.3333… to 1/3, the most common method goes as follows. Start with
\(\displaystyle x = 0.333333…\)
Multiply by 10 to shift the decimal point:
\(\displaystyle 10x = 3.333333…\)
Subtract the two equations:
\(\displaystyle \begin{alignat*}{4}10x-x &= &\phantom{-} &3.333333…\\ & & – & 0.333333…\end{alignat*}\)
Simplify and solve:
\(\displaystyle 9x = 3\)
\(\displaystyle x = \frac{3}{9} = \frac{1}{3}\)
Thus we have shown 0.333333… = 1/3.
A harder example
Can we do the same to 0.0102030405…? Let’s try and find out:
\(\displaystyle x = 0.0102030405…\)
Multiply by 100 to shift the decimal point over two places:
\(\displaystyle 100x = 1.0203040506…\)
Subtract the two equations:
\(\displaystyle \begin{alignat*}{4}100x-x &= &\phantom{-}&1.0203040506…\\ & & – &0.0102030405… \\99x &= &\phantom{-}&1.0101010101…\end{alignat*}\)
We get another infinite decimal, but we’re making progress! Let’s multiply by 100 again:
\(\displaystyle 9900x = 101.01010101…\)
Subtract to get
\(\displaystyle \begin{alignat*}{4}9900x-99x &= &\phantom{-}&101.01010101…\\ & &-&\phantom{10}1.01010101…\\9801x&=&\phantom{-}&100\end{alignat*}\)
\(\displaystyle x = \frac{100}{9801}\)
Success!
Fibonacci
The iconic Fibonacci sequence begins as follows: 1, 1, 2, 3, 5, 8, 13, …. Each term is the sum of the preceding two, e.g., 3 = 2 + 1 and 13 = 8 + 5. Would it be possible to embed this sequence into a decimal number? Let’s try:
\(\displaystyle x= 0.001\ 001\ 002\ 003\ 005\ 008\ 013…\)
Multiply by 1000 and subtract:
\(\displaystyle \begin{alignat*}{4}1000x-x &= &\phantom{-}&1.001\ 002\ 003\ 005\ 008\ 013…\\ & & -& 0.001\ 001\ 002\ 003\ 005\ 008…\\999x &= &\phantom{-}&1.000\ 001\ 001\ 002\ 003\ 005…\end{alignat*}\)
You may already notice that \(999x\) contains a copy of \(x\) shifted right a few decimal places. So, we can write:
\(\displaystyle 999x = 1+\frac{ 0.001\ 001\ 002\ 003\ 005\ 008\ 013…}{1000}\)
\(\displaystyle 999x = 1+\frac{x}{1000}\)
Solving for \(x\) gives:
\(\displaystyle x = \frac{1000}{998999}\)
Indeed, if you type this fraction into your favorite computer algebra system, you get the decimal:
0.001 001 002 003 005 008 013 021 034 055 089 144 233 377 610 988...We can see it has all the Fibonacci numbers up to 610. The next one, 987, is corrupted by a carry from the 4-digit Fibonacci number, 1597, that follows.
Generalizing with generating functions
In this section, we’ll derive an algebraic explanation of the phenomena we saw above. To start, recall that a decimal number 0.abcd… can be written as a sum
\(\displaystyle 0.abcd… = \frac{a}{10^1} + \frac{b}{10^2} + \frac{c}{10^3} + \frac{d}{10^4} + \cdots\)
Going back to our first example of 0.010203…, we can write it as
\(\displaystyle 0.010203… = \frac{1}{10^2} + \frac{2}{10^4} + \frac{3}{10^6} + \cdots\)
To generalize this expression, let’s get rid of the 10s by substituting in x instead. Specifically, let’s use \(x = 10^{-2}\), giving us the power series:
\(\displaystyle x + 2 x^2 + 3 x^3 + \cdots\)
Equivalently, using sigma notation,
\(\displaystyle \sum_{i=1}^\infty i x^i\)
At this point, we now have what’s called a generating function: a power series where the coefficients represent a sequence (in this case, the sequence is 1, 2, 3, …). Generating functions can be useful because they allow us to make connections between sequences, algebraic identities, and analytic functions. We’ll apply the shift-subtract-solve technique to discover one such algebraic identity.
To begin, define
\(\displaystyle F(x) = x + 2 x^2 + 3 x^3 + \cdots = \sum_{i=1}^\infty i x^i\)
The “shift” operation above was multiplying by 100. Here, we instead multiply by x:
\(\displaystyle xF(x) = x^2 + 2 x^3 + 3 x^4 + \cdots = \sum_{i=1}^\infty i x^{i+1}\)
Next, we perform the subtraction step:
\(\displaystyle \begin{alignat*}{6} F(x)-xF(x) &= & \ x &+ 2 x^2 &+ 3x^3 &+ 4x^4&+ \cdots\\ & & &- \phantom{2}x^2 &- 2x^3 &- 3 x^4 &- \cdots\\ &=& \ x &+ \phantom{2}x^2 &+ \phantom{2}x^3 &+ \phantom{2}x^4 &+ \cdots\end{alignat*}\)
(You may already recognize this sum from elementary algebra; it’s an infinite geometric series. We could use the formula for the sum to proceed more quickly, but instead we’ll keep using the shift-subtract-solve technique.)
We still have an infinite series, so let’s do another shift and subtract step. Let’s take \(F(x)-xF(x)\) and multiple the whole thing by x and subtract:
\(\displaystyle (F(x)-xF(x))-x(F(x)-xF(x)) = x + x^2 + x^3 + x^4 + \cdots-x(x + x^2 + x^3 + x^4 + \cdots)\)
\(\displaystyle = x + x^2 + x^3 + x^4 + \cdots-x^2-x^3-x^4-\cdots\)
Everything cancels except for \(x\), so
\(\displaystyle (F(x)-xF(x))-x(F(x)-x(F(x)) = x\)
Expand out the left side and simplify:
\(\displaystyle F(x)-xF(x)-xF(x)+x^2F(x) = x\)
\(\displaystyle F(x)(1-2x+x^2) = x\)
\(\displaystyle F(x) = \frac{x}{1-2x+x^2}\)
\(\displaystyle F(x) = \frac{x}{(1-x)^2}\)
Thus, we have discovered the algebraic identity
\(\displaystyle x + 2x^2 + 3x^3 + \cdots = \frac{x}{(1-x)^2}\)
(See the appendix for an alternative way to get this identity with calculus. Note that this only converges when \(|x| < 1\). Although understanding convergence is important, it is a bit technical and not the main point of this article, so I won’t say more here.)
If we plug in \(x = 1/100\), we recover our original fraction:
\(\displaystyle 0.010203… = \frac{1}{10^2} + \frac{2}{10^4} + \frac{3}{10^6} + \cdots = \frac{1/100}{(1-1/100)^2}\)
\(\displaystyle = \frac{1/100}{99^2/100^2} = \frac{100}{9801}\)
Using other powers of 10 for x, we can generalize this pattern and create similar decimal numbers:
x x/(1-x)^2 Decimal
------------------------------------------------
1/10 10/99 0.12345...
1/100 100/9801 0.0102030405...
1/1000 1000/998001 0.001002003004005...Fibonacci, redux
In this section, we’ll derive a formula for the Fibonacci numbers generating function. Our generating function is
\(\displaystyle G(x) = x + x^2 + 2x^3 + 3x^4 + 5x^5 + \cdots = \sum_{i=1}^\infty F_i x^i \ \ \ \ \ (1)\)
Though shift-subtract-solve will work, there’s a shortcut we can use. The definition of the Fibonacci series is \(F_{i+2} = F_{i+1} + F_i\), so \(F_i = F_{i+2}-F_{i+1}\). Substitute that in to (1) to get
\(\displaystyle G(x) = \sum_{i=1}^\infty (F_{i+2}-F_{i+1}) x^i\)
\(\displaystyle = \sum_{i=1}^\infty \frac{F_{i+2}x^{i+2}}{x^2}-\frac{F_{i+1}x^{i+1}}{x}\)
\(\displaystyle = \left(\frac{1}{x^2} \sum_{i=1}^\infty F_{i+2}x^{i+2}\right)-\left(\frac{1}{x} \sum_{i=1}^\infty F_{i+1}x^{i+1}\right)\)
Let’s change the range of the sums to make it look like our original series \(G(x)\):
\(\displaystyle = \left(\frac{1}{x^2} \sum_{i=3}^\infty F_ix^i\right)-\left(\frac{1}{x} \sum_{i=2}^\infty F_ix^i\right)\)
The sums are almost the same as \(G(x)\), but are missing the initial terms i=1 (for both) and i=2 (for the left sum). So, we can write
\(\displaystyle G(x) = \frac{G(x)-x-x^2}{x^2}-\frac{G(x)-x}{x}\)
Now we can solve for \(G(x)\):
\(\displaystyle G(x)\left(1-\frac{1}{x^2} + \frac{1}{x}\right) = \frac{-x-x^2}{x^2} – \frac{-x}{x}\)
\(\displaystyle G(x)\frac{x^2 + x-1}{x^2} = \frac{-x}{x^2}\)
\(\displaystyle G(x) = \frac{x}{1-x-x^2}\)
And that’s our generating function for the Fibonacci sequence! Plugging in powers of 10 for x, we can produce decimal numbers containing the sequence:
x x/(1 - x - x^2) Decimal
------------------------------------------------------------
1/10 10/89 0.11235...
1/100 100/9899 0.01010203050813213455...
1/1000 1000/998999 0.001001002003005008013...Where to learn more
Making fun infinite decimals isn’t the only cool thing generating functions can do. Among other things, they can help solve tricky combinatorial problems and find asymptotic behavior for sequences. There’s a free book I can recommend that does a great job covering them: generatingfunctionology.
Appendix: Calculus
Earlier, using the shift-subtract-solve procedure, we derived the identity
\(\displaystyle x + 2x^2 + 3x^3 + \cdots = \frac{x}{(1-x)^2}\)
This can also be derived quickly using calculus. Start with the formula for an infinite geometric series:
\(\displaystyle 1 + x + x^2 + x^3 + \cdots = \frac{1}{1-x}\)
Differentiate both sides with respect to x:
\(\displaystyle 1 + 2x + 3x^2 + 4x^3 + \cdots = \frac{1}{(1-x)^2}\)
Multiplying both sides by x gives the identity.