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.

| cite | improve this question | |
$\endgroup$
  • 1
    $\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 '12 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 '12 at 19:48
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.)

| cite | improve this answer | |
$\endgroup$
  • 5
    $\begingroup$ Its page 366 in the second edition. $\endgroup$ – J. M. isn't a mathematician Nov 3 '10 at 2:33
  • $\begingroup$ @J.M.: Thanks. I knew someone would find it quickly. :) $\endgroup$ – Mike Spivey Nov 3 '10 at 2:37
  • $\begingroup$ There is no page 366 in the second edition. $\endgroup$ – Igor Rivin Dec 28 '13 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 '13 at 18:48
  • $\begingroup$ @MikeSpivey Yes, I was, that clears it up! $\endgroup$ – Igor Rivin Dec 28 '13 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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Note for casual readers: page 17 of the book defines the concept of an "Appell sequence". $\endgroup$ – J. M. isn't a mathematician Nov 3 '10 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 '10 at 3:02
  • $\begingroup$ @MathFacts: You might try posting that as a separate question. $\endgroup$ – Mike Spivey Nov 3 '10 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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ It seems this operator works on binomial convolution like a derivative on a product. $\endgroup$ – Anixx Oct 2 '13 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 '13 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 '13 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 '13 at 19:12
2
$\begingroup$

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

| cite | improve this answer | |
$\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.