Why is generating function proof of Fibonacci formula correct?

Question

The proof goes as follows:-

Let $F = 1 + x + 2x^2 + 3x^3 + 5x^4 + 8x^5 + ...$

Then

$$\begin{align} 1 + Fx + Fx^2 &= 1 + (x + x^2 + 2x^3 + 3x^4 + ...) + (x^2 + x^3 + 2x^4 + 3x^5) \\ 1 + Fx + Fx^2 &= 1 + x + (x^2+x^2 + 2x^3+x^3 + 3x^4+2x^4 + ...) \\ 1 + Fx + Fx^2 &= F \\ \frac{1}{1-x-x^2} &= F \end{align} $$

We rearrange the terms and we get this result which can be then manipulated further to find formula for nth Fibonacci term.

I want to focus on the rearrangement of terms in an infinite series. This is no different from results like $ 1 + 2 + 4 + 8 + ... = -1$.

The usual answer given is that we cannot treat an infinite summation like this like real numbers and apply normal addition and subtraction rules. We must apply sophisticated techniques like limits to evaluate these sums. So $ 1 + r + r^2 + r^3 + ... $ only makes sense when $|r| < 1$.

So going back to the Fibonacci proof above. We are applying normal addition rules for an infinite summation and also the result $\displaystyle F = \frac{1}{1-x-x^2} $ doesn't make sense for any value of $x$. But we still use this result to complete the proof. Why does it work?

Isn't this the same as using the result $ 1 + 2 + 4 + 8 + ... = -1 $ to prove other results? It would be absurd to use it as basis for other proofs.

Please shed some light on this. I am really confused.

Answer 1

You can prove a bound like $F_n<2^n$ using induction so that the power series conveges at least for $|x|<1/2$ and the manipulations are valid. More generally, for a linear recurrence with constant coefficients, the radius of convergence of the resulting power series will be the minimum of the reciprocals of the roots of the characteristic equation and the power series hence will have nonzero radius of convergence.

Answer 2

Denote by $F_n$ the $n$-th Fibonacci number $$ F_0=0,\qquad F_1=1,\qquad F_{n+2}=F_{n+1}+F_n $$ and consider the series $$ F=\sum_{n\ge0}F_nx^n $$ in the ring of formal power series with coefficients in $\mathbb{R}$. This ring has the property that any series $$ \sum_{n\ge0}a_nx^n $$ with $a_0\ne0$ is invertible. Your computation takes places in this algebraic structure, where convergence is of no concern.

We can operate formally and write \begin{align} 1+xF+x^2F &=1+\sum_{n\ge0}F_nx^{n+1}+\sum_{n\ge0}F_nx^{n+2} \\[6px] &=1+\sum_{n\ge1}F_{n-1}x^n+\sum_{n\ge2}F_{n-2}x^n \\[6px] &=1+x+\sum_{n\ge2}(F_{n-1}+F_{n-2})x^n \\[6px] &=1+x+\sum_{n\ge2}F_nx^n \\[6px] &=F \end{align} so $$ 1=(1-x-x^2)F $$ The formal power series $1-x-x^2$ (with zero coefficient terms for $x^n$ with $n\ge3$) is invertible, so $$ F=(1-x-x^2)^{-1} $$ The rest is manipulation of elements in the ring of power series, using the fact that $$ (1-\alpha x)^{-1}=\sum_{n\ge0}\alpha^nx^n $$

No limit and no convergence, just algebra.

Answer 3

One way to do this is to first prove that the series converges and then do these calculations, as Foobaz John outlines. But in fact, all these manipulations are perfectly valid without even taking convergence into consideration if you frame them in the right way - that is, in terms of formal power series.

A formal power series is just an arbitrary infinite sequence $(a_0, a_1, a_2, \ldots)$ of (let's say) real numbers. But we "decorate" this sequence using the notation $(a_0, a_1, a_2, \ldots ) = \sum_{k=0}^\infty a_k x^k$. Note that we are not using any notion of convergence here. We just the notation $$\sum_{k=0}^\infty a_k x^k$$ to mean the sequence $(a_0, a_1, a_2, \ldots)$. In this context infinite sums like $\sum_{k=0}^\infty k! x^k$ that are convergent nowhere except $x=0$ are perfectly fine, since it just refers to the sequence of numbers $(1,1,2,6,24, \ldots)$.

This would be perfectly useless unless we allowed to manipulate them in certain ways. So we make the definitions

$$\sum_{k=0}^\infty a_k x^k + \sum_{k=0}^\infty b_k x^k := \sum_{k=0}^\infty (a_k + b_k) x^k$$

$$(\sum_{k=0}^\infty a_k x^k ) \cdot ( \sum_{k=0}^\infty b_k x^k) := \sum_{k=0}^\infty \sum_{i=0}^k a_ib_{k-i} x^k. $$

Now you can go through and prove that all the usual rules of algebra apply, so that $F(G+H) = FG + FH$, $(FG)H = F(GH)$ etc. for formal power series $F,G,H$. This means that the set of formal power series forms a ring. You can sometimes divide: it's possible to prove that $F = \sum_{k=0}^\infty a_k x^k$ has a multiplicative inverse $G$ so that $FG = 1$ if and only if $a_0 \neq 0$. (Here $1 := \sum_{k=0} b_k x^k$ where $b_0 = 1$, $b_k = 0$ for $k > 0$.)

In the ring of formal power series all of these computations are valid.