# Convolution 卷积

$(2^0 +2^1 + 2^2 +...). (3^0 +3^1 + 3^2 +...)$
$= (2^{0}3^{0})+ (2^{0}3^{1}+ 2^{1} 3^{0}) + (2^{0} 3^{2} + 2^{1} 3^{1} + 2^{2} 3^{0} ) + ...$
$\displaystyle = \sum_{n=0}^{\infty} \sum_{k=0}^{n} 2^{k} 3^{n-k}$

Let the sequence $\left \{ a_{n} \right \}$ convolved with another sequence $\left \{ b_{n} \right \}$

$\boxed { \left \{ a_{n} \right \} = \left \{ a_{0}, a_{1}, a_{2}, ..., a_{n}, ... \right \} }$
Its correspondence $\leftrightarrow$ the generating function:
$\displaystyle \boxed { a(x) = \sum_{k=0}^{n}a_{k}x^{k} }$

$\boxed { \left \{ b_{n} \right \} = \left \{ b_{0}, b_{1}, b_{2}, ..., b_{n}, ... \right \} }$
Its correspondence $\leftrightarrow$ the generating function:
$\displaystyle \boxed { b(x) = \sum_{k=0}^{n}b_{k}x^{k} }$

The convolution is $\displaystyle \boxed { \left \{ a_{n}* b_{n} \right \} = \left \{ \sum_{k=0}^{n} a_{k}b_{n-k}\right \} }$
Its correspondence $\leftrightarrow$ the generating function:
$\displaystyle \boxed { a(x).b(x) = \sum_{n=0}^{\infty} \left (\sum_{k=0}^{n} a_{k}.b_{n-k}\right ) x^{n} }$

Note: We encounter “Convolution” very often in Quantum Group 量子群 & Hopf Algebra 霍氏代数.

Ref: “The Math Girls
http://www.amazon.com/gp/aw/d/0983951349/ref=pd_aw_cart_recs_1?pi=SL500_SY115