Yesterday, I wrote about how the fractions

$$\begin{aligned}

\frac{1000}{998999} &= 0.00100100200300500801302103405509… \\

\frac{10000}{99989999} &= 0.000100010002000300050008001300210… \\

\frac{100000}{9999899999} &= 0.0000100001000020000300005000080001… \\

\frac{1000000}{999998999999} &= 1.000001000002000003000005000008000013…\cdot 10^{-6} \\

\frac{10000000}{99999989999999} &= 1.000000100000020000003000000500000080000013\cdot 10^{-7} \\

\end{aligned}$$

display the first several values of the Fibonacci sequence. The general formula for these fractions is $$f_k = \frac{10^k}{10^{2 k} – 10^k – 1}.$$

Today, I will provide a fairly simple derivation for this formula without summing an infinite series.

Let $a_1=1, a_2=1, a_3=2, a_4=3, a_5=5, a_6=8,\ldots$ be the Fibonacci sequence. Let $a_i=0$ when $i\leq 0$. Now, we know that by definition

$$a_n = a_{n-1} + a_{n-2}$$

for all $n>1$. The formula above also holds for $n<1$, but fails for $n=1$. We can fix that by adding in the Kronecker delta function $\delta_{i,j}$ which is 0 if $i\neq j$ and 1 when $i=j$. The amended formula valid for all $n$ is

$$a_n = a_{n-1} + a_{n-2} +\delta_{n,1}.$$

In the prior article, we defined the Fibonacci fractions to be

$$f_k = \sum_{i=1}^\infty \frac{a_i}{10^{\ ki}}.$$

So,

$$\begin{aligned} f_k &= \sum_{i=1}^\infty \frac{a_i}{10^{\ ki}} \\ &= \sum_{i=1}^\infty \frac{a_{i-1} + a_{i-2} + \delta_{i,1}}{10^{\ ki}}\\&= \sum_{i=1}^\infty \frac{a_{i-1}}{10^{\ ki}} +\frac{a_{i-2}}{10^{\ ki}} + \frac{\delta_{i,1}}{10^{\ ki}}\\&= \frac{1}{10^{\ k}} + \sum_{i=1}^\infty \frac{a_{i-1}}{10^k10^{\ k(i-1)}} +\frac{a_{i-2}}{10^{2k}10^{\ k(i-2)}} \\&= \frac{1}{10^{\ k}} + \frac{f_k}{10^k} +\frac{f_k}{10^{2k}}. \end{aligned}$$

Thus,

$$f_k= \frac{1}{10^{\ k}} + \frac{f_k}{10^k} +\frac{f_k}{10^{2k}}$$

$$f_k – \frac{f_k}{10^k} -\frac{f_k}{10^{2k}} = \frac{1}{10^{\ k}}$$

$$f_k \left(1 – \frac{1}{10^k} -\frac{1}{10^{2k}}\right) = \frac{1}{10^{\ k}}$$

$$f_k = \frac{\frac{1}{10^{\ k}}}{ 1 – \frac{1}{10^k} -\frac{1}{10^{2k}} }$$

$$f_k = \frac{10^{\ k}}{ 10^{2k} – 10^k -1 }$$

which completes the derivation.

This technique is often used for Z-transforms and generating functions.

## Related Posts via Categories