Formal Powerseries: Compute the reciprocal of $1-A(z)$ for $a_0 \ne 0$

Question

Let $A(z)$ be a formal powerseries with $a_0=0$. Show that the reciprocal of $1-A(z)$ is given by

$$B(z) := \sum_{n=0}^\infty A(z)^n = 1 + A(z)^1 + A(z)^2 + \ldots$$

I realise that when we rewrite $C(z) := 1-A(z)$, then the reciprocal of $C$ has to exist since $c_0 \ne 0$. If we let $D(z) := C(z)B(z)$ we are done if we can show that $d_0 = 1$ and $d_n = 0$ for all $n > 0$. We can readily see that $b_0, c_0 = 1$, so $d_0 = 1$. So we are left to compute the remaining $d_n$ for $n > 0$ via the formula

$$d_n = \sum_{k=0}^n c_k b_{n-k}.$$

It is clear that $c_0 = 1$ and $c_n = -a_n$ for $n > 1$, but I do not see how to find a formula for the $b_n$ with $n > 1$. Could you please help me?

Answer 1

We consider $\mathbb{C}[[z]]$, the ring of formal power series with coefficients in $\mathbb{C}$ and show for $A(z)\in\mathbb{C}[[z]]$ with $a_0=[z^0]A(z)=0$: \begin{align*} \color{blue}{\left(1-A(z)\right)^{-1}=\sum_{n=0}A^n(z)}\tag{1} \end{align*} We can show (1) essentially in two steps.

Step 1: At first we claim \begin{align*} \color{blue}{\left(1-z\right)^{-1}=\sum_{n=0}^{\infty}z^n}\tag{2} \end{align*} In order to show (2) we calculate \begin{align*} \color{blue}{(1-z)\sum_{n=0}^{\infty}z^n} =1+(1-1)z+(1-1)z^2+\cdots\color{blue}{=1}\tag{3} \end{align*} and the claim (2) follows.

In this proof we use two facts about formal power series

• The calculation of the coefficients of the product of two formal power series is done using the Cauchy product in the same way as for ordinary generating functions. \begin{align*} A(z)B(z)=\left(\sum_{k=0}^{\infty}a_kz^k\right)\left(\sum_{l=0}^{\infty}b_lz^l\right) =\sum_{n=0}^{\infty}\left(\sum_{k=0}^n a_kb_{n-k}\right) z^n \end{align*} In (3) we have $A(z)=1-z$ and $B(z)=\sum_{n=0}^{\infty}z^n$.

• Two formal power series are equal iff their coefficients are equal for all $n\geq 0$. \begin{align*} A(z)=B(z)\qquad\longleftrightarrow\qquad [z^n]A(z)=[z^n]B(z)\quad n\geq 0 \end{align*} This is used in (3) with $A(z)=(1-z)\sum_{n=0}^{\infty}z^n$ and $B(z)=1$.

Intermezzo: We want to use (3) by substituting $z$ with a formal power series $D(z)$. To guarantee that this kind of substitution is valid we have to assure that always a finite number of operations is involved when doing the calculation. \begin{align*} A(z)=\sum_{n=0}^{\infty}a_nz^n\qquad\longrightarrow\qquad A(D(z))=\sum_{n=0}^{\infty}a_nD^n(z)\tag{4} \end{align*} This finite number of operations does not refer to the countably infinite number of terms in $A(D(z))$ we usually have, but to the number of terms we have to consider when calculating a coefficient $[z^k]A(D(z))$. In fact this is assured iff \begin{align*} \color{blue}{[z^0]D(z)=0}\tag{5} \end{align*} because then we have \begin{align*} [z^n]A(D(z))&=[z^n]\sum_{k=0}^{\infty}a_kD(z)^k\\ &=[z^n]\sum_{k=0}^{\infty}a_k\left(d_1z+d_2z^2+\cdots\right)^k\\ &=\sum_{k=0}^n[z^n]\left(d_1z+d_2z^2+\cdots\right)^k\\ \end{align*} Since the coefficient $[z^0]D(z)=0$ the smallest power of $z$ in $D(z)^k$ is greater or equal to $k$ and we can restrict the calculation of $[z^n]$ in $A(D(z))$ to the finite number of the first $n+1$ summands of the formal power series.

• A family of series is called locally finite if for each coefficient $[z^n]$ the number of series in this family with non-zero coefficient of $[z^n]$ is finite. We observe if (5) is given, the family \begin{align*} \{D^n(z): n\geq 0\} \end{align*} is locally finite.

It turns out that a substitution (4) with a formal power series $D(z)$ is valid whenever the family $\{D^n(z): n\geq 0\}$ is locally finite. We are now well prepared for the second step.

Second step: Let $A(z), B(z), C(z)$ be formal power series in $\mathbb{C}[[z]]$. Let $D(z)\in\mathbb{C}[[z]]$ with $[z^0]D(z)=0$. The following is valid \begin{align*} \color{blue}{A(z)B(z)=C(z)\qquad \longrightarrow \qquad A(D(z))B(D(z))=C(D(z))}\tag{6} \end{align*}

