How to formalize substitutions in generating functions?

272 Views Asked by At

In my linear algebra course we recently defined generating functions as elements of the ring $R[[x]]$ formal power series over a Ring $R$. If you consider $x$ to be a formal power series corresponding to the sequence $(0, 1, 0, 0,\dots)$ you can take the inverse (in $R[[x]]^\times$) of $1+x$ and show it to be

$$\frac1{1+x} = \sum_{k=0}^\infty (-1)^k x^k \tag{1}$$

From this we wanted to derive, by substituting $x \to -x$ that

$$\frac1{1-x} = \sum_{k=0}^\infty x^k \tag{2}$$

Intuitively this should work and its easy to prove, that $1/(1-x)$ is the generating function of the series in $(2)$. However I'm not really sure how I should interpret this substitution (or other substitution like $x \to x^2$) in a rigorous way.

So my question is how would you formalize the deduction $(1) \Rightarrow (2)$ and more generally proofs using substitution in generating functions?

1

There are 1 best solutions below

7
On BEST ANSWER

There's a ring homomorphism $\phi: R[X] \to R[X]$ given by $X \mapsto -X$. This isomorphism takes $\sum_{k=0}^{\infty} (-1)^k x^k$ and outputs $\sum_{k=0}^{\infty} x^k$.

You've shown already that $\sum_{k=0}^{\infty} (-1)^k x^k \times (1+x) = 1$; so this holds when you apply $\phi$, yielding $\phi(\sum_{k=0}^{\infty} (-1)^k x^k) \times \phi(1+x) = 1$. That is, $\phi(\frac{1}{1+x}) = \frac{1}{1-x}$. The left-hand side is just $\sum_{k=0}^{\infty} x^k$.