"Binomial theorem"-like identities

There are several identities which resemble the binomial theorem. For starters, we have the binomial theorem itself: $$(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}$$ But I just learned from the book "Concrete Mathematics", Exercise 5.37, that the "falling factorial" $x^{\underline{k}} = x(x-1)\ldots(x-k+1)$ satisfies a similar identity: $$(x+y)^\underline{n} = \sum_{k=0}^n \binom{n}{k} x^\underline{k} y^\underline{n-k}$$ The "rising factorial" $x^{\overline{k}} = x(x+1)\ldots(x+k-1)$ also satisfies such an identity.

Sometimes, the identity involves a product instead of a sum on the left side. If $f$ and $g$ are $n$-times differentiable functions on $\mathbb{R}$, then this generalization of the product rule holds: $$(fg)^{(n)} = \sum_{k=0}^n \binom{n}{k} f^{(k)} g^{(n-k)}$$ where $f^{(k)}$ denotes the $k$-th derivative of $f$, and the 0th derivative of a function is the function itself.

Question: Are there any more of these binomial-theorem like identities in other contexts? Are these identities part of some more general result, where we can axiomatize some conditions under which some "iterative" process satisfies a binomial-like theorem?

Solution 1:

Some keywords you'll want to look into: binomial type, Appell sequence, Sheffer sequence, umbral calculus. The references in the corresponding Wikipedia articles are good too.

Edit: In some sense, all of these identities can be deduced from the last one. Setting $$f(t) = e^{xt}, g(t) = e^{yt}$$

produces the binomial theorem, and setting $$f(t) = (1 + t)^x = \exp (x \log (1 + t)), g(t) = (1 + t)^y = \exp ( y \log (1 + t))$$

produces the second identity. From this perspective one can think of the study of generalized binomial theorems as being all about generating functions of the form $\exp (x h(t))$ where $h(0) = 0$; setting $$f(t) = \exp (x h(t)), g(t) = \exp (y h(t))$$

produces a fairly general binomial theorem, especially if one writes $h(t) = \sum_{n \ge 1} h_n t^n$ as a formal power series in formal variables.

Solution 2:

I up-voted Qiaochu Yuan's answer. To be more explicit: Say you have a sequence of scalars $c_1,c_2,c_3,\ldots$ (starting with $1$, not with $0$). Then you can find a sequence of polynomials $p_0(x),p_1(x),p_2(x),\ldots$ (starting with $0$, not with $1$) such that for $n=0,1,2,3,\ldots$ $$ p_n(x+y) = \sum_{k=0}^n \binom n k p_k(x) p_{n-k}(y) $$ and $p_n\,'(0)=c_n$ for $n\ge 1$. This is a "polynomial sequence of binomial type".

And what I just wrote amounts to a definition by recursion, so if you want to write out, for example $p_6(x)$ with all its coefficients as polynomials in $c_1,\ldots, c_6$, just apply what I wrote above. The polynomials in $c_1,c_2,c_3,\ldots$ that are the coefficients are the incomplete Bell polynomials, named after Eric Temple Bell.

Solution 3:

Maybe the binomial transform might also be of interest to you. One example from the page:

The binomial transform is the shift operator for the Bell numbers. That is, $$ B_{n+1}=\sum_{k=0}^n {n\choose k} B_k $$ where the $B_n$ are the Bell numbers.