# Seeking a Purely Formal Power Series Solution

Seeking a Purely Formal Power Series Solution

Suppose that the set of nonnegative integers is partitioned into a finite number of infinite arithmetical progressions with common differences $$r_1, r_2, \ldots r_n$$ and first terms $$a_1, a_2, \ldots, a_n$$. Then prove that $$\frac{1}{r_1}+\frac{1}{r_2}+\cdots+\frac{1}{r_n}=1.$$

Solution. Since the set of nonnegative integers is partitioned by the progressions starting with ( a_i ) with difference ( r_i ), $$\left(X^{a_1}+X^{a_1+r_1}+X^{a_1+2r_1}+\cdots\right)+\cdots+\left(X^{a_n}+X^{a_n+r_n}+X^{a_n+2r_n}+\cdots\right)=X^0+X^1+X^2+\cdots.$$

Using the formula for a geometric series, we have $$\frac{X^{a_1}}{1-X^{r_1}}+\frac{X^{a_2}}{1-X^{r_2}}+\cdots+\frac{X^{a_n}}{1-X^{r_n}}=\frac{1}{1-X}.$$

Multiplying both sides by $$1-X$$ gives us $$\frac{X^{a_1}}{1+X+X^2+\cdots+X^{r_1-1}}+\frac{X^{a_2}}{1+X+X^2+\cdots+X^{r_2-1}}+\cdots+\frac{X^{a_n}}{1+X+X^2+\cdots+X^{r_n-1}}=1.$$

Now, taking the limit as $$X$$ approaches 1 gives us $$\frac{1}{r_1}+\frac{1}{r_2}+\cdots+\frac{1}{r_n}=1$$, as desired.

I understand the solution. However, I tried to think about whether we can achieve the same conclusion using purely formal power series (since this structure does not allow us to substitute values for $$X$$ or compute limits). What does $$\frac{1}{r_i}$$ mean in the context of formal power series? I thought about considering the coefficient of $$X^n$$, but it did not help.

• The generating function proofs are cute, but for this result they seem like overkill, and obscure the basic intuition. A much simpler proof: Let $N$ be the product of all the progression differences $r_i$ (or any common multiple of them all). Then $\{1,\ldots,N\}$ contains $N/r_i$ elements from the $i$th progression, and is partitioned by subsets, so $N = \sum_i N/r_i$. The result follows immediately. Commented Jul 16 at 9:23

It is not necessary to take the limit as $$x \to 1$$. What you have at the end there is just a rational function of $$x$$, and you can just substitute $$x = 1$$ in a completely ordinary way. This can be done completely formally as follows.

It is true that the entire ring $$K[[x]]$$ of formal power series does not have an evaluation homomorphism sending $$x$$ to $$1$$. However, it has subrings that do. The most obvious one is the subring $$K[x]$$ of polynomials; polynomials can be evaluated at any element of $$K$$ in the usual way. Less obviously, $$K[[x]]$$ also contains as a subring the $$K$$-algebra of rational functions in $$K(x)$$ whose denominator in lowest terms is not divisible by $$x$$; this is because all such rational functions have formal power series expansions. Within this subring is the $$K$$-algebra of rational functions in $$K(x)$$ whose denominator in lowest terms is not divisible by either $$x$$ or $$x - 1$$; for these rational functions $$\frac{p(x)}{q(x)}$$ there is a perfectly well-defined evaluation homomorphism at $$x = 1$$ which is just given by $$\frac{p(1)}{q(1)}$$. (This subring is a localization of $$K[x]$$.)

One way of describing what's going on before multiplying by $$1 - x$$ is the following. Over $$\mathbb{C}$$, if $$f(z)$$ is a meromorphic function then recall that its residue at a point $$z = a$$ can be computed as

$$\text{Res}_a(f) = \frac{1}{2 \pi i} \oint_{\gamma} f(z) \, dz$$

where $$\gamma$$ is a counterclockwise contour around $$a$$ not containing any other poles of $$f$$, and the significance of this number is that $$f(z) - \frac{\text{Res}_a(f)}{z - a}$$ has an analytic antiderivative in a punctured neighborhood of $$a$$; equivalently, in the Laurent series expansion of $$f$$ at $$a$$, $$\frac{\text{Res}_a(f)}{z - a}$$ is the first nonconstant term.

