1
$\begingroup$

In many books on generating functions author performs following operation to shift coefficients of $F(x) = \sum_i f_ix^i$ to the left $${F(x) - f_0} \over x$$ which in can be written as $$(F(x) - f_0) \times {1 \over x}$$ I do not understand why they can do that if generating function $x$ does not have any reciprocal so expression like $1 \over x$ does not make sense for generating function. Yet almost every author uses this trick.

$\endgroup$
  • $\begingroup$ Why shouldn't it make sense, it's just formally canceling one power of $x$. $\endgroup$ – Adam Hughes Jan 29 '15 at 19:57
  • $\begingroup$ @AdamHughes please read my post again. There is no reciprocal of $x$ in formal power series ring so you can not divide by $x$ because division is multiplication by reciprocal and since there is no reciprocal of $x$ division by $x$ does not make sense. $\endgroup$ – Trismegistos Jan 30 '15 at 12:08
  • $\begingroup$ You're over-thinking this: formal operations don't really care since all it does is reindex. Take a power series that actually converges in some neighborhood of 0, and you'll note division is fine, we adopt the convention of using such division for reindexing because in practice it doesn't really matter that $1/x$ is not in it. $\endgroup$ – Adam Hughes Jan 30 '15 at 17:48
1
$\begingroup$

Generating functions (with real coefficients) live in the ring $\mathbb{R}[[x]]$ of formal power series over $\mathbb{R}$ (see http://en.wikipedia.org/wiki/Formal_power_series). You are quite right that $x$ is not invertible in this ring (its group of units comprises precisely the series with non-zero constant term). However $\mathbb{R}[[x]]$ embeds in the field $\mathbb{R}((x))$ of formal Laurent series over $\mathbb{R}$ (see http://en.wikipedia.org/wiki/Formal_power_series#Formal_Laurent_series), in which $x$ is invertible. So the apparent abuse of notation can be made rigorous by stating that you are working in $\mathbb{R}((x))$.

$\endgroup$
  • $\begingroup$ I generally notice that treatment of generating functions are very sloppy in every book I've read. It is common for author to do trick which they were not proved to work or even are proven not to work e.g. dividing by $x$ in formal power series ring (not formal Laurent series). Do you know any books that would approach topic of formal power (or Laurent) series rigorously? $\endgroup$ – Trismegistos Jan 30 '15 at 10:17
  • $\begingroup$ Msc Lane & Birkhoff's Algebra is a good reference for formal power series. $\endgroup$ – Rob Arthan Jan 30 '15 at 17:09
0
$\begingroup$

\begin{equation} F(x) = f_0 + f_1x + f_2x^2 + \ldots \end{equation} Therefore we get that \begin{equation} F(x)-f_0 = f_1x + f_2x^2 + \ldots = x(f_1 + f_2x + \ldots) \end{equation} As you can see this expression is divisible by $x$.

$\endgroup$
  • $\begingroup$ This expression if treated as power series is not divisible by $x$. Because there is no reciprocal of $x$ in formal power series ring. $\endgroup$ – Trismegistos Jan 30 '15 at 10:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.