Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $A=(a_n)_{n=0}^\infty$ and $B=(b_n)_{n=0}^\infty$ be sequences of real numbers. Let $C = (c_n)_{n=0}^\infty$ be the sequence such that

$$c_n = {a_0}{b_n} + {a_1}{b_{n-1}} +\cdots+ {a_n}{b_0}.$$

Let $G_A(s), G_B(s), G_C(s)$ denote the generating functions of sequences $A,B$ and $C$, respectively.

My textbook claims that $$G_C(s) = \sum_{n=0}^{\infty}{c_n}{s^n} = \sum_{n=0}^{\infty} ({\sum_{k=0}^{n}{a_k}{b_{n-k}}}){s^n}= (\sum_{k=0}^{\infty}{a_k}{s^k})(\sum_{n=k}^{\infty}{b_{n-k}}{s^{n-k}}) = G_A(s) G_B(s).$$

I was able to verify the equality in the finite case via induction. In the infinite case, I think that absolute convergence is necessary. However, the book did not mention anything about this.

Going slightly off topic, I'd like to ask if this is why you cannot use induction to prove that two expressions of $n \in \mathbb N$ are equivalent when $n$ goes to infinity.

In this example, induction does not say any thing about convergence. The instructor in my Analysis class made that point, but I did not really understand it at the time.

share|improve this question
    
My rationale is that if you omit $G_A, G_B, G_C$ and examine the equality strictly from the perspective of series, then absolute convergence is necessary. –  Andy Tam Jun 22 '13 at 19:10
    
One often talks about "generating functions" in cases where the series have radius of convergence zero. The convolution is still OK, and can be used to say what we mean by "product" of the generating functions. –  GEdgar Jun 22 '13 at 19:44
    
I think absolute convergence of one of the two, and convergence of the other will get you convergence of the Cauchy product. –  Michael Hardy Jun 22 '13 at 20:16
1  
Four answers so far, and I'm the only one who's up-voted the question. –  Michael Hardy Jun 22 '13 at 20:24
    
Actually, the definition will not work in finite cases; I made a mistake in my calculation. Also, in my original question, I wrote that $A, B, C$ are series. They are sequences. –  Andy Tam Jun 22 '13 at 20:56
add comment

3 Answers 3

up vote 2 down vote accepted

Convergence is not an issue: these are formal power series, and as such are to be thought of as algebraic objects with an associated ‘arithmetic’, not as real- or complex-valued functions. As Herbert S. Wilf says in generatingfunctionology, ‘A generating function is a clothesline on which we hang up a sequence of numbers for display’. It is in the first instance a convenient way to manipulate the sequence of coefficients. In particular, if $A=\langle a_n:n\in\Bbb N\rangle$ and $B=\langle b_n:n\in\Bbb N\rangle$ are sequence (not series!) of real numbers, we can construct their convolution, $C=\langle c_n:n\in\Bbb N\rangle$, directly, by defining $C_n=\sum_{k=0}^na_kb_{n-k}$, or we can get it ‘automagically’ by taking the product of the generating functions of $A$ and $B$:

$$\begin{align*} G_A(x)G_B(x)&=\left(\sum_{n\ge 0}a_nx^n\right)\left(\sum_{n\ge 0}b_nx^n\right)\\\\ &=\sum_{n\ge 0}\left(\sum_{k=0}^na_kb_{n-k}\right)x^n\\\\ &=G_{A*B}(x)\;. \end{align*}$$

There’s actually nothing to prove here: the step

$$\left(\sum_{n\ge 0}a_nx^n\right)\left(\sum_{n\ge 0}b_nx^n\right)=\sum_{n\ge 0}\left(\sum_{k=0}^na_kb_{n-k}\right)x^n\;,$$

is a matter of definition. We define the product of formal power series to be the Cauchy product, generalizing the ordinary product of polynomials. Chapter $2$ of generatingfunctionology starts with a brief introduction to formal power series; you can freely download the whole book here.

Now it’s true that sometimes we do want to treat generating functions as analytic objects rather than as purely formal algebraic objects, and then we do have to worry about convergence. But when we have convergence, the operations behave as one would expect.

share|improve this answer
    
I found a mistake in my calculation of the finite case: $$\sum_{n=0}^{r}{c_n}{s^n} = \sum_{n=0}^{r} ({\sum_{k=0}^{n}{a_k}{b_{n-k}}}){s^n}= \sum_{k=0}^{r}\left({a_k}{s^k}\sum_{n=k}^{r}{b_{n-k}}{s^{n-k}}\right)$$ So the definition works only in infinite cases. TY for the explanation. –  Andy Tam Jun 22 '13 at 20:52
    
@Andy: You’re welcome. –  Brian M. Scott Jun 22 '13 at 20:53
add comment

Generally speaking, generating functions are discussed as formal power series - that is, as purely algebraic objects, without regards to whether or not they converge. All of the operations that we carry out with them - addition, convolution, differentiation, integration, etc. - are also treated in a purely algebraic context, without regards to convergence.

Of course, you are free to examine the series as an analytical object - for instance, if you are trying to use complex analytic methods to find asymptotics for the coefficients - but in practice I have always just manually dealt with convergence of the new series.

share|improve this answer
    
TY for clarifying. –  Andy Tam Jun 22 '13 at 20:58
add comment

"Going slightly off topic, I'd like to ask if this is why you cannot use induction to prove that two expressions of $n\in\mathbb N$ are equivalent when n goes to infinity."

Indeed, induction only gives you information about the "finite steps" (recall that infinity is not a natural number). To get information about the limiting behaviour (i.e. when you let $n$ go to infinity), you need analysis; induction is a purely set-theoretic/arithmetic statement.

share|improve this answer
    
TY for clarifying. –  Andy Tam Jun 22 '13 at 20:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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