View source for Cauchy product

{{Short description|Concept in mathematics}}
In [[mathematics]], more specifically in [[mathematical analysis]], the '''Cauchy product''' is the discrete [[convolution]] of two [[Series (mathematics)|infinite series]]. It is named after the French mathematician [[Augustin-Louis Cauchy]].

==Definitions==
The Cauchy product may apply to infinite series<ref>{{harvnb|Canuto|Tabacco|2015|p=20}}.</ref><ref>{{harvnb|Bloch|2011|p=463}}.</ref> or power series.<ref>{{harvnb|Canuto|Tabacco|2015|p=53}}.</ref><ref>{{harvnb|Mathonline|loc=Cauchy Product of Power Series}}.</ref> When people apply it to finite sequences<ref>{{harvnb|Weisstein|loc=Cauchy Product}}.</ref> or finite series, that can be seen merely as a particular case of a product of series with a finite number of non-zero coefficients (see [[Convolution#Discrete convolution|discrete convolution]]).

[[Convergence (mathematics)|Convergence]] issues are discussed in the [[#Convergence and Mertens' theorem|next section]].

===Cauchy product of two infinite series===

Let <math display="inline"> \sum_{i=0}^\infty a_i</math> and <math display="inline"> \sum_{j=0}^\infty b_j</math> be two [[infinite series]] with complex terms. The Cauchy product of these two infinite series is defined by a discrete convolution as follows:

:<math>\left(\sum_{i=0}^\infty a_i\right) \cdot \left(\sum_{j=0}^\infty b_j\right) = \sum_{k=0}^\infty c_k</math> &nbsp; &nbsp; where &nbsp; &nbsp; <math>c_k=\sum_{l=0}^k a_l b_{k-l}</math>.

===Cauchy product of two power series===

Consider the following two [[power series]]

:<math>\sum_{i=0}^\infty a_i x^i</math> &nbsp; &nbsp; and &nbsp; &nbsp; <math>\sum_{j=0}^\infty b_j x^j</math>

with complex coefficients <math>\{a_i\}</math> and <math>\{b_j\}</math>. The Cauchy product of these two power series is defined by a discrete convolution as follows:

:<math>\left(\sum_{i=0}^\infty a_i x^i\right) \cdot \left(\sum_{j=0}^\infty b_j x^j\right) = \sum_{k=0}^\infty c_k x^k</math> &nbsp; &nbsp; where &nbsp; &nbsp; <math>c_k=\sum_{l=0}^k a_l b_{k-l}</math>.

==Convergence and Mertens' theorem==
{{distinguish|text=[[Mertens' theorems]] concerning distribution of prime numbers}}

Let {{math|(''a<sub>n</sub>'')<sub>''n''≥0</sub>}} and {{math|(''b<sub>n</sub>'')<sub>''n''≥0</sub>}} be real or complex sequences. It was proved by [[Franz Mertens]] that, if the series <math display="inline"> \sum_{n=0}^\infty a_n</math> [[Convergent series|converges]] to {{math|''A''}} and <math display="inline"> \sum_{n=0}^\infty b_n</math> converges to {{math|''B''}}, and at least one of them [[Absolute convergence|converges absolutely]], then their Cauchy product converges to {{math|''AB''}}.<ref>{{cite book |last1=Rudin |first1=Walter |title=Principles of Mathematical Analysis |date=1976 |publisher=McGraw-Hill |page=74}}</ref> The theorem is still valid in a [[Banach algebra]] (see first line of the following proof).

It is not sufficient for both series to be convergent; if both sequences are [[conditional convergence|conditionally convergent]], the Cauchy product does not have to converge towards the product of the two series, as the following example shows:

===Example===
Consider the two [[alternating series]] with

<math display="block">a_n = b_n = \frac{(-1)^n}{\sqrt{n+1}}\,,</math>

which are only conditionally convergent (the divergence of the series of the absolute values follows from the [[direct comparison test]] and the divergence of the [[harmonic series (mathematics)|harmonic series]]). The terms of their Cauchy product are given by

<math display="block">c_n = \sum_{k=0}^n \frac{(-1)^k}{\sqrt{k+1}} \cdot \frac{ (-1)^{n-k} }{ \sqrt{n-k+1} } = (-1)^n \sum_{k=0}^n \frac{1}{ \sqrt{(k+1)(n-k+1)} }</math>

for every integer {{math|''n'' ≥ 0}}. Since for every {{math|''k'' ∈ {{mset|0, 1, ..., ''n''}}}} we have the inequalities {{math|''k'' + 1 ≤ ''n'' + 1}} and {{math|''n'' – ''k'' + 1 ≤ ''n'' + 1}}, it follows for the square root in the denominator that {{math|{{sqrt|(''k'' + 1)(''n'' − ''k'' + 1)}} ≤ ''n'' +1}}, hence, because there are {{math|''n'' + 1}} summands,

<math display="block">|c_n| \ge \sum_{k=0}^n \frac{1}{n+1} = 1</math>

for every integer {{math|''n'' ≥ 0}}. Therefore, {{math|''c<sub>n</sub>''}} does not converge to zero as {{math|''n'' → ∞}}, hence the series of the {{math|(''c<sub>n</sub>'')<sub>''n''≥0</sub>}} diverges by the [[term test]].

===Proof of Mertens' theorem===
For simplicity, we will prove it for complex numbers. However, the proof we are about to give is formally identical for an arbitrary [[Banach algebra]] (not even commutativity or associativity is required).

Assume [[without loss of generality]] that the series <math display="inline"> \sum_{n=0}^\infty a_n</math> converges absolutely.
Define the [[partial sums]]

<math display="block">A_n = \sum_{i=0}^n a_i,\quad B_n = \sum_{i=0}^n b_i\quad\text{and}\quad C_n = \sum_{i=0}^n c_i</math>

with

<math display="block">c_i=\sum_{k=0}^ia_kb_{i-k}\,.</math>

Then

<math display="block">C_n = \sum_{i=0}^n  a_{n-i}B_i</math>

by rearrangement, hence

{{NumBlk|:|<math>C_n = A_nB+\sum_{i=0}^na_{n-i}(B_i-B)\,.</math>|{{EquationRef|1}}}}

Fix {{math|''ε'' > 0}}. Since <math display="inline"> \sum_{k \in \N} |a_k| < \infty</math> by absolute convergence, and since {{math|''B<sub>n</sub>''}} converges to {{math|''B''}} as {{math|''n'' → ∞}}, there exists an integer {{math|''N''}} such that, for all integers {{math|''n'' ≥ ''N''}},

{{NumBlk|:|<math>|B_n-B|\le\frac{\varepsilon/3}{\sum_{ k \in \N } |a_k|+1}</math>|{{EquationRef|2}}}}

(this is the only place where the absolute convergence is used). Since the series of the {{math|(''a<sub>n</sub>'')<sub>''n''≥0</sub>}} converges, the individual {{math|''a<sub>n</sub>''}} must converge to 0 by the [[term test]]. Hence there exists an integer {{math|''M''}} such that, for all integers {{math|''n'' ≥ ''M''}},

{{NumBlk|:|<math>|a_n|\le\frac{\varepsilon}{3N(\max_{ i\in\{0,\dots,N-1\} } |B_i-B|+1)}\,. </math>|{{EquationRef|3}}}}

Also, since {{math|''A<sub>n</sub>''}} converges to {{math|''A''}} as {{math|''n'' → ∞}}, there exists an integer {{math|''L''}} such that, for all integers {{math|''n'' ≥ ''L''}},

{{NumBlk|:|<math>|A_n-A|\le\frac{\varepsilon/3}{|B|+1}\,.</math>|{{EquationRef|4}}}}

Then, for all integers {{math|''n'' ≥ max{{mset|''L'', ''M'' + ''N''}}}}, use the representation ({{EquationNote|1}}) for {{math|''C<sub>n</sub>''}}, split the sum in two parts, use the [[triangle inequality]] for the [[absolute value]], and finally use the three estimates ({{EquationNote|2}}), ({{EquationNote|3}}) and ({{EquationNote|4}}) to show that

<math display="block">\begin{align}
|C_n - AB| &= \biggl|(A_n-A)B+\sum_{i=0}^n a_{n-i}(B_i-B)\biggr| \\
 &\le {}\underbrace{|A_n-A|\,|B|}_{\le\,\varepsilon/3\text{ by (4)}}+\sum_{i=0}^{N-1}\underbrace{|a_{\underbrace{\scriptstyle n-i}_{\scriptscriptstyle \ge M}}|\,|B_i-B|}_{\le\,\varepsilon/3\text{ by (3)}}+{}\underbrace{\sum_{i=N}^n |a_{n-i}|\,|B_i-B|}_{\le\,\varepsilon/3\text{ by (2)}}\le\varepsilon\,. 
\end{align}</math>

By the [[Convergent series|definition of convergence of a series]], {{math|''C<sub>n</sub>'' → ''AB''}} as required.

==Cesàro's theorem==
<!-- [[Cesàro's theorem]] redirects here -->

In cases where the two sequences are convergent but not absolutely convergent, the Cauchy product is still [[Cesàro summation|Cesàro summable]].<ref>{{Cite book |last=Hardy |first=Godfrey H. |title=Divergent series |date=2000 |publisher=AMS Chelsea Publ |isbn=978-0-8218-2649-2 |edition=2. , (textually unaltered) ed., repr |location=Providence, RI}}</ref>  Specifically:

If <math display="inline"> (a_n)_{n \geq 0}</math>, <math display="inline"> (b_n)_{n \geq 0}</math> are real sequences with <math display="inline"> \sum a_n\to A</math> and <math display="inline"> \sum b_n\to B</math> then

<math display="block">\frac{1}{N}\left(\sum_{n=1}^N\sum_{i=1}^n\sum_{k=0}^i a_k b_{i-k}\right)\to AB.</math>

This can be generalised to the case where the two sequences are not convergent but just Cesàro summable:

===Theorem===
For <math display="inline"> r>-1</math> and <math display="inline"> s>-1</math>, suppose the sequence <math display="inline"> (a_n)_{n \geq 0}</math> is <math display="inline"> (C,\; r)</math> summable with sum ''A'' and <math display="inline"> (b_n)_{n \geq 0}</math> is <math display="inline"> (C,\; s)</math> summable with sum ''B''. Then their Cauchy product is <math display="inline"> (C,\; r+s+1)</math> summable with sum ''AB''.

==Examples==

* For some <math display="inline"> x,y \in \Reals</math>, let <math display="inline"> a_n = x^n/n!</math> and <math display="inline"> b_n = y^n/n!</math>.  Then <math display="block"> c_n = \sum_{i=0}^n\frac{x^i}{i!}\frac{y^{n-i}}{(n-i)!} = \frac{1}{n!} \sum_{i=0}^n \binom{n}{i} x^i y^{n-i} = \frac{(x+y)^n}{n!}</math> by definition and the [[binomial formula]].  Since, [[formal series|formally]], <math display="inline"> \exp(x) = \sum a_n</math> and <math display="inline"> \exp(y) = \sum b_n</math>, we have shown that <math display="inline"> \exp(x+y) = \sum c_n</math>.  Since the limit of the Cauchy product of two [[absolute convergence|absolutely convergent]] series is equal to the product of the limits of those series, we have proven the formula <math display="inline"> \exp(x+y) = \exp(x)\exp(y)</math> for all <math display="inline"> x,y \in \Reals</math>.
* As a second example, let <math display="inline"> a_n = b_n = 1</math> for all <math display="inline"> n \in \N</math>. Then <math display="inline"> c_n = n+1</math> for all <math>n \in \N</math> so the Cauchy product <math display="block"> \sum c_n = (1,1+2,1+2+3,1+2+3+4,\dots)</math> does not converge.

==Generalizations==

All of the foregoing applies to sequences in <math display="inline"> \Complex</math> ([[complex number]]s).  The '''Cauchy product''' can be defined for series in the <math display="inline"> \R^n</math> spaces ([[Euclidean spaces]]) where multiplication is the [[inner product]].  In this case, we have the result that if two series converge absolutely then their Cauchy product converges absolutely to the inner product of the limits.

=== Products of finitely many infinite series ===
Let <math>n \in \N</math> such that <math>n \ge 2</math> (actually the following is also true for <math>n=1</math> but the statement becomes trivial in that case) and let <math display="inline">\sum_{k_1 = 0}^\infty a_{1, k_1}, \ldots, \sum_{k_n = 0}^\infty a_{n, k_n}</math> be infinite series with complex coefficients, from which all except the <math>n</math>th one converge absolutely, and the <math>n</math>th one converges. Then the limit
<math display="block">\lim_{N\to\infty}\sum_{k_1+\ldots+k_n\leq N} a_{1,k_1}\cdots a_{n,k_n}</math>
exists and we have:
<math display="block">\prod_{j=1}^n \left( \sum_{k_j = 0}^\infty a_{j, k_j} \right)=\lim_{N\to\infty}\sum_{k_1+\ldots+k_n\leq N} a_{1,k_1}\cdots a_{n,k_n}</math>
=== Proof ===
Because
<math display="block">\forall N\in\mathbb N:\sum_{k_1+\ldots+k_n\leq N}a_{1,k_1}\cdots a_{n,k_n}=\sum_{k_1 = 0}^N \sum_{k_2 = 0}^{k_1} \cdots \sum_{k_n = 0}^{k_{n-1}}a_{1, k_n} a_{2, k_{n-1} - k_n} \cdots a_{n, k_1 - k_2}</math>
the statement can be proven by induction over <math>n</math>: The case for <math>n = 2</math> is identical to the claim about the Cauchy product. This is our induction base.

The induction step goes as follows: Let the claim be true for an <math>n \in \N</math> such that <math>n \ge 2</math>, and let <math display="inline">\sum_{k_1 = 0}^\infty a_{1, k_1}, \ldots, \sum_{k_{n+1} = 0}^\infty a_{n+1, k_{n+1}}</math> be infinite series with complex coefficients, from which all except the <math>n+1</math>th one converge absolutely, and the <math>n+1</math>-th one converges. We first apply the induction hypothesis to the series <math display="inline">\sum_{k_1 = 0}^\infty |a_{1, k_1}|, \ldots, \sum_{k_n = 0}^\infty |a_{n, k_n}|</math>. We obtain that the series
<math display="block">\sum_{k_1 = 0}^\infty \sum_{k_2 = 0}^{k_1} \cdots \sum_{k_n = 0}^{k_{n-1}} |a_{1, k_n} a_{2, k_{n-1} - k_n} \cdots a_{n, k_1 - k_2}|</math>
converges, and hence, by the triangle inequality and the sandwich criterion, the series
<math display="block">\sum_{k_1 = 0}^\infty \left| \sum_{k_2 = 0}^{k_1} \cdots \sum_{k_n = 0}^{k_{n-1}} a_{1, k_n} a_{2, k_{n-1} - k_n} \cdots a_{n, k_1 - k_2} \right|</math>
converges, and hence the series
<math display="block">\sum_{k_1 = 0}^\infty \sum_{k_2 = 0}^{k_1} \cdots \sum_{k_n = 0}^{k_{n-1}} a_{1, k_n} a_{2, k_{n-1} - k_n} \cdots a_{n, k_1 - k_2}</math>
converges absolutely. Therefore, by the induction hypothesis, by what Mertens proved, and by renaming of variables, we have:
<math display="block">\begin{align}
\prod_{j=1}^{n+1} \left( \sum_{k_j = 0}^\infty a_{j, k_j} \right) & = \left( \sum_{k_{n+1} = 0}^\infty \overbrace{a_{n+1, k_{n+1}}}^{=:a_{k_{n+1}}} \right) \left( \sum_{k_1 = 0}^\infty \overbrace{\sum_{k_2 = 0}^{k_1} \cdots \sum_{k_n = 0}^{k_{n-1}} a_{1, k_n} a_{2, k_{n-1} - k_n} \cdots a_{n, k_1 - k_2}}^{=:b_{k_1}} \right) \\

& =  \left( \sum_{k_1 = 0}^\infty \overbrace{\sum_{k_2 = 0}^{k_1} \sum_{k_3 = 0}^{k_2} \cdots \sum_{k_n = 0}^{k_{n-1}} a_{1, k_n} a_{2, k_{n-1} - k_n} \cdots a_{n, k_1 - k_2}}^{=:a_{k_1}} \right) \left ( \sum_{k_{n+1} = 0}^\infty \overbrace{a_{n+1, k_{n+1}}}^{=:b_{k_{n+1}}} \right)  \\

& =  \left( \sum_{k_1 = 0}^\infty \overbrace{\sum_{k_3 = 0}^{k_1} \sum_{k_4 = 0}^{k_3} \cdots \sum_{k_n+1 = 0}^{k_{n}} a_{1, k_{n+1}} a_{2, k_{n} - k_{n+1}} \cdots a_{n, k_1 - k_3}}^{=:a_{k_1}} \right) \left ( \sum_{k_{2} = 0}^\infty \overbrace{a_{n+1, k_{2}}}^{=:b_{n+1,k_{2}}=:b_{k_{2}}} \right)  \\

& =  \left( \sum_{k_1 = 0}^\infty a_{k_1} \right) \left ( \sum_{k_{2} = 0}^\infty b_{k_2} \right)  \\

& =  \left( \sum_{k_1 = 0}^\infty \sum_{k_{2} = 0}^{k_1} a_{k_2}b_{k_1 - k_2} \right)  \\

& =  \left( \sum_{k_1 = 0}^\infty \sum_{k_{2} = 0}^{k_1} \left ( \overbrace{\sum_{k_3 = 0}^{k_2} \cdots \sum_{k_n+1 = 0}^{k_{n}} a_{1, k_{n+1}} a_{2, k_{n} - k_{n+1}} \cdots a_{n, k_2 - k_3}}^{=:a_{k_2}} \right) \left ( \overbrace{a_{n+1, k_1 - k_2}}^{=:b_{k_1 - k_2}}  \right) \right)  \\

& =  \left( \sum_{k_1 = 0}^\infty \sum_{k_{2} = 0}^{k_1}  \overbrace{\sum_{k_3 = 0}^{k_2} \cdots \sum_{k_n+1 = 0}^{k_{n}} a_{1, k_{n+1}} a_{2, k_{n} - k_{n+1}} \cdots a_{n, k_2 - k_3}}^{=:a_{k_2}} \overbrace{a_{n+1, k_1 - k_2}}^{=:b_{k_1 - k_2}}   \right)  \\


& = \sum_{k_1 = 0}^\infty \sum_{k_2 = 0}^{k_1} a_{n+1, k_1 - k_2} \sum_{k_3 = 0}^{k_2} \cdots \sum_{k_{n+1} = 0}^{k_n} a_{1, k_{n+1}} a_{2, k_n - k_{n+1}} \cdots a_{n, k_2 - k_3}
\end{align}</math>
Therefore, the formula also holds for <math>n+1</math>.

== Relation to convolution of functions ==
A finite sequence can be viewed as an infinite sequence with only finitely many nonzero terms, or in other words as a function <math>f: \N \to \Complex</math> with finite support. For any complex-valued functions ''f'', ''g'' on <math>\N</math> with finite support, one can take their [[convolution (mathematics)|convolution]]:
<math display="block">(f * g)(n) = \sum_{i + j = n} f(i) g(j).</math>
Then <math display="inline">\sum (f *g)(n)</math> is the same thing as the Cauchy product of <math display="inline">\sum f(n)</math> and <math display="inline">\sum g(n)</math>.

More generally, given a [[monoid]] ''S'', one can form the [[semigroup algebra]] <math>\Complex[S]</math> of ''S'', with the multiplication given by convolution. If one takes, for example, <math>S = \N^d</math>, then the multiplication on <math>\Complex[S]</math> is a generalization of the Cauchy product to higher dimension.

==Notes==
{{reflist}}

==References==
*{{Citation
 | first = Tom M.
 | last = Apostol
 | authorlink = Tom M. Apostol
 | title = Mathematical Analysis
 | edition = 2nd
 | year = 1974
 | publisher = Addison Wesley
 | isbn = 978-0-201-00288-1
 | page=204
}}.

*{{Citation
 | first = Ethan D.
 | last = Bloch
 | title = The Real Numbers and Real Analysis
 | publisher = [[Springer Science+Business Media|Springer]]
 | year = 2011
 | isbn = 9780387721767
 | url=https://books.google.com/books?id=r0qcU9U2_I4C&q=%22Cauchy+product%22
}}.

*{{Citation
 | first1 = Claudio
 | last1 = Canuto
 | first2 = Anita
 | last2 = Tabacco
 | title = Mathematical Analysis II
 | edition = 2nd
 | publisher = [[Springer Science+Business Media|Springer]]
 | year = 2015
}}.

*{{Citation
 | first1 = Menahem
 | last1 = Friedman
 | first2 = Abraham
 | last2 = Kandel
 | title = Calculus Light
 | publisher = [[Springer Science+Business Media|Springer]]
 | year = 2011
 | isbn = 9783642178481
 | url = https://books.google.com/books?id=xGg52Cv9RsgC&q=%22Cauchy+product%22
}}.

*{{Citation
 | first1 = Sudhir R.
 | last1 = Ghorpade
 | first2 = Balmohan V.
 | last2 = Limaye
 | title = A Course in Calculus and Real Analysis
 | publisher = [[Springer Science+Business Media|Springer]]
 | year = 2006
}}.

*{{Citation
 | first = G. H.
 | last = Hardy
 | authorlink = G. H. Hardy
 | title = Divergent Series
 | year = 1949
 | publisher = [[Oxford University Press]]
 | pages = 227–229
}}.

*{{Citation
 | first = Omar
 | last = Hijab
 | title = Introduction to Calculus and Classical Analysis
 | edition = 3rd
 | publisher = [[Springer Science+Business Media|Springer]]
 | year = 2011
}}.

*{{Citation
 | first1 = Vicente
 | last1 = Montesinos
 | first2 = Peter
 | last2 = Zizler
 | first3 = Václav
 | last3 = Zizler
 | title = An Introduction to Modern Analysis
 | publisher = [[Springer Science+Business Media|Springer]]
 | year = 2015
}}.

*{{Citation
 | first1 = Michael
 | last1 = Oberguggenberger
 | first2 = Alexander
 | last2 = Ostermann
 | title = Analysis for Computer Scientists
 | publisher = [[Springer Science+Business Media|Springer]]
 | year = 2011
}}.

*{{Citation
 | first = Steen
 | last = Pedersen
 | title = From Calculus to Analysis
 | publisher = [[Springer Science+Business Media|Springer]]
 | year = 2015|doi=10.1007/978-3-319-13641-7
| isbn = 978-3-319-13640-0
 }}.

*{{Citation
 | first = S.
 | last = Ponnusamy
 | title = Foundations of Mathematical Analysis
 | publisher = [[Birkhäuser]]
 | year = 2012
 | isbn = 9780817682927
 | url = https://books.google.com/books?id=flwN3psxt_kC&q=%22Cauchy+product%22
}}.

*{{Citation
 | first = Charles C.
 | last = Pugh
 | title = Real Mathematical Analysis
 | edition = 2nd
 | publisher = [[Springer Science+Business Media|Springer]]
 | year = 2015
}}.

*{{Citation
 | first = Houshang H.
 | last = Sohrab
 | title = Basic Real Analysis
 | edition = 2nd
 | publisher = [[Birkhäuser]]
 | year = 2014
}}.

==External links==
*{{Cite web
 | last = Mathonline
 | title = Cauchy Product of Power Series
 | url = http://mathonline.wikidot.com/cauchy-product-of-power-series
}}.
*{{Citation
 | first = Eric W.
 | last = Weisstein
 | contribution = Cauchy Product
 | title = From MathWorld – A Wolfram Web Resource
 | url = http://mathworld.wolfram.com/CauchyProduct.html
}}.
[[Category:Augustin-Louis Cauchy]]
[[Category:Real analysis]]
[[Category:Complex analysis]]
[[Category:Sequences and series]]
[[Category:Articles containing proofs]]