In order to prove the equality of the right-hand side in (6) we have to show that $[z^n]A(D(z))B(D(z))=[z^n]C(D(z))$ for all $n\geq 0$. We obtain \begin{align*} \color{blue}{[z^n]}&\color{blue}{A(D(z))B(D(z))}\\ &=\sum_{k=0}^n[z^k]A(D(z))[z^{n-k}]B(D(z))\\ &=\sum_{k=0}^n\left(\sum_{q=0}^na_q[z^k]D^q(z)\right)\left(\sum_{r=0}^nb_r[z^{n-k}]D^r(z)\right)\\ &=\sum_{q=0}^n\sum_{r=0}^na_qb_r\sum_{k=0}^n[z^k]D^q(z)[z^{n-k}]D^{r}(z)\\ &=\sum_{q=0}^n\sum_{r=0}^na_qb_r[z^n]D^{q+r}(z)\tag{7}\\ &=\sum_{{0\leq q+r\leq n}\atop{q,r\geq 0}}a_qb_r[z^n]D^{q+r}(z)\\ &=\sum_{m=0}^{n}\sum_{q=0}^{m}a_qb_{m-q}[z^n]D^{m}(z)\\ &=[z^n]\sum_{m=0}^{\infty}\sum_{q=0}^{m}a_qb_{m-q}[z^n]D^{m}(z)\\ &\;\color{blue}{=[z^n]C(D(z))} \end{align*} and the claim (6) follows.

Comment: In (7) we observe that $[z^n]D^{q+r}=0$ if $q+r>n$, so that we can restrict the index region in the next line.

Looking at OPs stated problem and noting that $[z^0]A(z)=0$, so that $\{A^n(z): n\geq 0\}$ is a locally finite family we can apply (6) and obtain from (3) by substituting $z$ with $A(z)$: \begin{align*} \color{blue}{\left(1-A(z)\right)\sum_{n=0}^{\infty}A^n(z)=1} \end{align*} where we set in (6) $A(z):=1-z, B(z):=\sum_{n=0}^{\infty}z^n, C(z):=1$ and $D(z):= A(z)$.

Note: This approach is nicely elaborated in chapter 7 of Discrete Calculus: Methods for Counting by C. Mariconda and A. Tonolo.

Answer 2

The formula for $b_n$ is a little unwieldy, but it is possible to prove this without computing $b_n$ exactly. We use the same proof idea for the corresponding statement for real numbers: $$ \frac1{1-x}=1+x+x^2+\dots\quad (|x|<1) $$ The proof is $$ \begin{align} (1-x)(1+x+x^2+\dots) &=(1-x)\left(\lim_{N\to\infty}1+x+\dots+x^{N-1}\right) \\&=\lim_{N\to\infty} (1-x)(1+x+\dots+x^{N-1}) \\&=\lim_{N\to\infty}(1-x^N)\tag{cancellation} \\&=1 \end{align} $$ We do this same proof, replacing $x$ with $A(z)$. However, in what sense can we say that $\lim_{N\to\infty} [A(z)]^N=0$? These are just formula power series, they do not necessarily have real number values.

Still, the concept of a limit makes sense for formal power series. If $F_1(x), F_2(x),\dots$ is a sequence of power series, we say that $\lim_{n\to\infty} F_n(x)=G(x)$ if the following holds. Here, $F_n(x)=\sum_i f_{n,i}x^i$, and $G(x)=\sum_i g_ix^i$.

For all $i\in \mathbb N$, there exists $N(i)\in \mathbb N$ so $j\ge N(i)$ implies $f_{i,j}=g_i$.

This is the definition of limit used to define the infinite sum $\sum_{n=0}^\infty A(z)^n$ in the first place. Now, you should be able to show $A(z)^N\to 0$ in this sense. Here is where we need the fact that $a_0=0$; this ensures that $z^N$ divides $[A(z)]^N$, so that the first $N$ coefficients of $[A(z)]^N$ are zero.

You also need to show that you can bring the $1-A(z)$ inside the limit. That is, you need to use the general fact that $H(x)\lim_n F_n(x)=\lim_n H(x)F_n(x)$. This is straightforward to prove.

Answer 3

I use the notation $[z^n]F(z)$ to denote the coefficient of $z^n$ in $F(z)$.

If you really want/need to compute $b_n$ exactly, here is how you do it. Note that $$ [z^n]A(z)^2=a_1a_{n-1}+a_2a_{n-2}\dots+a_{n-1}a_1,\\ [z^n]A(z)^3=a_1a_1a_{n-2}+a_1a_2a_{n-3}+\dots+a_{n-2}a_1a_1\\ \vdots $$ In general, $[z^n]A(z)^k$ is the sum of $$ a_{i(1)}a_{i(2)}\cdots a_{i(k)}, $$

ranging over all finite lists $[i(1),\dots,i(k)]$ with length $k$ of positive integers whose sum is $n$. Therefore, $b_n$ is a similar sum over finite lists, but with length ranging anywhere from $1$ to $n$. For example, $$ b_4=(a_4)+(a_1a_3+a_2a_2+a_3a_1)+(a_1a_1a_2+a_1a_2a_1+a_2a_1a_1)+(a_1a_1a_1a_1) $$ A special case is $b_0=1$. Now, you need to argue why the $z^n$ coefficient of $(1-A(z))B(z)$ is equal to $1$ when $n=0$ and $0$ otherwise. That is, why is $$ b_n-a_1b_{n-1}-a_2b_{n-2}-\dots-a_{n-1}b_1=0,\quad (n\ge 1) $$ There is a combinatorial proof of this. $b_n$ is a sum of lists, and each list is subtracted away by exactly one of the $a_ib_{n-i}$'s. Namely, if the list starts with $a_s$, then it is canceled by a term in $a_sb_{n-s}$.