This second definition of the residue allows us to define the formal residue $$\text{Res}_a(r(x))$$ of a rational function $$r(x)$$ at a point $$x = a$$ over any field $$K$$ in terms of its Laurent series expansion at $$a$$. An alternative and more clearly algebraic definition is to consider the partial fraction decomposition of $$r(x)$$, and to take the coefficient of $$\frac{1}{x - a}$$ in this decomposition.

The formal residue has the property that if the rational function $$s(x) = (x - a) r(x)$$ in lowest terms has a denominator not divisible by $$a$$ then

$$\text{Res}_a(r) = s(a)$$

can be computed by just evaluating $$s(x)$$ at $$a$$; this is what is happening in your computation, you are just computing $$\text{Res}_1$$ of both sides.

Now, what does this computation mean? In the context of generating functions, if $$A(z) = \sum a_n z^n$$ is a meromorphic generating function with the property that the coefficients $$a_n$$ tend to a limit as $$n \to \infty$$, then the residue $$\text{Res}_1(A)$$ computes this limit. In these examples where $$A(z)$$ is the generating function of an arithmetic progression this limit does not exist but the Cesàro averages $$\frac{a_1 + \dots + a_n}{n}$$ tend to a limit, and the residue $$\text{Res}_1(A)$$ computes this limit; in other words, it computes the average value of the coefficients $$a_i$$.

For an arithmetic progression with common difference $$r_1$$, the residue $$\frac{1}{r_1}$$ of the generating function can therefore be interpreted as the natural density of the arithmetic progression, so the generating function is telling us that in order for a bunch of arithmetic progressions to exactly cover $$\mathbb{N}$$ their natural densities must sum to $$1$$. So the whole argument can be rephrased in terms of natural density (we just show that the natural density of an arithmetic progression with common difference $$r$$ is $$\frac{1}{r}$$ and that natural density is finitely additive), without the extra fluff of generating functions at all, which is arguably a distraction and makes the argument both more complicated and less conceptual.

• I follow your account and I know you are very knowledgeable. However, I haven't fully understood what I read above. I am just a high school student! Can you help me understand this within the scope of formal power series operations? Or with the least amount of knowledge possible. Thank you! Commented Jul 16 at 2:25
• @Math_fun2006: it simply is not a formal power series operation, in the sense that we are not applying an operation which can be applied to an arbitrary formal power series. We are applying an operation which can be applied to rational functions, which embed into formal power series, and all of the generating functions occurring here are rational. If you prefer you can completely ignore the rest of the answer and just read the very first paragraph. Do you know what I mean when I say you can plug $x = 1$ into a rational function? Commented Jul 16 at 3:28
• Thank you, I understand that when substituting $x = 1$, the nature of both sides being rational functions makes that substitution valid. What I desire is for the solution to fit entirely within the framework of formal power series. I believe it can be presented that way, and I will continue to think about it. Thank you once again. Commented Jul 16 at 3:49
• @Math_fun2006: if by "fit entirely within the framework of formal power series" you mean only applying operations valid on arbitrary formal power series, this is not possible. Consider the simplest nontrivial case, the partition of the natural numbers into the even and odd natural numbers, which corresponds to $\frac{1}{1 - x^2} + \frac{x}{1 - x^2} = \frac{1}{1 - x}$. Multiplying by $1 - x$ gives $\frac{1}{1 + x} + \frac{x}{1 + x} = 1$. Substituting $x = 1$ gives $\frac{1}{2} + \frac{1}{2} = 1$ as expected. But what does this mean as an operation on formal power series? Commented Jul 16 at 4:09
• We have $\frac{1}{1 + x} = 1 - x + x^2 - x^3 + x^4 \mp \dots$. This is a perfectly sensible formal power series but there is no way to plug $x = 1$ into it and get a number out. We have to know that this is not just a totally arbitrary formal power series but in fact the formal power series expansion of a rational function to make sense of what it means to plug $x = 1$ into it. Commented Jul 16 at 4:10