Solution
Fibonacci in Decimal
Show the problem again
Let $F_1 = F_2 = 1$ and $F_{n+1} = F_n + F_{n-1}$. Find the exact value of $\sum_{n=1}^{\infty} F_n / 10^n = 0.1 + 0.01 + 0.002 + 0.0003 + 0.00005 + \dots$. Give your answer as a reduced fraction.
Worked solution
The answer is 10/89. The generating function $G(x) = \sum_{n \ge 1} F_n x^n$ satisfies $G - xG - x^2G = x$ (the recurrence cancels every term except the first), so $G(x) = x/(1 - x - x^2)$. It converges for $|x| < 1/\varphi \approx 0.618$, which includes $x = 1/10$. Then $G(1/10) = (1/10)/(1 - 1/10 - 1/100) = (1/10)/(89/100) = 10/89$. Indeed $10/89 = 0.11235955\dots$, whose early digits visibly echo 1, 1, 2, 3, 5, 8 before the carries take over.
Source: Classic generating-function exercise in wide circulation; no traceable original source. Statement written for AxiomIQ.