finding area of convergence for Fibonacci Generating Function Formula

Question

The following text is from the book A Friendly Introduction to Number Theory by J H Goldenman :)

---

Checking the process again and again I found no restriction for x (i.e. the area of convergence). However, for x=1 we have $\infty = -1$. When we say $1+x+x^2+ \dots = \dfrac{1}{1-x}$, valid for $|x|<1$, that's becasue $1+x+x^2+ \dots + x^n = \dfrac{1-x^{n+1}}{1-x}$ for any $x$, then we impose $-1<x<1$ in order to make the series convergent for $n \to \infty$; But how the l.h.s of Fibonacci Generating Function Formula doesn't show divergence when written in a close form?

Answer 1

The golden ratio $\phi = \frac{1 + \sqrt{5}}{2}$ satisfies

$$\phi^2 - \phi - 1 = 0,$$

and the reciprocal $x = \phi^{-1}$ satisfies

$$1 - x - x^2 = 0.$$

Furthermore,

$$\lim_{k \to \infty} \frac{F_{k+1}}{F_k}= \phi.$$

The ratio test specifies a radius of convergence for $\sum F_k x^k$ equal to $\phi^{-1}$ since

$$\lim_{k \to \infty} \frac{F_{k+1}|x|^{k+1}}{F_k |x|^k} = \phi |x|,$$

with absolute convergence for $|x| < \phi^{-1}.$

Clearly the power series can't converge everywhere since the denominator of the generating function tends to $0$ as $x \to \phi^{-1}$.

You have to be careful applying arithmetic operations to infinite sums as if they were real numbers. Your manipulations of $F(x)$ are not valid for every $x$ unless you know a priori that the series is convergent.

For example, if we write $S = 1 + x + x^2 + \ldots$ and then argue that

$$xS = x + x^2 + x^3 + \ldots \\ \implies S - xS = 1 \\ \implies S = \frac{1}{1-x},$$

we don't find the sum of an infinite series with infinite radius of convergence.

Answer 2

The power series of the generating function is $\sum_{n=1}^{\infty} F_n x^n$. By applying the ratio test, we have convergence when

$$ \lim_{n\to \infty}\left| \frac{F_{n+1} x^{n+1}}{F_n x^n} \right| = \lim_{n\to \infty} \frac{F_{n+1}}{F_n}\left| x \right| = \phi |x| <1, $$

where the last result in the limit is a famous property about the quotient of successive Fibonacci numbers.

Therefore, the radius of convergence around zero is $1/\phi$, where $\phi = \frac{1+\sqrt{5}}{2}$ is the Golden Ratio. In other words, when $|x|<1/\phi$, the power series will converge.

I took the liberty of using Mathematica to plot the first 30 terms of the power series. The (approximate) series is shown in blue; the generating function is shown in red; and the interval of convergence is partitioned off by the vertical green lines.