"Matching coefficients" in generating functions approach

Here (https://austinrochford.com/posts/2013-11-01-generating-functions-and-fibonacci-numbers.html), it is proved (by generating functions) that the nth Fibonacci number is $$F_n=\frac{1}{\sqrt{5}}(\varphi^n-\psi^n)$$ where $\varphi$ is the golden ratio and $\psi =-\varphi^{-1}$.

This is one of the arguments on the page:

Recall that the sum of a geometric series is given by $$\frac{1}{1-x}=\sum_{n=0}^\infty x^n.$$ Note that this infinite sum converges if and only if $|x|\lt 1$. However, considered as a formal power series, this identity always holds.

They arrive at $\sum_{n=0}^\infty a_nx^n=\sum_{n=0}^\infty b_nx^n$ for some $a_n,b_n$ and conclude that $a_n=b_n$. But I think the arguments are flawed in general: Consider $$\sum_{n=0}^\infty n!x^n=\sum_{n=0}^\infty n!^2 x^n.$$ (this is actually true for $x=0$). Then it is certainly not the case that $n!=n!^2$ for all $n\in\mathbb{N}$.

I think that the reason why the generating function approach works well with Fibonacci numbers is that the radius of convergence of $\sum_{n=0}^\infty F_n x^n$ is non-zero. Then we can apply the theorem from complex analysis that the coefficients of such power series (non-zero radius of convergence) are uniquely determined.

But this way of thinking is quite different from "However, considered as a formal power series, this identity always holds." etc., I'm worried I'm missing something.

Solution 1:

A formal power series means that we're really working with a sequence of coefficients, and we're manipulating them the way we would work with infinite sums, but we're not actually thinking about the infinite sums at all. More specifically:

1. A formal power series in $x$ is a sequence $(a_0, a_1, a_2, \dots)$ which we write as $\sum_{n=0}^\infty a_n x^n$, for intuition.
2. The sum of two such sequences $(a_0, a_1, a_2, \dots)$ and $(b_0, b_1, b_2, \dots)$ is $(a_0+b_0, a_1+b_1, a_2+b_2, \dots)$.
3. The product of two such sequences is $(a_0 b_0, a_0b_1 + a_1b_0, a_0b_2 + a_1b_1+a_2b_0, \dots)$.
4. Two formal power series are equal iff the sequences are equal.

In particular, it's valid to say that $\frac1{1-x} = \sum_{n=0}^\infty x^n$. This is saying that the formal power series $\sum_{n=0}^\infty x^n$, or the sequence $(1,1,1,1,\dots)$, is the multiplicative inverse of the formal power series $1-x$, or the sequence $(1,-1,0,0,\dots)$. To check this, multiply them together by the rule given above.

In most ways, working with formal power series is similar to working with power series as infinite sums. In particular, when the power series has a positive radius of convergence, then within that radius, either approach should give the same answers.

However, in the realm of formal power series, it is not true that $$\sum_{n=0}^\infty n!x^n=\sum_{n=0}^\infty n!^2 x^n.$$ The left-hand side is the formal power series represented by the infinite sequence $(1,1,2,6,24,\dots)$. The right-hand side is the formal power series represented by the infinite sequence $(1,1,4,36,576,\dots)$. These are not the same sequence, so they are not the same formal power series, period (even though for all $x$, both infinite sums either diverge or give the same value).

In general, the purpose of working with formal power series is to avoid thinking about the radius of convergence in purely combinatorial problems where it's not actually relevant.