14
$\begingroup$

This operation is similar to discrete convolution and cross-correlation, but has binomial coefficients:

$$f(n)\star g(n)=\sum_{k=0}^n \binom{n}{k}f(n-k)g(k) $$

Particularly,

$$a^n\star b^n=(a+b)^n$$

following binomial theorem.

I just wonder if there is a name for such operation and where I can read about its properties.

$\endgroup$
2
  • 3
    $\begingroup$ To be precise, one should write $(f\star g)(b)$ rather than $f(n)\star g(n)$. For example, what if $n=5$ and $f(5)=3$ and $g(5)7$. Would $f(n)\star g(n)$ then be $3\star 7$? Obviously that's nonsense. $\endgroup$
    – Michael Hardy
    Jan 30, 2012 at 19:28
  • 1
    $\begingroup$ Composition is distributive against any binary functions. That is $(f\circ w) \star (g \circ w) = (f \star g) \circ w$ for any f,g,w and binary operation $\star$ $\endgroup$
    – Anixx
    Jan 30, 2012 at 19:48

4 Answers 4

Reset to default
19
$\begingroup$

It's called a binomial convolution in Graham, Knuth, and Patashnik's Concrete Mathematics. I don't have that text in front of me (but I bet someone here can give you a page number), but here's a reference on the Fermat's Last Theorem blog.

It would also be worth checking out Section 2.3 of Wilf's Generatingfunctionology. This is on exponential generating functions. The property of interest is that if $F(x)$ and $G(x)$ are the exponential generating functions of $f(n)$ and $g(n)$, respectively, then $F(x)G(x)$ is the exponential generating function of $f(n) \star g(n)$.

(FYI: You can download the second edition of Generatingfunctionology from Wilf's web site.)

$\endgroup$
5
  • 5
    $\begingroup$ Its page 366 in the second edition. $\endgroup$
    – J. M. ain't a mathematician
    Nov 3, 2010 at 2:33
  • $\begingroup$ @J.M.: Thanks. I knew someone would find it quickly. :) $\endgroup$
    – Mike Spivey
    Nov 3, 2010 at 2:37
  • $\begingroup$ There is no page 366 in the second edition. $\endgroup$
    – Igor Rivin
    Dec 28, 2013 at 17:55
  • $\begingroup$ @IgorRivin: The "binomial convolution" reference is on page 365 of the second edition of Concrete Mathematics. Perhaps you are talking about Generatingfunctionology? $\endgroup$
    – Mike Spivey
    Dec 28, 2013 at 18:48
  • $\begingroup$ @MikeSpivey Yes, I was, that clears it up! $\endgroup$
    – Igor Rivin
    Dec 28, 2013 at 19:16
5
$\begingroup$

Remark that one can employ the powerful umbral calculus to compute closed forms for many such binomial convolutions of special functions, e.g. from p. 161 of Roman: Umbral Calculus:
alt text

$\endgroup$
3
  • $\begingroup$ Note for casual readers: page 17 of the book defines the concept of an "Appell sequence". $\endgroup$
    – J. M. ain't a mathematician
    Nov 3, 2010 at 2:56
  • $\begingroup$ I wonder where can I find a closed form expression of binomial Bell's numbers of higher order? I.e. I need $\sum_{k=0}^{x-1} B_n^x \star B_n^k$ $\endgroup$
    – Anixx
    Nov 3, 2010 at 3:02
  • $\begingroup$ @MathFacts: You might try posting that as a separate question. $\endgroup$
    – Mike Spivey
    Nov 3, 2010 at 20:48
3
$\begingroup$

I came across this same binomial convolution in the following curious setting: consider the shift operator $S(a_n) = (a_{n+1})$ which maps $(a_0, a_1, a_2, \ldots) \mapsto (a_1, a_2, a_3, \ldots)$.

It is easy to check that $S$ is a derivation of this convolution, that is: $$ S ((a_n) \star (b_n)) = S (a_n) \star (b_n) + (a_n) \star S(b_n) $$ just by using Pascal's rule $ {n+1 \choose k} = {n \choose k} + {n+1 \choose k-1} $.

This can be used to give a proof of the form of the general solution to a linear recurrence (homogeneous, with constant coefficients): Just repeat the same linear algebra one does to give a proof of the form of the general solution to a linear homogeneous differential equation with constant coefficients, exchanging the derivative operator D, functions and the exponential functions by the shift operator S, sequences and the geometrical sequences.

I have not seen this used elsewhere and I do not know if it has other applications other then the one sketched above.

$\endgroup$
4
  • 2
    $\begingroup$ It seems this operator works on binomial convolution like a derivative on a product. $\endgroup$
    – Anixx
    Oct 2, 2013 at 8:07
  • $\begingroup$ Exactly @Anixx, the above would be the analogous to Leibnitz derivation rule for the shift $S$ under this convolution product, this surprised me! One can use this to solve linear recurrences very much like linear ODEs: by characteristic roots or by the annihilator method, which was what I was I looking for when I found this. $\endgroup$
    – Lucas Seco
    Oct 2, 2013 at 14:45
  • 1
    $\begingroup$ I wrote a paper a few years ago that uses finite differences to evaluate binomial sums. Since the finite difference is $S(a_n) - a_n$, some of the ideas in there are related to your observation here. In case you're interested, the paper is here. $\endgroup$
    – Mike Spivey
    Oct 2, 2013 at 17:32
  • $\begingroup$ Thanks for the article @MikeSpivey, I will take a look! And Anixx, the analogy with ODE gets better using "Taylor series" $\sum_{i=0}^\infty \frac{a_n}{n!} x^n$. First, the coeficients of the derivative are given by the shift: $$ \left( \sum_{i=0}^\infty \frac{a_n}{n!} x^n \right)' = \sum_{i=0}^\infty \frac{a_{n+1}}{n!} x^n $$ Second, the coefficients of the product is the binomial convolution: $$ \left( \sum_{i=0}^\infty \frac{a_n}{n!} x^n \right) \left( \sum_{i=0}^\infty \frac{b_n}{n!} x^n \right) = \sum_{i=0}^\infty \frac{((a_n) \star (b_n))_n}{n!} x^n $$ $\endgroup$
    – Lucas Seco
    Oct 2, 2013 at 19:12
2
$\begingroup$

It corresponds to multiplying exponential generating functions (check generatingfunctionology).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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