Sign up ×

I've been reading generationgfunctionology by Herbert S. Wilf (you can find a copy of the second edition on the author's page here).

On page 33 he does something I find weird. He wants to shuffle the index forward and does so like this: \begin{align*} (f_{n+1})_{n\in N_0} &= \frac{(f(X)-f(0))}{X}\\ (f_{n})_{n\in N_0} &= \sum_{n\in N_0} f_nx^n \end{align*}

Why is this allowed? Namely $X$ has a noninvertible (0) constant term, so how is this division (multiplication with the reciprocal) defined within the ring of formal power series?

share|cite|improve this question
It looks to me like he's just canceling a factor of $X$ from $f(X)-f(0)$ and not inverting $X$ as a power series, which is impossible, as you say. – Grumpy Parsnip Mar 10 '11 at 21:16

5 Answers 5

up vote 9 down vote accepted

If a power series $g(X)$ has zero constant term, then it is true that it is not invertible, so you cannot divide by it in general. However, it may happen that you can divide some power series by $g(X)$, namely those that have $g(X)$ as a factor. If $f(X)$ is a power series and $g(X)$ is a nonzero power series, then we can divide $h(X)=g(X)f(X)$ by $g(X)$ by defining $\frac{h(X)}{g(X)}$ to be $f(X)$. This is unambiguous because, as Qiaochu noted, the power series ring is an integral domain.

This is what's going on here. Because $f(X)-f(0)$ has zero constant term, you can write it as $Xg(X)$ for some power series $g(X)$, and $\frac{f(X)-f(0)}{X}$ is another name for $g(X)$.

share|cite|improve this answer
Aha, thanks! I thought as much, it just never mentioned in the book explicitly. – jvr Mar 10 '11 at 21:30
Wilf doesn't try to go all rigor with formal series, for that you'd have to look elsewhere, e.g. Kauers and Paule "The Concrete Tetrahedron" (Springer, 2011) goes to some lengths in this. – vonbrand Aug 18 at 18:27

The ring of formal power series is an integral domain, so you can cancel factors from two sides of an equation. (This is equivalent to saying that it embeds into a field, the ring of formal Laurent series.) This is the same thing you do when you say that $2 = \frac{6}{3}$ even though $3$ isn't invertible in $\mathbb{Z}$.

share|cite|improve this answer

The ring of formal power series over a domain is itself a domain, hence nonzero elements are cancellable, quotients are unique, etc. But you don't need these results for the whole ring - only for the element $\rm\:X\:,\: $ and this case can be proved quite simply. It is obvious that $\rm\:X\:$ is not a zero-divisor, i.e. $\rm\ X\ f\:(X) = 0\ \Rightarrow\ f\:(X)=0\:,\: $ from which closely related results follow immediately, viz.

THEOREM $\ \ $ TFAE for $\rm\ a \in R\ $ any ring

$(1)\quad\ \rm a\: b\ =\ a\: c\ \ \Rightarrow\ \ b\ =\ c\quad\quad\quad\quad\quad\quad\ $ ($\rm\:a\:$ is cancellable)

$(2)\quad\rm\ a\:b\ =\ \ 0\ \ \ \Rightarrow\ \ b\ =\ 0\quad\quad\quad\quad\quad\quad\ $ ($\rm\:a\:$ is not a zero-divisor)

$(3)\quad $ roots of $\rm\ a\ x\ =\ b\ $ are unique $\quad\ \ $ (uniqueness of division by $\rm\:a\:$)

Proof $\rm\ \ \ (1\Rightarrow 2)\ \ $ Specialize $\rm\: c = 0$

$\rm (2\Rightarrow 3)\ \ \ a\ x = b = a\ x'\ \Rightarrow\ \ a\ (x-x') = 0\ \ \Rightarrow\ \ x = x'$

$\rm (3 \Rightarrow 1)\ \ \ a\ x = a\: c\ $ has roots $\rm\ b,c\ $ so $\rm\ b = c$

share|cite|improve this answer
Since you are talking about "any ring", you might as well write "left cancellable" in (1), "not a left-zero-divisor" in (2), and "left division" in (3), no? – Arturo Magidin Mar 11 '11 at 0:22
@Arturo: The OP's context is a commutative ring. Adding language to deal with noncommutative generalizations would only serve to obfuscate these simple ideas. – Bill Dubuque Mar 11 '11 at 0:33

Are you allowed to write the following?

\begin{align*} X = \frac{X^2}{X}\ \end{align*}

share|cite|improve this answer

The concept of ring formalizes all the allowed operations, but I think this can be presented without all reference to the machinery.

The original function is $f_n$. The generating function is $f(x)$ where $x$ is the variable ($X$ in the OP's question):

$$f(x) = \sum_{n\ge0} f_n x^n$$

Then we can operate on this as follows using naive power series operations: $f(0) = f_0$, so

$$f(x) - f(0) = \sum_{n\ge1} f_n x^n$$

(whatever the value of $f_0$; it can be invertible or not - we're not trying to invert the gf here at all). So then

$$\frac{f(x) - f(0)}{x} = \frac{1}{x}\sum_{n\ge1} f_n x^n = \sum_{n\ge1} f_n x^{n-1} = \sum_{n\ge0} f_{n+1} x^n$$

which is what is desired, the gf for $f_{n+1}$.

share|cite|improve this answer

Your Answer


