The important binomial theorem states that
(1)
|
Consider sums of powers of binomial coefficients
(2)
| |||
(3)
|
where is a generalized hypergeometric function. When they exist, the recurrence equations that give solutions to these equations can be generated quickly using Zeilberger's algorithm.
For , the closed-form solution is given by
(4)
|
i.e., the powers of two. obeys the recurrence relation
(5)
|
For , the closed-form solution is given by
(6)
|
i.e., the central binomial coefficients. obeys the recurrence relation
(7)
|
Franel (1894, 1895) was the first to obtain recurrences for ,
(8)
|
(Riordan 1980, p. 193; Barrucand 1975; Cusick 1989; Jin and Dickinson 2000), so are sometimes called Franel numbers. The sequence for cannot be expressed as a fixed number of hypergeometric terms (Petkovšek et al. 1996, p. 160), and therefore has no closed-form hypergeometric expression.
Franel (1894, 1895) was also the first to obtain the recurrence for ,
(9)
|
(Riordan 1980, p. 193; Jin and Dickinson 2000).
Perlstadt (1987) found recurrences of length 4 for and 6.
(10)
|
Schmidt and Yuan (1995) showed that the given recurrences for , 4, 5, and 6 are minimal, are the minimal lengths for are at least 3. The following table summarizes the first few values of for small .
OEIS | ||
1 | A000079 | 1, 2, 4, 8, 16, 32, 64, ... |
2 | A000984 | 1, 2, 6, 20, 70, 252, 924, ... |
3 | A000172 | 1, 2, 10, 56, 346, 2252, ... |
4 | A005260 | 1, 2, 18, 164, 1810, 21252, ... |
5 | A005261 | 1, 2, 34, 488, 9826, 206252, ... |
The corresponding alternating series is
(11)
| |||
(12)
|
The first few values are
(13)
| |||
(14)
| |||
(15)
| |||
(16)
| |||
(17)
| |||
(18)
|
where is the gamma function, is a Legendre polynomial, and the odd terms of are given by de Bruijn's with alternating signs.
Zeilberger's algorithm can be used to find recurrence equations for the s,
(19)
|
Sums of the form (Boros and Moll 2004, pp. 14-15) are given by
(20)
| |||
(21)
| |||
(22)
| |||
(23)
| |||
(24)
| |||
(25)
|
where the triangle of the coefficients of the right-hand polynomials (ignoring the even/odd terms and ) are given by 1; 1, 3; 1, 5, ; 1, 10, 15, ; ... (OEIS A102573).
de Bruijn (1981) has considered the sum
(26)
|
for . This sum has closed form for , 2, and 3,
(27)
|
(28)
|
the central binomial coefficient, giving 1, 2, 6, 20, 70, 252, 924, ... (OEIS A000984), and
(29)
|
giving 1, 6, 90, 1680, 36450, 756756, ... (OEIS A006480; Aizenberg and Yuzhakov 1984). However, there is no similar formula for (de Bruijn 1981). The first few terms of are 1, 14, 786, 61340, 5562130, ... (OEIS A050983), and for are 1, 30, 5730, 1696800, 613591650, ... (OEIS A050984).
An interesting generalization of is given by
(30)
|
for positive integer and all (Ruiz 1996). This identity is consequence of the fact the difference operator applied times to a polynomial of degree will result in times the leading coefficient of the polynomial. The above equation is just a special instance of this, with the general case obtained by replacing by any polynomial of degree with leading coefficient 1.
The infinite sum of inverse binomial coefficients has the analytic form
(31)
| |||
(32)
|
where is a hypergeometric function. In fact, in general,
(33)
|
and
(34)
|
Another interesting sum is
(35)
| |||
(36)
|
where is an incomplete gamma function and is the floor function. The first few terms for , 2, ... are 2, 5, 16, 65, 326, ... (OEIS A000522).
A fascinating series of identities involving inverse central binomial coefficients times small powers are given by
(37)
| |||
(38)
| |||
(39)
| |||
(40)
| |||
(41)
| |||
(42)
| |||
(43)
|
(Comtet 1974, p. 89; Le Lionnais 1983, pp. 29, 30, 41, 36; Borwein et al. 1987, pp. 27-28), which follow from the beautiful formula
(44)
|
for , where is a generalized hypergeometric function and is the polygamma function and is the Riemann zeta function (Plouffe 1998).
A nice sum due to B. Cloitre (pers. comm., Oct. 6, 2004) is given by
(45)
|
Additional classes of binomial sums that can be done in closed form include
(46)
| |||
(47)
| |||
(48)
| |||
(49)
|
(Gosper 1974, Borwein and Borwein 1987; Borwein et al. 2004, pp. 20-25). Some of these follow from the general results
(50)
| |||
(51)
|
where is a Stirling number of the second kind and , are definite rational numbers (Borwein et al. 2004, pp. 23-25). The first few sums of the first form are
(52)
| |||
(53)
| |||
(54)
|
giving values of as 2/3, 4/3, 10/3, 32/3, ..., and of as 2/9, 10/27, 74/81, ....
Similarly, the first few sums of the second form are given by
(55)
|
The first few of these are
(56)
| |||
(57)
| |||
(58)
|
giving values for as 2/25, 81/625, 561/3125, ..., for as , , 42/15625, ..., and for as 11/250, 79/3125, 673/31250, ....
Borwein (et al. 2004, pp. 27-28) conjecture closed-form solutions to sums of the form
(59)
|
in terms of multidimensional polylogarithms.
Sums of the form
(60)
|
can also be simplified (Plouffe 1998) to give the special cases
(61)
| |||
(62)
| |||
(63)
|
Other general identities include
(64)
|
(Prudnikov et al. 1986), which gives the binomial theorem as a special case with , and
(65)
| |||
(66)
|
where is a hypergeometric function (Abramowitz and Stegun 1972, p. 555; Graham et al. 1994, p. 203).
For nonnegative integers and with ,
(67)
|
Taking gives
(68)
|
Other identities are
(69)
|
(Gosper 1972) and
(70)
|
where
(71)
|
The latter is the umbral analog of the multinomial theorem for
(72)
|
using the lower-factorial polynomial , giving
(73)
|
The identity holds true not only for and , but also for any quadratic polynomial of the form .
Sinyor et al. (2001) give the strange sum
(74)
| |
(75)
| |
(76)
|