In mathematics, a transformation of a sequence's generating function provides a method of converting the generating function for one sequence into a generating function enumerating another. These transformations typically involve integral formulas applied to a sequence generating function (see integral transformations) or weighted sums over the higher-order derivatives of these functions (see derivative transformations).
Given a sequence,
\{fn\}
infty | |
n=0 |
F(z)
\widehat{F}(z)
F(z)=
infty | |
\sum | |
n=0 |
fnzn=f0+f1z+f2z2+ …
\widehat{F}(z)=
infty | |
\sum | |
n=0 |
fn | |
n! |
zn=
f0 | |
0! |
+
f1 | |
1! |
z+
f2 | |
2! |
z2+ … .
In this article, we use the convention that the ordinary (exponential) generating function for a sequence
\{fn\}
F(z)
\widehat{F}(z)
z
[zn]F(z):=fn
See main article: Series multisection.
Series multisection provides formulas for generating functions enumerating the sequence
\{fan+b\}
F(z)
a,b\inN
a\geq2
0\leqb<a
(a,b):=(2,0),(2,1)
F(z)
\sumnf2nz2n=
1 | |
2 |
\left(F(z)+F(-z)\right)
\sumnf2n+1z2n+1=
1 | |
2 |
\left(F(z)-F(-z)\right).
More generally, suppose that
a\geq3
\omegaa:=\exp\left(
2\pi\imath | |
a |
\right)
ath
\sumnfan+bzan+b=
1 | |
a |
x
a-1 | |
\sum | |
m=0 |
-mb | |
\omega | |
a |
m | |
F\left(\omega | |
a |
z\right).
For integers
m\geq1
\sumn
f | ||||||
|
zn=
1-zm | |
1-z |
F(zm)=\left(1+z+ … +zm-2+zm-1\right)F(zm).
The exponential Bell polynomials,
Bn,k(x1,\ldots,xn):=n! ⋅ [tnuk]\Phi(t,u)
\Phi(t,u)=\exp\left(u x \summxm
tm | |
m! |
\right)=1+\sumn
n | |
\left\{\sum | |
k=1 |
Bn,k(x1,x2,\ldots)uk\right\}
tn | |
n! |
.
The next formulas for powers, logarithms, and compositions of formal power series are expanded by these polynomials with variables in the coefficients of the original generating functions.[4] [5] The formula for the exponential of a generating function is given implicitly through the Bell polynomials by the EGF for these polynomials defined in the previous formula for some sequence of
\{xi\}
The power series for the reciprocal of a generating function,
F(z)
1 | |
F(z) |
=
1 | |
f0 |
-
f1 | ||||||
|
z+
| ||||||||||
|
z2-
| ||||||||||||||||
|
+ … .
If we let
bn:=[zn]1/F(z)
bn=-
1 | |
f0 |
\left(f1bn-1+f2bn-2+ … +fnb0\right),n\geq1.
Let
m\inC
f0=1
(m) | |
b | |
n |
:=[zn]F(z)m
F(z)m
F(z)m=1+mf1z+
2+2f | |
m\left((m-1)f | |
2\right) |
z2 | |
2 |
+
3 | |
\left(m(m-1)(m-2)f | |
1 |
+6m(m-1)f2+6mf3\right)
z3 | |
6 |
+ … ,
and the coefficients
(m) | |
b | |
n |
n ⋅
(m) | |
b | |
n |
=(m-n+1)f1
(m) | |
b | |
n-1 |
+(2m-n+2)f2
(m) | |
b | |
n-2 |
+ … +((n-1)m-1)fn-1
(m) | |
b | |
1 |
+nmfn,n\geq1.
Another formula for the coefficients,
(m) | |
b | |
n |
F(z)m=
m | |
f | |
0 |
+\sumn\left(\sum1(m)k
m-k | |
f | |
0 |
Bn,k(f1 ⋅ 1!,f2 ⋅ 2!,\ldots)\right)
zn | |
n! |
,
where
(r)n
If we let
f0=1
qn:=[zn]logF(z)
logF(z)=f1+\left(2f2-f
2\right) | |
1 |
z | |
2 |
+\left(3f3-3f1f2+f
3\right) | |
1 |
z2 | |
3 |
+ … ,
where the coefficients,
qn
n ⋅ qn=nfn-(n-1)f1qn-1-(n-2)f2qn-2- … -fn-1q1,
and a corresponding formula expanded by the Bell polynomials in the form of the power series coefficients of the following generating function:
logF(z)=\sumn\left(\sum1(-1)k-1(k-1)!Bn,k(f1 ⋅ 1!,f2 ⋅ 2!,\ldots)\right)
zn | |
n! |
.
See main article: Faà di Bruno's formula.
Let
\widehat{F}(z)
\{fn\}n
\widehat{G}(z)
\{gn\}n
\{hn\}n
\widehat{H}(z):=\widehat{F}(\widehat{G}(z))
hn=\sum1fk ⋅ Bn,k(g1,g2, … ,gn-k+1)+f0 ⋅ \deltan,0.
We have the following integral formulas for
a,b\inZ+
z
z
\sumnfnzn=
infty | |
\int | |
0 |
\widehat{F}(tz)e-tdt=z-1l{L}[\widehat{F}](z-1)
\sumn\Gamma(an+b) ⋅ fnzn=
infty | |
\int | |
0 |
tb-1e-tF(taz)dt.
\sumn
fn | |
n! |
zn=
1 | |
2\pi |
\pi | |
\int | |
-\pi |
F\left(ze-\imath\vartheta\right)
e\imath\vartheta | |
e |
d\vartheta.
Notice that the first and last of these integral formulas are used to convert between the EGF to the OGF of a sequence, and from the OGF to the EGF of a sequence whenever these integrals are convergent.
The first integral formula corresponds to the Laplace transform (or sometimes the formal Laplace–Borel transformation) of generating functions, denoted by
l{L}[F](z)
F(z)
The single factorial function,
(2n)!
(2n)!=(2n)!! x (2n-1)!!=
4n ⋅ n! | |
\sqrt{\pi |
where an integral for the double factorial function, or rational gamma function, is given by
1 | |
2 |
⋅ (2n-1)!!=
2n | |
\sqrt{4\pi |
for natural numbers
n\geq0
(2n-1)!!
q\inC
k\geq0
log(q)k | |
k! |
=
1 | |
(2k)! |
x
infty | |
\left[\int | |
0 |
| |||||||
\sqrt{2\pi |
Thus for any prescribed integer
j\geq0
\sumn\left\{\begin{matrix}2n\ j\end{matrix}\right\}
log(q)n | |
n! |
=
infty | |
\int | |
0 |
| |||||
\sqrt{2\pi |
⋅ j!}\left[\sumb\left(eb\sqrt{2 ⋅ t}-1\right)j\right]dt,
which is convergent provided suitable conditions on the parameter
0<|q|<1
For fixed non-zero
c,z\inC
|cz|<1
(cz)n
G(z):=1/(1-cz)
jth
z
Gj(z):=
(cz)j | |
1-cz |
x \left(
d | |
dz |
\right)(j)\left[G(z)\right],
for non-negative integers
j\geq0
jth
Gj(z)=
(cz)j ⋅ j! | |
(1-cz)j+2 |
,
for any
j\geq0
|cz|<1
\longmapsto
Gj(z)
\widehat{G}j(z)=
1 | |
2\pi |
+\pi | |
\int | |
-\pi |
Gj\left(ze-\imath\right)
e\imath | |
e |
dt=
(cz)jecz | |
(j+1) |
\left(j+1+z\right).
Fractional integrals and fractional derivatives (see the main article) form another generalized class of integration and differentiation operations that can be applied to the OGF of a sequence to form the corresponding OGF of a transformed sequence. For
\Re(\alpha)>0
\alpha
I\alphaF(z)=
1 | |
\Gamma(\alpha) |
z | |
\int | |
0 |
(z-t)\alpha-1F(t)dt,
which corresponds to the (formal) power series given by
I\alphaF(z)=\sumn
n! | |
\Gamma(n+\alpha+1) |
fnzn+\alpha.
For fixed
\alpha,\beta\inC
\Re(\alpha),\Re(\beta)>0
I\alphaI\beta=I\alpha+\beta
\alpha\inC
n
0<\Re(\alpha)<n
D\alphaF(z)=
d(n) | |
dz(n) |
In-\alphaF(z),
and
DkI\alpha=DnI\alpha+n-k
k=1,2,\ldots,n,
where we have the semigroup property that
D\alphaD\beta=D\alpha+\beta
\alpha,\beta,\alpha+\beta
For fixed
s\inZ+
\sumn
fn | |
(n+1)s |
zn=
(-1)s-1 | |
(s-1)! |
1 | |
\int | |
0 |
logs-1(t)F(tz)dt.
Notice that if we set
gn\equivfn+1
G(z)
z\equiv1
\widetilde{F}(s)
\{fn\}
For fixed non-zero
q,c,z\inC
|q|<1
|cz|<1
\{fn\}
z
\sumn
n2 | |
q |
fn ⋅ (cz)n=
1 | |
\sqrt{2\pi |
This result, which is proved in the reference, follows from a variant of the double factorial function transformation integral for the Stirling numbers of the second kind given as an example above. In particular, since
n2 | |
q |
=\exp(n2 ⋅ log(q))=1+n2log(q)+n4
log(q)2 | |
2! |
+n6
log(q)3 | |
3! |
+ … ,
we can use a variant of the positive-order derivative-based OGF transformations defined in the next sections involving the Stirling numbers of the second kind to obtain an integral formula for the generating function of the sequence,
\left\{S(2n,j)/n!\right\}
jth
F(z)
\sumn\left\{\begin{matrix}2n\ j\end{matrix}\right\}
z2n | |
(2n)! |
=
1 | |
2j! |
\left((ez-1)j+(e-z-1)j\right),
for each fixed
j\inN
We have an integral representation for the Hadamard product of two generating functions,
F(z)
G(z)
(F\odotG)(z):=\sumnfngnzn=
1 | |
2\pi |
2\pi | |
\int | |
0 |
F\left(\sqrt{z}ei\right)G\left(\sqrt{z}e-i\right)dt,
More information about Hadamard products as diagonal generating functions of multivariate sequences and/or generating functions and the classes of generating functions these diagonal OGFs belong to is found in Stanley's book.[13] The reference also provides nested coefficient extraction formulas of the form
\operatorname{diag}\left(F1 … Fk\right):=\sumnf1,n … fk,nzn=
0 | |
[x | |
k-1 |
…
0 | |
x | |
2 |
0] | |
x | |
1 |
F | ||||
|
\right)Fk-1\left(
xk-1 | |
xk-2 |
\right) …
F | ||||
|
\right)F1(x1),
which are particularly useful in the cases where the component sequence generating functions,
Fi(z)
z
In general, the Hadamard product of two rational generating functions is itself rational.[14] This is seen by noticing that the coefficients of a rational generating function form quasi-polynomial terms of the form
fn=p1(n)
n | |
\rho | |
1 |
+ … +p\ell(n)
n, | |
\rho | |
\ell |
where the reciprocal roots,
\rhoi\inC
pi(n)
n
1\leqi\leq\ell
F(z):=
1 | |
1+a1z+a2z2 |
and
G(z):=
1 | |
1+b1z+b2z2 |
is given by the rational generating function formula[15]
(F\odotG)(z)=
1-a2b2z2 | ||||||||||||||||||
|
.
Ordinary generating functions for generalized factorial functions formed as special cases of the generalized rising factorial product functions, or Pochhammer k-symbol, defined by
pn(\alpha,R):=R(R+\alpha) … (R+(n-1)\alpha)=\alphan ⋅ \left(
R | |
\alpha |
\right)n,
where
R
\alpha ≠ 0
(x)n
\operatorname{Conv}h(\alpha,R;z):=\operatorname{FP}h(\alpha,R;z)/\operatorname{FQ}h(\alpha,R;z)
hth
h\geq2
\operatorname{FP}h(\alpha,R;z)=
h-1 | |
\sum | |
n=0 |
n | |
\left[\sum | |
k=0 |
\binom{h}{k}\left(1-h-
R | |
\alpha |
\right)k\left(
R | |
\alpha |
\right)n-k\right](\alphaz)n,
and
\begin{align}\operatorname{FQ}h(\alpha,R;z)&=(-\alphaz)h ⋅ h! x
\left(R/\alpha-1\right) | |
L | |
h |
\left((\alphaz)-1\right)\ &=
h | |
\sum | |
k=0 |
\binom{h}{k}
k-1 | |
\left[\prod | |
j=0 |
(R+(j-1-j)\alpha)\right](-z)k,\end{align}
where
(\beta) | |
L | |
n |
(x)
hth
\operatorname{Conv}h(\alpha,R;z)
pn(\alpha,R)
0\leqn<2h
h\geq2
hth
\operatorname{Conv}h(\alpha,R;z)=
h-1 | ||
\sum | \binom{ | |
i=0 |
R | |
\alpha |
+i-1}{i} x
(-\alphaz)-1 | ||||||||||||||
|
Moreover, since the single factorial function is given by both
n!=pn(1,1)
n!=pn(-1,n)
2h
G(z)
2h
\begin{align}\widetilde{l{L}}h[G](z)&:=[x0]\operatorname{Conv}h\left(1,1;
z | |
x |
\right)G(x)\ & =
1 | |
2\pi |
2\pi | |
\int | |
0 |
\operatorname{Conv}h\left(1,1;\sqrt{z}eI\right)G\left(\sqrt{z}e-I\right)dt.\end{align}
Examples of sequences enumerated through these diagonal coefficient generating functions arising from the sequence factorial function multiplier provided by the rational convergent functions include
\begin{align}n!2&=[zn][x0]\operatorname{Conv}h\left(-1,n;
z | |
x |
\right)\operatorname{Conv}h\left(-1,n;x\right),h\geqn\ \binom{2n}{n}&=
0 | |
[x | |
1 |
0 | |
x | |
2 |
zn]\operatorname{Conv}h\left(-2,2n;
z | |
x2 |
\right)\operatorname{Conv}h\left(-2,2n-1;
x2 | |
x1 |
\right)I0(2\sqrt{x1})\ \binom{3n}{n}\binom{2n}{n}&=
0 | |
[x | |
1 |
0 | |
x | |
2 |
zn]\operatorname{Conv}h\left(-3,3n-1;
3z | |
x2 |
\right)\operatorname{Conv}h\left(-3,3n-2;
x2 | |
x1 |
\right)I0(2\sqrt{x1})\ !n&=n! x
n | |
\sum | |
i=0 |
(-1)i | |
i! |
=[znx0]\left(
e-x | |
(1-x) |
\operatorname{Conv}n\left(-1,n;
z | |
x |
\right)\right)\ \operatorname{af}(n)&=
n | |
\sum | |
k=1 |
(-1)n-kk!=
| ||||
[z |
1;z)-1}{1+z}\right)\ (t-1)n
P | ||||
|
\right)&=
n | |
\sum | |
k=0 |
\binom{n}{k}2tk\ &=
0 | |
[x | |
1 |
0] | |
x | |
2 |
[zn]\left(\operatorname{Conv}n\left(1,1;
z | |
x1 |
\right)\operatorname{Conv}n\left(1,1;
x1 | |
x2 |
\right)I0(2\sqrt{t ⋅ x2})I0(2\sqrt{x2})\right),n\geq1\ (2n-1)!!&=
n | |
\sum | |
k=1 |
(n-1)! | |
(k-1)! |
k ⋅ (2k-3)!!\ &=
0 | |
[x | |
1 |
0 | |
x | |
2 |
n-1 | |
x | |
3 |
]\left(\operatorname{Conv}n\left(1,1;
x3 | |
x2 |
\right)\operatorname{Conv}n\left(2,1;
x2 | |
x1 |
\right)
| |||||||||||
(1-x2) |
\right),\end{align}
I0(z)
!n
\operatorname{af}(n)
Pn(x)
For fixed
k\inZ+
F(z)
jth
1\leqj\leqk
\sumnnkfnzn=
k | |
\sum | |
j=0 |
\left\{\begin{matrix}k\ j\end{matrix}\right\}zjF(j)(z),
where
\scriptstyle{\left\{\begin{matrix}n\ k\end{matrix}\right\}}
fn\equiv1\foralln
\scriptstyle{\left\langle\begin{matrix}n\ m\end{matrix}\right\rangle}
\sumnnkzn=
k | |
\sum | |
j=0 |
\left\{\begin{matrix}k\ j\end{matrix}\right\}
zj ⋅ j! | |
(1-z)j+1 |
=
1 | |
(1-z)k+1 |
x \sum0\left\langle\begin{matrix}k\ m\end{matrix}\right\ranglezm+1.
We can also expand the negative-order zeta series transformations by a similar procedure to the above expansions given in terms of the
jth
F(z)\inCinfty
In particular, for integers
k,j\geq0
\left\{\begin{matrix}k+2\ j\end{matrix}\right\}\ast:=
1 | |
j! |
x
j | |
\sum | |
m=1 |
\binom{j}{m}
(-1)j-m | |
mk |
.
Then for
k\inZ+
F(z)\inCinfty
jth
F(z)
j\geq0
\sumn
fn | |
nk |
zn=\sumj\left\{\begin{matrix}k+2\ j\end{matrix}\right\}\astzjF(j)(z).
A table of the first few zeta series transformation coefficients,
\scriptstyle{\left\{\begin{matrix}k\ j\end{matrix}\right\}\ast
k | \left\{\begin{matrix}k\ j\end{matrix}\right\}\ast x (-1)j-1j! | ||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
2 | 1 | ||||||||||||||||||||||||||||||||||
3 | Hj | ||||||||||||||||||||||||||||||||||
4 |
\right) | ||||||||||||||||||||||||||||||||||
5 |
+2
\right) | ||||||||||||||||||||||||||||||||||
6 |
+
\right)2+8Hj
+
\right) |
The next series related to the polylogarithm functions (the dilogarithm and trilogarithm functions, respectively), the alternating zeta function and the Riemann zeta function are formulated from the previous negative-order series results found in the references. In particular, when
s:=2
k:=4
\begin{align}Li2(z)&=\sumj
(-1)j-1 | |
2 |
(2) | |
\left(H | |
j |
\right)
zj | |
(1-z)j+1 |
\ \zeta\ast(2)&=
\pi2 | |
12 |
=\sumj
| ||||||||||
4 ⋅ 2j |
.\end{align}
When
s:=3
k:=5
\begin{align}Li3(z)&=\sumj
(-1)j-1 | |
6 |
3+3H | |
\left(H | |
j |
(2) | |
H | |
j |
+2
(3) | |
H | |
j |
\right)
zj | |
(1-z)j+1 |
\ \zeta\ast(3)&=
3 | |
4 |
\zeta(3)=\sumj
| ||||||||||||||||||||||
12 ⋅ 2j |
\ &=
1 | |
6 |
log(2)3+\sumj
| |||||||||||||
2j+1 |
.\end{align}
It is known that the first-order harmonic numbers have a closed-form exponential generating function expanded in terms of the natural logarithm, the incomplete gamma function, and the exponential integral given by
\sumn
Hn | |
n! |
zn=ez\left(E1(z)+\gamma+logz\right)=ez\left(\Gamma(0,z)+\gamma+logz\right).
Additional series representations for the r-order harmonic number exponential generating functions for integers
r\geq2
\sumn
| |||||||
n! |
zn=\sumj
| |||||||
2 ⋅ (j+1)! |
zjez\left(j+1+z\right).
A further generalization of the negative-order series transformations defined above is related to more Hurwitz-zeta-like, or Lerch-transcendent-like, generating functions. Specifically, if we define the even more general parametrized Stirling numbers of the second kind by
\left\{\begin{matrix}k+2\ j\end{matrix}
\right\} | |
(\alpha,\beta)\ast |
:=
1 | |
j! |
x \sum0\binom{j}{m}
(-1)j-m | |
(\alpham+\beta)k |
for non-zero
\alpha,\beta\inC
- | \beta |
\alpha |
\notinZ+
k\geq1
\sumn
fn | |
(\alphan+\beta)k |
zn=\sumj\left\{\begin{matrix}k+2\ j\end{matrix}
\right\} | |
(\alpha,\beta)\ast |
zjF(j)(z).
Moreover, for any integers
u,u0\geq0
u | |
\sum | |
n=1 |
fn | |
(\alphan+\beta)k |
zn=
u+u0 | |
[w | |
j=1 |
\left\{\begin{matrix}k+2\ j\end{matrix}
\right\} | |
(\alpha,\beta)\ast |
(wz)jF(j)(wz) | |
1-w |
\right).
Series for special constants and zeta-related functions resulting from these generalized derivative-based series transformations typically involve the generalized r-order harmonic numbers defined by
(r) | |
H | |
n |
(\alpha,\beta):=\sum1(\alphak+\beta)-r
r\geq1
n\inZ+
\begin{align} | 4\sqrt{3 |
\pi}{9} |
&=\sumj
8 | |
9j+1 |
\left(2\binom{j+
1 | |
3 |
Several other series for the zeta-function-related cases of the Legendre chi function, the polygamma function, and the Riemann zeta function include
\begin{align}\chi1(z)&=\sumj\binom{j+
1 | |
2 |
Additionally, we can give another new explicit series representation of the inverse tangent function through its relation to the Fibonacci numbers[19] expanded as in the references by
\tan-1(x)=
\sqrt{5 | |
for
t\equiv2x/\left(1+\sqrt{1+
4 | |
5 |
x2}\right)
\varphi,\Phi:=
1 | |
2 |
\left(1\pm\sqrt{5}\right)
An inversion relation is a pair of equations of the form
gn=
n | |
\sum | |
k=0 |
An,k ⋅ fk \longleftrightarrow fn=
n | |
\sum | |
k=0 |
Bn,k ⋅ gk,
which is equivalent to the orthogonality relation
n | |
\sum | |
k=j |
An,k ⋅ Bk,j=\deltan,j.
Given two sequences,
\{fn\}
\{gn\}
an=\sumdbd \longleftrightarrow bn=\sumd\mu\left(
n | |
d |
\right)ad,
the generating functions for the sequences,
\{an\}
\{bn\}
\sumnanzn=\sumn
bnzn | |
1-zn |
.
Similarly, the Euler transform of generating functions for two sequences,
\{an\}
\{bn\}
1+\sumnbnzn=\prodi
1 | ||||||||||
|
,
is given in the form of
1+B(z)=\exp\left(\sumk
A(zk) | |
k |
\right),
where the corresponding inversion formulas between the two sequences is given in the reference.
The remainder of the results and examples given in this section sketch some of the more well-known generating function transformations provided by sequences related by inversion formulas (the binomial transform and the Stirling transform), and provides several tables of known inversion relations of various types cited in Riordan's Combinatorial Identities book. In many cases, we omit the corresponding functional equations implied by the inversion relationships between two sequences (this part of the article needs more work).
The first inversion relation provided below implicit to the binomial transform is perhaps the simplest of all inversion relations we will consider in this section. For any two sequences,
\{fn\}
\{gn\}
gn=
n | |
\sum | |
k=0 |
\binom{n}{k}(-1)kfk \longleftrightarrow fn=
n | |
\sum | |
k=0 |
\binom{n}{k}(-1)kgk,
we have functional equations between the OGFs and EGFs of these sequences provided by the binomial transform in the forms of
G(z)=
1 | F\left( | |
1-z |
-z | |
1-z |
\right)
and
\widehat{G}(z)=ez\widehat{F}(-z).
For any pair of sequences,
\{fn\}
\{gn\}
gn=
n | |
\sum | |
k=1 |
\left\{\begin{matrix}n\ k\end{matrix}\right\}fk \longleftrightarrow fn=
n | |
\sum | |
k=1 |
\left[\begin{matrix}n\ k\end{matrix}\right](-1)n-kgk,
these inversion relations between the two sequences translate into functional equations between the sequence EGFs given by the Stirling transform as
\widehat{G}(z)=\widehat{F}\left(ez-1\right)
and
\widehat{F}(z)=\widehat{G}\left(log(1+z)\right).
These tables appear in chapters 2 and 3 in Riordan's book providing an introduction to inverse relations with many examples, though which does not stress functional equations between the generating functions of sequences related by these inversion relations. The interested reader is encouraged to pick up a copy of the original book for more details.
Relation | Formula | Inverse Formula | Generating Functions (OGF) | Generating Functions (EGF) | Notes / References | |||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | an=
\binom{n}{k}bk | bn=
\binom{n}{k}(-1)n-kak | B(z)=
\right) | \widehat{B}(z)=ez\widehat{A}(-z) | See the Binomial transform | |||||||||||||||||||||||||||||||
2 | an=
\binom{p-k}{p-n}bk | bn=
\binom{p-k}{p-n}(-1)n-kak | \ast | \ast | ||||||||||||||||||||||||||||||||
3 | an=
\binom{n+p}{k+p}bk | bn=
\binom{n+p}{k+p}(-1)n-kak | B(z)=
\right) | \ast | ||||||||||||||||||||||||||||||||
4 | an=\sumk\geq\binom{k+p}{n+p}bk | bn=\sumk\geq\binom{k+p}{n+p}(-1)n-kak | \ast | \ast | ||||||||||||||||||||||||||||||||
5 | an=
\binom{n-1}{k-1}bk | bn=
\binom{n-1}{k-1}(-1)n-kak | \ast | \widehat{B}(z)=\widehat{A}\left(
\right) | ||||||||||||||||||||||||||||||||
6 | an=
\binom{n}{k}2k!bn-k | bn=
\binom{n}{k}2(-1)kk!an-k | \ast | \widehat{B}(z)=
\right) | ||||||||||||||||||||||||||||||||
7 |
=
\binom{n}{k}
|
=
\binom{n}{k}
| B(z)=
\right) | \ast | ||||||||||||||||||||||||||||||||
8 | sn=\sumk\binom{n+k}{m+2k}ak | \ast | S(z)=
\right) | \ast | See.[21] | |||||||||||||||||||||||||||||||
9 | an=
\binom{n}{k}ak(-c)n-kbk | \ast | A(z)=
\right) | \ast | Generalization of the binomial transform for a,b,c\inC \left | \frac\right | < \sigma_B. | |||||||||||||||||||||||||||||
10 | wn=
\binom{n}{i}knai, k ≠ 0 | \ast | \ast | \widehat{W}(A,k;z)=ekz\widehat{A}(kz) | The k | |||||||||||||||||||||||||||||||
11 | fn=
\binom{n}{i}kn-iai, k ≠ 0 | \ast | \ast | \widehat{F}(A,k;z)=ekz\widehat{A}(z) | The falling k | |||||||||||||||||||||||||||||||
12 | rn=
\binom{n}{i}kiai, k ≠ 0 | \ast | \ast | \widehat{R}(A,k;z)=ez\widehat{A}(kz) | The rising k |
The terms,
An,k
Bn,k
an=\sumkAn,k ⋅ bk \longleftrightarrow bn=\sumkBn,k ⋅ (-1)n-kak,
forming several special cases of Gould classes of inverse relations are given in the next table.
Class | An,k | Bn,k | |
---|---|---|---|
1 | \binom{p+qk-k}{n-k} | \binom{p+qn-k}{n-k}-q\binom{p+qn-k-1}{n-k-1} | |
2 | \binom{p+qk-k}{n-k}+q\binom{p+qk-k}{n-1-k} | \binom{p+qn-k}{n-k} | |
3 | \binom{p+qn-n}{k-n} | \binom{p+qk-n}{k-n}-q\binom{p+qk-n-1}{k-n-1} | |
4 | \binom{p+qn-n}{k-n}+q\binom{p+qn-n}{k-1-n} | \binom{p+qk-n}{k-n} |
For classes 1 and 2, the range on the sum satisfies
k\in[0,n]
k=n,n+1,\ldots
\binom{p+qn-k}{n-k}-q x \binom{p+qn-k-1}{n-k-1}=
p+qk-k | |
p+qn-k |
\binom{p+qn-k}{n-k}
\binom{p+qk-k}{n-k}+q x \binom{p+qk-k}{n-1-k}=
p+qn-n+1 | |
p+qk-n+1 |
\binom{p+qk-k}{n-k}.
The so-termed simpler cases of the Chebyshev classes of inverse relations in the subsection below are given in the next table.
Relation | Formula for an | Inverse Formula for bn | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | an=\sumk\binom{n}{k}bn-2k | bn=\sumk\left[\binom{n-k}{k}+\binom{n-k-1}{k-1}\right](-1)kan-2k | ||||||||||
2 | an=\sumk\left[\binom{n}{k}-\binom{n}{k-1}\right]bn-2k | bn=\sumk\binom{n-k}{k}(-1)kan-2k | ||||||||||
3 | an=\sumk\binom{n+2k}{k}bn+2k | bn=\sumk\left[\binom{n+k}{k}+\binom{n+k-1}{k-1}\right](-1)kan+2k | ||||||||||
4 | an=\sumk\left[\binom{n+2k}{k}-\binom{n+2k}{k-1}\right]bn+2k | bn=\sumk\binom{n+2k}{k}(-1)kan+2k | ||||||||||
5 | an=\sumk\binom{n-k}{k}bn-k | bn=\sumk\left[\binom{n+k-1}{k}-\binom{n+k-1}{k-1}\right](-1)kan-k | ||||||||||
6 | an=\sumk\left[\binom{n+1-k}{k}+\binom{n-k}{k-1}\right]bn-k | bn=\sumk\binom{n+k}{k}(-1)kan-k | ||||||||||
7 | an=
\binom{n}{k}bn+ck | bn=\sumk\binom{n+ck+k}{k}
an+ck |
The formulas in the table are simplified somewhat by the following identities:
\begin{align}\binom{n-k}{k}+\binom{n-k-1}{k-1}&=
n | |
n-k |
\binom{n-k}{k}\ \binom{n}{k}-\binom{n}{k-1}&=
n+1-k | |
n+1-2k |
\binom{n}{k}\ \binom{n+2k}{k}-\binom{n+2k}{k-1}&=
n+1 | |
n+1+k |
\binom{n+2k}{k}\ \binom{n+k-1}{k}-\binom{n+k-1}{k-1}&=
n-k | |
n+k |
\binom{n+k}{k}.\end{align}
Additionally the inversion relations given in the table also hold when
n\longmapston+p
The terms,
An,k
Bn,k
an=\sumkAn,k ⋅ bn+ck \longleftrightarrow bn=\sumkBn,k ⋅ (-1)kan+ck,
for non-zero integers
c
Class | An,k | Bn,k | |
---|---|---|---|
1 | \binom{n}{k} | \binom{n+ck+k}{k}-(c+1)\binom{n+ck+k-1}{k-1} | |
2 | \binom{n}{k}+(c+1)\binom{n}{k-1} | \binom{n+ck+k}{k} | |
3 | \binom{n+ck}{k} | \binom{n-1+k}{k}+c\binom{n-1+k}{k-1} | |
4 | \binom{n+ck}{k}-(c-1)\binom{n+ck}{k-1} | \binom{n+k}{k} |
Additionally, these inversion relations also hold when
n\longmapston+p
p=0,1,2,\ldots,
(-1)k
Bn,k
An,k
\begin{align}\binom{n+ck+k}{k}-(c+1)\binom{n+ck+k-1}{k-1}&=
n | |
n+ck+k |
\binom{n+ck+k}{k}\ \binom{n}{k}+(c+1)\binom{n}{k-1}&=
n+1+ck | |
n+1-k |
\binom{n}{k}\ \binom{n-1+k}{k}+c\binom{n-1+k}{k-1}&=
n+ck | |
n |
\binom{n-1+k}{k}\ \binom{n+ck}{k}-(c-1)\binom{n+ck}{k-1}&=
n+1 | |
n+1+ck-k |
\binom{n+ck}{k}.\end{align}
Relation | Formula for an | Inverse Formula for bn | |||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | an=\sumk\binom{n+p+k}{n-k}bk | bn=\sumk\left[\binom{2n+p}{n-k}-\binom{2n+p}{n-k-1}\right](-1)n-kak | |||||||||||||
2 | an=\sumk\binom{2n+p}{n-k}bk | bn=\sumk\left[\binom{n+p+k}{n-k}-\binom{n+p+k-1}{n-k-1}\right](-1)n-kak | |||||||||||||
3 | an=\sumk\geq\binom{n+p+k}{k-n}bk | bn=\sumk\left[\binom{2k+p}{k-n}-\binom{2k+p}{k-n-1}\right](-1)n-kak | |||||||||||||
4 | an=\sumk\geq\binom{2k+p}{k-n}bk | bn=\sumk\left[\binom{n+p+k}{k-n}-\binom{n+p+k-1}{k-n-1}\right](-1)n-kak | |||||||||||||
5 | an=\sumk\binom{2n+p}{k}bn-2k | bn=\sumk\left[\binom{2n+p-3k}{k}+3\binom{2n+p-3k-1}{k-1}\right](-1)kan-2k | |||||||||||||
6 | an=\sumk\left[\binom{2n+p}{k}-3\binom{2n+p}{k-1}\right]bn-2k | bn=\sumk\binom{2n+p-3k}{k}(-1)kan-2k | |||||||||||||
7 | an=
\binom{3n}{k}bn-2k | bn=
\left[\binom{3n-5k}{k}+5\binom{3n-5k-1}{k-1}\right](-1)kan-2k | |||||||||||||
8 | an=
\binom{2n}{k}bn-3k | bn=
\left[\binom{2n-5k}{k}+5\binom{2n-5k-1}{k-1}\right](-1)kan-3k |
The Legendre–Chebyshev classes of inverse relations correspond to inversion relations of the form
an=\sumkAn,k ⋅ bk \longleftrightarrow bn=\sumkBn,k ⋅ (-1)n-kak,
where the terms,
An,k
Bn,k
c\inZ
an=\sumkAn,k ⋅ bn-ck \longleftrightarrow bn=\sumkBn,k ⋅ (-1)kan-ck,
if
c
n\longmapstocn+p
acn+p\longmapstoAn
bcn+p\longmapstoBn
k\longmapston-k
An=\sumkAcn+p,kBn-k \longleftrightarrow Bn=\sumkBcn+p,k(-1)kAn-k.
Similarly, if the positive integer
c:=de
An=\sumkAdn+p,kBn-ek \longleftrightarrow Bn=\sumkBdn+p,k(-1)kAn-ek.
The next table summarizes several generalized classes of Legendre–Chebyshev inverse relations for some non-zero integer
c
Class | An,k | Bn,k | |
---|---|---|---|
1 | \binom{cn+p}{n-k} | \binom{n+p-1+ck-k}{n-k}+c\binom{n+p-1+ck-k}{n-k-1} | |
2 | \binom{cn+p}{k-n} | \binom{ck+k+p-n-1}{k-n}-c\binom{ck+k+p-n-1}{k-n-1} | |
3 | \binom{ck+p}{n-p} | \binom{cn+n+p-k-1}{n-k}-c\binom{cn+n+p-k-1}{n-k-1} | |
4 | \binom{ck+p}{k-n} | \binom{cn-n+p+k-1}{k-n}+c\binom{cn-n+p+k-1}{k-n-1} | |
5 | \binom{cn+p}{n-k}-(c-1)\binom{cn+p}{n-k-1} | \binom{n+p+ck-k}{n-k} | |
6 | \binom{cn+p}{k-n}+(c+1)\binom{cn+p}{k-n-1} | \binom{ck+k+p-n}{k-n} | |
7 | \binom{ck+p}{n-k}+(c+1)\binom{ck+p}{n-k-1} | \binom{cn+n+p-k}{n-k} | |
8 | \binom{ck+p}{k-n}-(c-1)\binom{ck+p}{k-n-1} | \binom{cn-n+p+k}{k-n} |
Abel inverse relations correspond to Abel inverse pairs of the form
an=
n | |
\sum | |
k=0 |
\binom{n}{k}Ankbk \longleftrightarrow bn=
n | |
\sum | |
k=0 |
\binom{n}{k}Bnk(-1)n-kak,
where the terms,
Ank
Bnk
x
\binom{n}{k}\longmapsto\binom{n+p}{k+p}
p
Number | Ank | Bnk | Generating Function Identity | |
---|---|---|---|---|
1 | x(x+n-k)n-k-1 | x(x-n+k)n-k-1 | \ast | |
2 | (x+n-k)n-k | (x2-n+k)(x-n+k)n-k-2 | \ast | |
3 | (x+k)n-k | (x+k)(x+n)n-k-1 | \ast | |
3a | (x+n)(x+k)n-k-1 | (x+n)n-k | \ast | |
4 | (x+2n)(x+n+k)n-k-1 | (x+2n)(x+n+k)n-k-1 | \ast | |
4a | (x+2k)(x+n+k)n-k-1 | (x+2k)(x+n+k)n-k-1 | \ast | |
5 | (n+k)n-k | \left[n+k(4n-1)\right](n+k)n-k-2 | \ast |
If we let the convolved Fibonacci numbers,
(\pmp) | |
f | |
k |
\begin{align}
(p) | |
f | |
n |
&=\sumj\binom{p+n-j-1}{n-j}\binom{n-j}{j}\
(-p) | |
f | |
n |
&=\sumj\binom{p}{n+j}\binom{n-j}{j}(-1)n-j,\end{align}
we have the next table of inverse relations which are obtained from properties of ordinary sequence generating functions proved as in section 3.3 of Riordan's book.
Relation | Formula for an | Inverse Formula for bn | ||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | an=
\binom{p+k}{k}bn-k | bn=
\binom{p+1}{k}(-1)kan-k | ||||||||||||||||||||||||
2 | an=\sumk\binom{p+k}{k}bn-qk | bn=\sumk\binom{p+1}{k}(-1)kan-qk | ||||||||||||||||||||||||
3 | an=
bn-k | bn=
an-k | ||||||||||||||||||||||||
4 | an=
\binom{2k}{k}bn-k |
\binom{2k}{k}
| ||||||||||||||||||||||||
5 | an=
\binom{2k}{k}
| bn=an-
\binom{2k}{k}
| ||||||||||||||||||||||||
6 | an=
\binom{2p+2k}{p+k}\binom{p+k}{k}\binom{2p}{p}-1bn-k | bn=
\binom{2p+1}{2k}\binom{p+k}{k}\binom{p+k}{2k}-1(-1)kan-k | ||||||||||||||||||||||||
7 | an=\sumk\binom{4k}{2k}bn-2k | bn=\sumk\binom{4k}{2k}
| ||||||||||||||||||||||||
8 | an=\sumk\binom{4k+2}{2k+1}bn-2k | bn=
-\sumk\binom{4k-2}{2k-1}
| ||||||||||||||||||||||||
9 | an=\binom{4k}{2k}
| bn=\sumk\binom{4k}{2k}
|
Note that relations 3, 4, 5, and 6 in the table may be transformed according to the substitutions
an-k\longmapstoan-qk
bn-k\longmapstobn-qk
q\geq1
Let
Bn
En
\{d2n\}
\{e2n\}
\{f2n\}
\begin{align}\sumn
d2nz2n | |
(2n)! |
&=
2z | |
ez-e-z |
\ \sumn
e2nz2n | |
(2n)! |
&=
z2 | |
ez+e-z-2 |
\ \sumn
f2nz2n | |
(2n)! |
&=
z3 | |
3(ez-e-z-2z) |
.\end{align}
The next table summarizes several notable cases of inversion relations obtained from exponential generating functions in section 3.4 of Riordan's book.[25]
Relation | Formula for an | Inverse Formula for bn | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | an=
\binom{n}{k}
| bn=
Bkan-k | |||||||||||||||
2 | an=\sumk\binom{n+k}{k}
| bn=\sumk\binom{n+k}{k}Bkan+k | |||||||||||||||
3 | an=\sumk\binom{n}{2k}bn-2k | bn=\sumk\binom{n}{2k}E2kan-2k | |||||||||||||||
4 | an=\sumk\binom{n+2k}{2k}bn+2k | bn=\sumk\binom{n+2k}{2k}E2kan+2k | |||||||||||||||
5 | an=\sumk\binom{n}{2k}
| bn=\sumk\binom{n}{2k}d2kan-2k | |||||||||||||||
6 | an=\sumk\binom{n+1}{2k+1}bn-2k | (n+1) ⋅ bn=\sumk\binom{n+1}{2k}d2kan-2k | |||||||||||||||
7 | an=\sumk\binom{n}{2k}\binom{2k+2}{2}-1bn-2k | bn=\sumk\binom{n}{2k}e2kan-2k | |||||||||||||||
8 | an=\sumk\binom{n+2}{2k+2}bn-2k | \binom{n+2}{2} ⋅ bn=\sumk\binom{n+2}{2k}e2kan-2k | |||||||||||||||
9 | an=\sumk\binom{n}{2k}\binom{2k+3}{3}-1bn-2k | bn=\sumk\binom{n}{2k}f2kan-2k | |||||||||||||||
10 | an=\sumk\binom{n+3}{2k+3}bn-2k | \binom{n+3}{3} ⋅ bn=\sumk\binom{n+3}{2k}f2kan-2k |
The inverse relations used in formulating the binomial transform cited in the previous subsection are generalized to corresponding two-index inverse relations for sequences of two indices, and to multinomial inversion formulas for sequences of
j\geq3
amn=
m | |
\sum | |
j=0 |
n | |
\sum | |
k=0 |
\binom{m}{j}\binom{n}{k}(-1)j+kbjk \longleftrightarrow bmn=
m | |
\sum | |
j=0 |
n | |
\sum | |
k=0 |
\binom{m}{j}\binom{n}{k}(-1)j+kajk,
and the more general form of a multinomial pair of inversion formulas given by
a | |
n1n2 … nj |
=
\sum | |
k1,\ldots,kj |
\binom{n1}{k1} … \binom{nj}{kj}
k1+ … +kj | |
(-1) |
b | |
k1k2 … kj |
\longleftrightarrow
b | |
n1n2 … nj |
=
\sum | |
k1,\ldots,kj |
\binom{n1}{k1} … \binom{nj}{kj}
k1+ … +kj | |
(-1) |
a | |
k1k2 … kj |
.