A Golden Fraction I

Number Theory Level 5

$\frac{100,000,000,000,000,000,000}{99,999,999,989,999,999,999}$

What is the $250^{\text{th}}$ digit to the right of the decimal place of the fraction above?

As an explicit example, the $3^\text{rd}$ digit to the right of the decimal place of 11235.123456789 is 3.

Inspired by Pi Han Goh .

The answer is 3.

3 solutions

Brandon Monsen
Nov 27, 2015

First, lets divide the numerator and denominator by $10^{20}$ , in order to make it look less scary. We should get that our expression is equal to

$\frac{1}{.99999999989999999999}$

Note that this fraction is equal to

$\frac{1}{1-10^{-10}-10^{-20}}$

In other words, our fraction is equal to

$\frac{1}{1-x-x^{2}}$

Evaluated at $x=10^{-10}$

Using long division, we get that:

$\frac{1}{1-x-x^{2}}=1+x+2x^{2}+3x^{3}+5x^{4}+8x^{5}+13x^{6}+...$

And we can see that our coefficients correspond to terms of the Fibonacci Sequence , being:

$\frac{1}{1-x-x^{2}}=F_{1}+F_{2}x+F_{3}x^{2}+F_{4}x^{3}+F_{5}x^{4}+...$

Where $F_{n}$ means the $n^{th}$ term of the Fibonacci Sequence.

By re-substituting $10^{-10}$ in for $x$ , our polynomial looks like:

$\frac{1}{1-10^{-10}-10^{-20}}=F_{1}+F_{2} \times 10^{-10}+F_{3} \times 10^{-20}+F_{4} \times 10^{-30}+F_{5} \times 10^{-40}+...$ .

This means that the $10 \times n^{th}$ decimal place is the last digit of $F_{n+1}$ , provided that $F_{n+1}$ has less than 10 digits. Since we are looking for the $250^{th}$ decimal place, we want the value of $F_{26} \mod 10$ .

We can list out our values of $F_{n} \mod 10$ as:

$1,1,2,3,5,8,3,1,4,5,9,4,3,\\7,0,7,7,4,1,5,6,1,7,8,5,3$

And so $3$ is the last digit of $F_{26}$

We can also tell that given $F_{n}$ , $F_{n+1}<2F_{n}$ , so $F_{26}<2^{26}$ .

Since $5>2^{2}$ , we know that $F_{26}<2^{26}<5^{8} \times 2^{10}<10^{8} \times 4 < 10^{10}$

So we can conclude that $F_{26}$ has less than ten digits, and so our answer is $\large \boxed{3}$

Nice solution, but it needs a little tightening up. We need to do a little more than use long division, unless we can show that all the coefficients have been identified, rather than just the first $7$ you have written down.

Basically, we need to show that the generating function of the Fibonacci numbers is $(1 - x - x^2)^{-1}$ . But $\begin{array}{rcl} \displaystyle(1 - x - x^2)\sum_{n=1}^\infty F_nx^n & = & \displaystyle\sum_{n=1}^\infty F_nx^n - \sum_{n=1}^\infty F_n x^{n+1} - \sum_{n=1}^\infty F_n x^{n+2} \\ & = & \displaystyle \sum_{n=1}^\infty F_n x^n - \sum_{n=2}^\infty F_{n-1}x^n - \sum_{n=3}^\infty F_{n-2}x^n \\ & = & \displaystyle F_1x + F_2x^2 - F_1x^2 + \sum_{n=3}^\infty(F_n - F_{n-1} - F_{n-2})x^n \; = \; x \end{array}$ and hence $\sum_{n=1}^\infty F_n x^n \; = \; (1 - x - x^2)^{-1} \;,$ as required. Since $\frac{F_{n+1}}{F_n} \to \phi$ as $n \to \infty$ , where $\phi$ is the Golden Ratio, the generating function of the Fibonacci numbers has radius of convergence $\phi^{-1}$ , and so all the above manipulations are valid for $|x| < \phi^{-1}$ .

Mark Hennings - 5 years, 6 months ago

This is great! Thanks for tightening up the loose ends!

Brandon Monsen - 5 years, 6 months ago

Nice solution!

Chew-Seong Cheong - 5 years, 6 months ago

@Mark Hennings This may not be related question, but if I wanted to find the rate of convergence of $\frac{F_{n+1}}{F_n}\to\phi$ , how would we find it?

Axas Bit - 5 years, 4 months ago

You need to use Binet's Formula for the Fibonacci numbers: $F_n \; = \; \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right]$ so that $F_n \,=\, \tfrac{\phi^n}{\sqrt{5}}(1 - \alpha^n)$ , and hence $\frac{F_{n+1}}{F_n} \; = \; \phi\left(\frac{1 - \alpha^{n+1}}{1-\alpha^n}\right)$ where $\alpha \; =\; \frac{1-\sqrt{5}}{1+\sqrt{5}} \;.$ Then $\frac{F_{n+1}}{F_n} - \phi \; = \; \phi\frac{\alpha^n(1 - \alpha)}{1 - \alpha^n} \;,$ and so you can find a constant $K$ such that $\left| \frac{F_{n+1}}{F_n} - \phi\right| \; \le \; K \left(\frac{\sqrt{5}-1}{\sqrt{5}+1}\right)^n \;,$ showing an exponential rate of convergence.

Mark Hennings - 5 years, 4 months ago

@Mark Hennings – Wait, I don't quite understand. How would one go about finding $K$ ? Doesn't this already show an exponential growth without finding K?

Axas Bit - 5 years, 4 months ago

@Axas Bit – $\left| \frac{F_{n+1}}{F_n}-\phi\right| \; = \; \phi(1-\alpha)\frac{|\alpha|^n}{1 - \alpha^n} \; \le \; \frac{\phi(1-\alpha)}{1-|\alpha|}|\alpha|^n$ for $n \ge 1$ , so $K = \frac{\phi(1-\alpha)}{1-|\alpha|}$ works. The actual value of $K$ is irrelevant; all I am doing is absorbing the $1-\alpha^n$ in the denominator into the constant, since it does not affect the exponential rate of decay.

Mark Hennings - 5 years, 4 months ago

Kyle Gray
Mar 17, 2016

Solution in Java

System.out.println((new BigDecimal("100000000000000000000")).divide(new BigDecimal("99999999989999999999"), 250, BigDecimal.ROUND_FLOOR));

Lu Chee Ket
Nov 29, 2015

Scientific method rather than mathematical method is introduced here. Apply $\frac{x}{x - a} = 1 + \frac{a}{x - a}.$

Since 1.000000000100000000020000000003 is its leading figure to reveal some digits, using calculator with 32 significant figures, we can determine its terms of Fibonacci sequence continuously to the right by coincidence perhaps. Minus step by step, it reveals up to 55 as 54.999182896696369939279022260939e-88!

The right most of 121393 is the 250th digit wanted, which is 3.

Answer: $\boxed{3}$

Wrong. Nothing scientific about this. What you did was you just asked the computer to find the answer.

Pi Han Goh - 5 years, 5 months ago

This is not scientific since you did nothing to base your conjecture on. How do you know that this sequence is going to be repeated?

Anupam Nayak - 5 years, 5 months ago

A Golden Fraction I

Inspired by Pi Han Goh .

The answer is 3.

3 solutions

0 pending reports