1/109 and Fibonacci

289 Views Asked by At

I saw the image at the end of this post and wanted to check it. With the Mathematica code

Abs[N[1/109, 106] - Total[Table[Fibonacci[n] 1/10^(109 - n), {n, 1, 89}]]]

I get the following, with a lot of matching except at the start.

0.009798037939832989000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

That's pretty good, but that doesn't exactly match the claimed result. is it possible to make this work exactly by using more than 89 Fibonacci terms?

enter image description here

1

There are 1 best solutions below

1
On BEST ANSWER

The Fibonacci sequence is defined by the recurrence $$ F_{n} = F_{n-1} + F_{n-2} $$ Since this is a linear recurrence, we can run it in reverse and define earlier Fibonacci numbers as as function of later ones: $$ F_{n} = -F_{n+1} + F_{n+2} $$ This lets us continue the sequence to negative indices: $$ (F_{n})_{n\in \mathbb Z} = \ldots -8,5,-3,2,-1,1,0,1,1,2,3,5,8\ldots $$ If we flip this around with $G_{n}=F_{-n}$ we get a sequence satisfying $$ G_0 = 0 \qquad G_1 = 1 \qquad G_n = -G_{n-1} + G_{n-2} $$

The generating function for the $G_i$s is $$ f_G(x) = G_0 + G_1x + G_2 x^2 + \cdots + G_n x^n + \cdots = \frac{x}{1+x-x^2} $$ In particular we have $$ G_0 + \frac{G_1}{10} + \frac{G_2}{100} + \cdots + \frac{G_n}{10^n} + \cdots = \frac{0.1}{1.09} = \frac{10}{109} $$ Now things start to look like they may have something to do with the question!

Now long division by 109 turns out to repeat after 108 digits, after each remainder has been used exactly once.

Because the recurrence is linear we can use combinations of it to produce reverse Fibonacci sequences that start at other points -- in particular if we set $$ H_n = F_{108-n} $$ such that the $H_i$ start with the first 108 Fibonacci numbers backwards, we get $$ H_n = aG_n + bG_{n+1} $$ for some integers $a$ and $b$ which I could compute -- but I'd probably commit several off-by-one errors along the way, and it turns out the precise values don't matter.

In particular $$ H_0 + \frac{H_1}{10} + \cdots + \frac{H_n}{10^n} + \cdots = \frac{10(a+10b)}{109} $$ still for some integer $a$ and $b$. What we learn from this is that the long division by $109$ can produce a digit sequence ending at $\ldots 8532110$ -- but since $\frac{1}{109}$ uses all the remainders, it must eventually produce the reverse Fibonacci pattern. All we need to do is find out where and adjust the numerator such that we start as just the right place -- but, by direct inspection of the division it turns out that $1$ is the right numerator -- as long as we're okay by discarding any digits to the left of the decimal point, which we'll certainly need to do in order to match the figure in the question.