Combinatorial numbers and Egorychev method (MathJax)

The collection including a list of all identities proved is available here (part 1 and 2, formal power series and residue operators):

• Egorychev method and the evaluation of combinatorial sums part 1 and 2 (PDF)
and here:
• Egorychev method and the evaluation of combinatorial sums part 1 and 2 (PS.GZ)

• Egorychev method and the evaluation of combinatorial sums part 3 (PDF)
and here:
• Egorychev method and the evaluation of combinatorial sums part 3 (PS.GZ)

We now have a new section as of March 2023 "computer search" which includes hypergeometric identities that can prove challenging even for computer algebra systems, such as

$${n\choose m} n^m = (-1)^n \sum_{k=0}^n {n\choose k} (-1)^k {n-m+k\choose k} {kn+m\choose m}$$

As of January 2024 "computer search" continues with rare identities such as (the 42 identity)

$${4p-2\choose p} = (-1)^m \sum_{k=0}^n {n+p\choose k+p} (-1)^k {k+p-1\choose k+p-m} {2k+1-p\choose p}$$

Here are the slides from Hosam Mahmoud's talk on Egorychev method at Catholic University on November 9, 2022: History and examples of Egorychev method.

The 2023 paper "Egorychev method: a hidden treasure" by Riedel and Mahmoud is at the following Springer link.

Part 1 and 2

Egorychev method in formal power series

1. MSE 2384932

$$\sum_{l=0}^m (-4)^l {m\choose l} {2l\choose l}^{-1} \sum_{k=0}^n \frac{(-4)^k}{2k+1} {n\choose k} {2k\choose k}^{-1} {k+l\choose l} = \frac{1}{2n+1-2m}$$

2. MSE 2472978

$$\sum_{l=0}^n {n\choose l}^2 (x+y)^{2l} (x-y)^{2n-2l} = \sum_{l=0}^n {2l\choose l} {2n-2l\choose n-l} x^{2l} y^{2n-2l}$$

3. MSE 2719320

$$\sum_{k=0}^n {n\choose k} \frac{1}{k+c} = {n+c\choose c}^{-1} \frac{(-1)^c}{c} \left(1-2^{n+1} \sum_{q=0}^{c-1} {n+q\choose q} (-1)^q\right)$$

4. MSE 2830860

$$\sum_{j=0}^{n-k} (-1)^j {2k+2j\choose j} {n+k+j+1\choose n-k-j} = [[(n-k) \; \text{is even}]] = \frac{1+(-1)^{n-k}}{2}$$

5. MSE 2904333

$$\sum_{k=0}^{b-1} {a+k-1\choose a-1} p^a (1-p)^k = \sum_{k=a}^{a+b-1} p^k (1-p)^{a+b-k-1}$$

6. MSE 2950043

$$(-1)^{n+k} {n\brack k} = \sum_{j=0}^{n-k} (-1)^j {n-1+j\choose n-k+j} {2n-k\choose n-k-j} {n-k+j\brace j}$$

7. MSE 3049572

$${m+n\choose s+1} - {n\choose s+1} = \sum_{q=0}^s \frac{m}{q+1} {m+1+2q\choose q} {n-2-2q\choose s-q}$$

8. MSE 3051713

$$\sum_{k=q}^{2n} {2n+k\choose 2k} \frac{(2k-1)!!}{(k-q)!} (-1)^k$$ is zero when $q$ is odd and $$\frac{(-1)^{n+q/2}}{2^{2n}} \frac{(2n+q)!}{(n-q/2)!\times (n+q/2)!}$$ otherwise.

9. MSE 3068381

$$\sum_{j=n}^{2n} \sum_{k=j+1-n}^j (-1)^j 2^{j-k} {2n\choose j} {j\brace k} {k\brack j+1-n}$$

10. MSE 3138710

$$\sum_{j=0}^{\lfloor n/2\rfloor} {m+j+k\choose m-j+1} \frac{n}{n-j} {n-j\choose j} = {n+k+m\choose m+1}$$

11. MSE 3196998

$$F_{2n+2} = \sum_{p=0}^n \sum_{q=0}^n {n-p\choose q} {n-q\choose p}$$

12. MSE 3245099

$$\sum_{q=0}^{K-1} {K-1+q\choose K-1} \frac{a^qb^K+a^kb^q}{(a+b)^{q+K}} = 1$$

13. MSE 3260307

$${r+2n-1\choose n-1} - {2n-1\choose n-1} = \sum_{k=1}^{n-1} {2k-1\choose k} {r+2(n-k)-1\choose r+n-k}$$

14. MSE 3285142

$$\sum_{k=1}^n \left(-\frac{1}{4}\right)^k {2k\choose k}^2 \frac{1}{1-2k} {n+k-2\choose 2k-2}$$ is zero when $n$ is odd and $$\left[\left(\frac{1}{4}\right)^m {2m\choose m} \frac{1}{1-2m}\right]^2$$ when $n=2m$ is even

15. MSE 3333597

$$\sum_{n=0}^N \sum_{k=0}^N \frac{(-1)^{n+k}}{n+k+1} {N\choose n} {N\choose k} {N+n\choose n} {N+k\choose k} = \frac{1}{2N+1}$$

16. MSE 3342361

$$\sum_{k=3}^n (-1)^k {n\choose k} \sum_{j=1}^{k-2} {j(n+1)+k-3\choose n-2} = (-1)^{n-1} \left[ {n\choose 2} - {2n+1\choose n-2} \right]$$

17. MSE 3383557

$$n\sum_{k=0}^n \frac{(-1)^k}{2n-k} {2n-k\choose k} x^k y^{2n-2k} = \frac{1}{2^{2n}} \sum_{k=0}^n {2n\choose 2k} y^{2k} (y^2-4x)^{n-k}$$

18. MSE 3441855

$$\sum_{k=0}^n (-1)^k 4^{n-k} {2n-k\choose k} = 2n+1$$

19. MSE 3577193

$$\sum_{k=0}^l {k\choose m} {k\choose n} = \sum_{k=0}^n (-1)^k {l+1\choose m+k+1} {l-k\choose n-k}$$

20. MSE 3583191

$$\sum_{j=0}^k {2n\choose 2j} {n-j\choose k-j} = \frac{4^k n}{n+k} {n+k\choose n-k}$$

21. MSE 3592240

$$\sum_{q=m}^{n-k} (-1)^{q-m} {k-1+q\choose k-1} {q\brace m} {n\brack q+k} = {n-1\choose m} {n-m\brack k}$$

22. MSE 3604802

$$\sum_{q=0}^N (-1)^q {2q\choose q} {N+q\choose N-q} \frac{q^2}{(q+1)^2} = (-1)^N + \frac{1}{N(N+1)}$$

23. MSE 3619182

$$\sum_{k=0}^n {n\choose k}^2 \sum_{l=0}^k {k\choose l} {n\choose l} {2n-l\choose n} = \sum_{k=0}^n {n\choose k}^2 {n+k\choose k}^2$$

24. MSE 3638162

$$\sum_{k=1}^n (-1)^{a-k} {a\choose k} {b+k\choose b+1} = {b\choose a-1}$$

25. MSE 3661349

$$\sum_{q=0}^k (-1)^{q-j} {n+q\choose q} {n+k-q\choose k-q} {2n\choose n+j-q} = {2n\choose n}$$ where $0\le j\le k.$

26. MSE 3706767

$$\sum_{k=m}^n {k+m\choose 2m} {2n+1\choose n+k+1} = {n\choose m} 4^{n-m}$$

27. MSE 3737197

$$\sum_{j=0}^k {k\choose j} {j/2\choose n} (-1)^{n-j} = \frac{k}{n} 2^{k-2n} {2n-k-1\choose n-1}$$

28. MSE 3825092

$$\sum_{k=1}^n (-1)^{n-k} k^n {n+1\choose n-k} = 1$$

29. MSE 3845061

$$\sum_{q=a+1}^n {q-1\choose a} {n-q\choose k-a} = {n\choose k+1}$$ or alternatively $$\sum_{q=0}^n {q\choose a} {n-q\choose b} = {n+1\choose a+b+1}$$

30. MSE 3885278

$$\sum_{k\ge 0} \frac{(2k+1)^2}{(p+k+1)(q+k+1)} {2p\choose p-k} {2q\choose q-k} = \frac{1}{p+q+1} {2p+2q\choose p+q}$$

31. MSE 3559223

With $$G_{n,j} = \sum_{k=1}^n \frac{k^j (-1)^{n-k} {n\choose k}}{\frac{1}{2}n(n+1)-k}$$ we have $$G_{n,j} = \frac{(\frac{1}{2} n(n+1))^{j-1}n!}{\prod_{q=1}^n (\frac{1}{2} n(n+1)-q)} - [[j\gt n]] n! \sum_{q=0}^{j-1-n} \left(\frac{1}{2} n(n+1)\right)^q {j-1-q\brace n}$$

32. MSE 3926409

$$\sum_{p=q}^k (-1)^p {k\choose p} (q-p)^k = \sum_{p=q}^k \left\langle k \atop p \right\rangle$$

33. MSE 3942039

$$\sum_{k=0}^n (-1)^k \frac{2^{n-k} {n\choose k}}{(m+k+1) {m+k\choose k}} = \sum_{k=0}^n \frac{n\choose k}{m+k+1}$$

34. MSE 3956698

$$\sum_{k\ge 1} \left[{\lfloor \frac{k}{2}\rfloor \choose m} + {\lceil \frac{k}{2}\rceil \choose m} \right] {n-1\choose k-1} = 2^{n-2m} {n-m\choose m-1} \frac{n+1}{m}$$

35. MSE 3993530

$$\sum_{k=0}^n \left\langle {n\atop k}\right\rangle x^{n-k} = (1-x)^n \sum_{k=0}^n {n\brace k} k! \left(\frac{x}{1-x}\right)^k$$

36. MSE 4008277

$$\sum_{k=0}^r k^p {m\choose k} {n\choose r-k} = \sum_{j=0}^p m^\underline{j} {m+n-j\choose m+n-r} {p\brace j}$$

37. MSE 4031272 (Li Shanlan identity)

$${m+k\choose k}^2 = \sum_{q=0}^m {k\choose m-q}^2 {2k+q\choose q}$$

38. MSE 4034224 (Eulerian numbers, Stirling numbers first and second kind)

Two alternate representations of second order Eulerian numbers: $$\sum_{j=0}^k (-1)^{k-j} {2n+1\choose k-j} {n+j\brace j} = \sum_{j=0}^{n-k} (-1)^j {2n+1\choose j} {2n-k-j+1\brack n-k-j+1}$$

39. MSE 4037172 (Eulerian numbers, associated Stirling numbers first and second kind)

Two alternate representations of second order Eulerian numbers: $$\sum_{j=0}^k (-1)^{k-j} {n-j\choose k-j} \left\{\!\!\left\{ n+j\atop j \right\}\!\!\right\} = \sum_{j=0}^{n-k+1} (-1)^{n-k-j+1} {n-j\choose k-1} \left[\!\!\left[ n+j\atop j \right]\!\!\right]$$

40. MSE 4037946 (Eulerian numbers, associated Stirling numbers first and second kind)

$${n\brack n-k} - {n\brace n-k} = \sum_{j=0}^k \left({n+j-1\choose 2k} - {n+k-j\choose 2k}\right) \left\langle\!\!\left\langle {k\atop j}\right\rangle\!\!\right\rangle$$

41. MSE 4055292

$$\sum_{k=0}^{2n} (-1)^k {n+k\choose k}^{-1} {2n\choose k} {2k\choose k} = 1$$

42. MSE 4054024

$$\sum_{k=1}^n {2n-2k\choose n-k} \frac{H_{2k}-2H_k}{2n-2k-1} {2k\choose k} = \frac{1}{n} \left[ 4^n - 3{2n-1\choose n} \right]$$

43. MSE 4084763

$$\sum_{q=0}^n {n\choose q} q^k = \sum_{q=1}^k n^\underline{q} {k\brace q} 2^{n-q}$$

44. MSE 4095795

$$\sum_{r=0}^n r^k = (n+1)\sum_{q=1}^k n^\underline{q} \frac{1}{q+1} {k\brace q}$$

45. MSE 4098492

$$\sum_{k=0}^n {k\choose m} {n-k\choose r-m} = {n+1\choose r+1}$$

46. MSE 4127695

$$\sum_{r=0}^n 2^{n-r} {n+r\choose r} = 4^n$$

47. MSE 4131219

With $$\mathcal{K}_k(x; n) = \sum_{j=0}^k (-1)^j {x\choose j} {n-x\choose k-j}$$ we have $$\sum_{\ell=0}^n \mathcal{K}_\ell(x;n) = 2^m {n-x\choose m}$$

48. MSE 4139722

$$B_n = \sum_{k=0}^n (-1)^k \frac{1}{k+1} H_{k+1} (k+2)! {n+1\brace k+1} + (-1)^{n+1} (n+1)$$

49. MSE 4192271

$$\sum_{q\ge k} {m+1\choose 2q+1} {q\choose k} = {m-k\choose k} 2^{m-2k}$$

50. MSE 4212878

$$\sum_{k=1}^{n-1} k{n\choose k} \frac{(2n-2k-1)!!}{(2n-1)!!} \sim \frac{1}{2}\sqrt{e}$$

51. A different obstacle from Concrete Mathematics by Knuth, Graham, and Patashnik

$$\sum_{k=0}^n {n+k\choose 2k} {2k\choose k} \frac{(-1)^k}{k+1+m} = \frac{(-1)^n \times m^\underline{n}}{(n+m+1)^\underline{n+1}}$$

52. MO 291738 (not quite the same as previous)

$$\sum_{k=0}^n \frac{(-1)^k}{2k+1} {n+k\choose n-k} {2k\choose k} = \frac{1}{2n+1}$$

53. A Stirling number identity by Gould

$${n\brack n-k} = (-1)^k {n\choose k} \sum_{j=0}^k {k\choose k} \sum_{q=0}^j (-1)^q {j+1\choose q+1} {j+qn+q\choose qn+q}^{-1} {j+qn+q\brace qn+q}$$

54. A Stirling number identity by Gould II

$${n\brack n-k} = (-1)^k {n-1\choose k} \sum_{j=0}^k (-1)^j {k+1\choose j+1} {jn+k\choose k}^{-1} {jn+k\brace jn}$$

55. Schläfli's identity for Stirling numbers

$${n\brack n-k} = \sum_{q=0}^k (-1)^{k-q} {n+q-1\choose n-k-1} {n+k\choose k-q} {k+q\brace q}$$

56. Stirling numbers and Faulhaber's formula

$$\sum_{k=0}^n k^p = \sum_{j=1}^{p+1} n^j \sum_{k=j}^{p+1} \frac{1}{k} {p+1\brace k} (-1)^{k-j} {k\brack j} \\ = \frac{1}{p+1} n^{p+1} + \frac{1}{2} n^p + \sum_{k=1}^{p-1} {p\choose k} \frac{B_{p+1-k}}{p+1-k} n^k$$

57. Stirling numbers and binomial coefficient

$$\sum_{k=0}^n (-1)^k {n\choose k} (x-k)^{n+j} = \sum_{k=0}^j {x-n\choose k} (n+k)! {n+j\brace n+k}$$

58. Stirling numbers and a double binomial coefficient

$$\sum_{k=0}^n (-1)^k {x\choose k} k^r = \sum_{k=0}^r (-1)^k {x\choose k} {n-x\choose n-k} k! {r\brace k}$$

59. Stirling numbers and a double binomial coefficient II

$$\sum_{k=0}^n (-1)^k {n\choose k} k^{n+j} = (-1)^n (n+j)! \sum_{k=0}^j {j-n\choose j-k} {n\choose k} \frac{k!}{(k+j)!} {k+j\brace k}$$

60. Stirling numbers and Bernoulli polynomials

$$\sum_{k=0}^n (-1)^k {n+x\choose n-k} \frac{1}{k+1} = \frac{1}{n!} \sum_{k=0}^n {n+1\brack k+1} B_k(x)$$

61. Central binomial coefficients and Stirling numbers

$$\sum_{k=0}^n {2k\choose k} \frac{k^r}{2^{2k}} = \frac{2n+1}{2^{2n}} {2n\choose n} \sum_{k=0}^r {n\choose k} \frac{1}{2k+1} k! {r\brace k}$$

62. Single variable monomial and two binomial coefficients

$$x^n = (-1)^{m+n} \sum_{k=0}^{m+1} {x+k-1\choose m} \sum_{p=0}^k (-1)^p {m+1\choose p} (k-p)^n$$

63. Use of an Iverson bracket

$$\sum_{k=0}^n {2k+1\choose j} = \frac{(-1)^{j+1}}{2^{j+2}} \left\{ \sum_{k=0}^{j+1} (-1)^k {2n+3\choose k} 2^k + 1 \right\}$$

64. Use of an Iverson bracket II

$$\sum_{k=0}^n (-1)^k {j+k\choose j} = \frac{(-1)^j}{2^{j+1}} \left\{ (-1)^n \sum_{k=0}^j (-1)^k {n+j+1\choose k} 2^k + (-1)^j \right\}$$

65. Use of an Iverson bracket III

$$\sum_{k=0}^n {x\choose n-k} {x\choose n+k} = \frac{1}{2} \left\{{2x\choose 2n} + {x\choose n}^2\right\}$$

66. Basic example

$$\sum_{k=0}^{\lfloor n/2\rfloor} {x\choose 2k} {x\choose n-2k} = \frac{1}{2} {2x\choose n} + \frac{1}{2} (-1)^{/2} {x\choose n/2} \frac{1+(-1)^n}{2}$$

67. Basic example continued

$$\sum_{k=0}^{\lfloor n/2\rfloor} {x\choose 2k} {2n-x\choose n-2k} = = \frac{1}{2} \left\{ {2n\choose n} + (-1)^n 2^{2n} {\frac{x-1}{2} \choose n} \right\}$$

68. An identity by Erik Sparre Andersen

$$\sum_{k=0}^r {x\choose k} {-x\choose n-k} = \frac{n-r}{n} {x-1\choose r} {-x\choose n-r}$$

69. Very basic example

$$\sum_{k=0}^{\lfloor n/2\rfloor} {x\choose k} {x-k\choose n-2k} 2^{n-2k} = {2x\choose n}$$

70. An identity by Karl Goldberg

$$\sum_{k=0}^n {x\choose k} {y+k\choose n-k} 2^{2k} = \sum_{k=0}^n {2x\choose k} {y\choose n-k} 2^k = \sum_{k=0}^n {2x\choose k} {2x+y-k\choose n-k}$$

71. Sum producing a square root

$$\sum_{k=0}^n {2x\choose 2k} {x-k\choose n-k} = \frac{x}{x+n} {x+n\choose 2n} 2^{2n} = \frac{2^{2n}}{(2n)!} \prod_{k=0}^{n-1} (x^2-k^2)$$

72. Sum producing a square root II

$$\sum_{k=0}^n {2x+1\choose 2k+1} {x-k\choose n-k} = \frac{2x+1}{2n+1} {x+n\choose 2n} 2^{2n} = \frac{2x+1}{(2n+1)!} \prod_{k=0}^{n-1} ((2x+1)^2-(2k+1)^2)$$

73. Use of an Iverson bracket IV

$$\sum_{k=0}^n (-1)^k {x\choose n-k} {x\choose n+k} = \frac{1}{2} \left\{ {x\choose n}+{x\choose n}^2 \right\}$$

74. Binomial coefficient manipulation

$$\sum_{k=0}^n (-1)^k {2n\choose k} {2x-2n\choose x-k} = \frac{1}{2} (-1)^n \left\{ {x\choose n}+{x\choose n}^2 \right\} {2x\choose x} {2x\choose 2n}^{-1}$$

75. Four binomial sums

$$\sum_{k=0}^n (-1)^k {x\choose k} {2n-x\choose n-k} = \sum_{k=0}^{\lfloor n/2\rfloor} (-1)^k {x\choose k} {2n-2x\choose n-2k} \\ = (-1)^n \sum_{k=0}^n (-1)^k {2n-k\choose n-k} {2n-x\choose k} 2^k \\ = \sum_{k=0}^n (-1)^k 2^k {x\choose k} {2n-k\choose n} \\ = \frac{2^n}{n!} \prod_{k=0}^{n-1} (2k+1-x) = (-1)^n 2^{2n} {\frac{x-1}{2} n}$$

76. Power term and two binomial coefficients

$$\sum_{k=0}^n {n\choose k}^2 k^r = \sum_{k=0}^r {n\choose k} {2n-k\choose n} k! {r\brace k}$$

77. Use of an Iverson bracket V

$$\sum_{k=0}^n (-1)^k {2n\choose k}^2 = \frac{1}{2} (-1)^n \left\{ {2n\choose n} + {2n\choose n}^2 \right\}$$

78. Use of an Iverson bracket VI

$$\sum_{k=0}^{\lfloor n/2 \rfloor} {2n\choose 2k}^2 = \frac{1}{4} {4n\choose 2n} + \frac{1}{4} (-1)^n {2n\choose n} + \frac{1+(-1)^n}{4} {2n\choose n}^2$$

79. Appearance of the constants three and five

$$2^{2n} \sum_{k=0}^n {n\choose k} {2k\choose k} = \sum_{k=0}^n {2n-2k\choose n-k} {2k\choose k} 5^k$$ $$2^{2n} \sum_{k=0}^n (-1)^k {n\choose k} {2k\choose k} = \sum_{k=0}^n (-1)^k {2n-2k\choose n-k} {2k\choose k} 3^k$$

80. Generating function of a binomial term

$$\sum_{k=0}^n {2n-2k\choose n-k} {2k\choose k} \frac{x}{x+k} = 2^{2n} {x+n\choose n}^{-1} {n+x-1/2\choose n}$$

81. Double square root

$$\sum_{k=0}^n {2n-2k\choose n-k} {2k\choose k} \frac{1}{(2k-1)(2n-2k+1)} = \frac{2^{4n}}{2n(2n+1)} {2n\choose n}^{-1} $$

82. Central Delannoy numbers

$$\sum_{k=0}^n {4n-4k\choose 2n-2k} {4k\choose 2k} = 2^{4n-1} + 2^{2n-1} {2n\choose n}$$ $$\sum_{k=0}^n {4n-4k-2\choose 2n-2k-1} {4k+2\choose 2k+1} = 2^{4n-1} - 2^{2n-1} {2n\choose n}$$

83. A case of factorization

$$\sum_{k=0}^n (-1)^k {n+k\choose 2k} {2k\choose k} \frac{x}{x+k} = (-1)^n {x+n\choose n}^{-1} {x-1\choose n}$$

84. Two identities due to Grosswald

$$\sum_{k=0}^n (-1)^k {n\choose k} {n+2r+k\choose n+r} 2^{n-k} = (-1)^{n/2} \frac{1+(-1)^n}{2} {n+r\choose n} {n+r\choose n/2} {n+2r\choose r}$$ $$\sum_{k=0}^{n-r} (-1)^k {n\choose k+r} {n+k+r\choose k} 2^{n-r-k} = (-1)^{(n-r)/2} \frac{1+(-1)^{n-r}}{2} {n\choose (n-r)/2}$$

85. Appearance of the constant three

$$\sum_{k=0}^{2n} (-1)^k {2n\choose k} {2n+2k\choose n+k} 3^{2n-k} = {2n\choose n}$$

86. Very basic example

$$\sum_{k=0}^n {4n+1\choose 2n-2k} {k+n\choose n} = 2^{2n} {3n\choose n}$$

87. Very basic example II

$$\sum_{k=0}^n (-1)^k {2n\choose n-k} {2n+2k+1\choose 2k} = (-1)^n (n+1) 2^{2n}$$

88. Nested square root

$$\sum_{k=0}^n {2k\choose k} {2n-k\choose n} \frac{k}{(2n-k)\times 2^k} = (-1)^n 2^{2n} {-1/4\choose n}$$

89. Harmonic numbers and a squared binomial coefficient

$$\sum_{k=1}^n {n\choose k}^2 H_k = {2n\choose n} (2H_n - H_{2n})$$

90. Harmonic numbers and a double binomial coefficient

$$\sum_{k=1}^n (-1)^k {n\choose k} {n+k-1\choose k} H_k = \frac{(-1)^n}{n}$$ $$\sum_{k=1}^n (-1)^k {n\choose k} {n+k-1\choose k} H_{n+k-1} = \frac{(-1)^n}{n}$$

91. Two instances of a Harmonic number

$$\sum_{k=1}^n (-1)^{k-1} {n\choose k} {n+k\choose k} \frac{1}{k} = 2 H_n$$

92. Legendre Polynomials

$$P_n(x) = \frac{1}{2^n} \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k {n\choose k} {2n-2k\choose n} x^{n-2k}$$ $$P_n(x) = \left[\frac{x-1}{2}\right]^n \sum_{k=0}^n {n\choose k}^2 \left[\frac{x+1}{x-1}\right]^k$$ $$P_n(x) = (-1)^n \sum_{k=0}^n {n\choose k} {n+k\choose k} (-1)^k \left[\frac{x+1}{2}\right]^k$$ $$P_n(x) = \sum_{k=0}^n {n\choose k} {n+k\choose k} \left[\frac{x-1}{2}\right]^k$$

93. Legendre Polynomials and a square root

$$P_n(x) = \sum_{k=0}^n {n\choose k} {2k\choose k} 2^{-k} \sqrt{x^2-1}^k \left[x-\sqrt{x^2-1}\right]^{n-k}$$ $$P_n(x) = \sum_{k=0}^{\lfloor n/2\rfloor} {n\choose 2k} {2k\choose k} 2^{-2k} x^{n-2k} (x^2-1)^k$$

94. Legendre Polynomials and a double square root

$$\sum_{k=0}^n {2k\choose k} {2n-2k\choose n-k} x^{2k} = 2^{2n} x^n P_n((x+1/x)/2) = 2^{2n} \frac{2}{\pi} \int_0^{\pi/2} (x^2 \sin^2 t + \cos^2 t)^n \; dt$$ $$\sum_{k=0}^n {-1/2\choose k} {-1/2\choose n-k} x^{2k} = (-1)^n x^n P_n((x+1/x)/2) = \sum_{k=0}^n (-1)^k {n\choose k} {k-1/2\choose n} x^{2k}$$

95. MSE 4304623

$$\sum_{r=0}^n \frac{1}{4^r} {2r\choose r} = \frac{1}{2^n} \sum_{q=0}^n {n+q\choose n} \frac{1}{2^q} (n-q+1) = {n+1/2\choose n} $$

96. Legendre Polynomials, trigonometric terms and a contour integral

$$P_n(x) = \frac{1}{\pi} \int_0^\pi (x+\sqrt{x^2-1} \times \cos t)^n \; dt$$ $$P_n(x) = \frac{1}{m} \sum_{k=0}^{m-1} \left(x+\sqrt{x^2-1} \times \cos \frac{2\pi k}{m}\right)^n$$ $$P_n(x) = \frac{1}{2^n} \frac{1}{2\pi i} \int_{|t-x|=\varepsilon} \frac{(t^2-1)^n}{(t-x)^{n+1}} \; dt$$

97. Sum independent of a variable

$$\sum_{k=0}^n {x+ky\choose k} {p-x-ky\choose n-k} = \begin{cases} y^{p+1} (y-1)^{n-p-1}, & 0\le p\le n-1 \\ \frac{y^{n+1}-1}{y-1}, & p=n \\ \end{cases}$$

98. Polynomial in three variables

$$\sum_{k=0}^n {x+kt\choose k} {y-kt\choose n-k} = \sum_{k=0}^n {x+y-k\choose n-k} t^k$$

99. An identity by Van der Corput

$$\sum_{k=1}^{n-1} {kx\choose k} {nx-kx\choose n-k} \frac{1}{kx(nx-kx)} = \frac{2}{nx} {nx\choose n} \sum_{k=1}^{n-1} \frac{1}{nx-n+k}$$

100. MSE 4316037 Logarithm, binomial coefficient and harmonic numbers

$$[z^n] \frac{1}{(1-z)^{\alpha+1}}\log\frac{1}{1-z} = {n+\alpha\choose n} (H_{n+\alpha} - H_\alpha)$$

101. An identity credited to Chung

$$\sum_{k=1}^n \frac{1}{k} {kx-2\choose k-1} {nx-kx\choose n-k} = \frac{1}{x} {nx\choose n}$$

102. MSE 4317353 A Catalan number convolution

$$C_{n-1} = \sum_{k=1}^{\lfloor n/2\rfloor} 2^{n-2k} {n-2\choose n-2k} \frac{1}{k} {2k-2\choose k-1}$$

103. Odd index binomial coefficients

$$\sum_{k=0}^{n-1} {2x\choose 2k+1} {x-k-1\choose n-k-1} = \frac{n}{x+n} 2^{2n} {x+n\choose 2n}$$ $$\sum_{k=0}^{n-1} {2x\choose 2k+1} {x-k-1\choose n-k} = \frac{x+n}{2n+1} 2^{2n+1} {x+n-1\choose 2n}$$

104. MSE 4325592 A sum of inverse binomial coefficients

$$\sum_{k=1}^{a-b} \frac{(a-b-k)!}{(a+1-k)!} = \frac{1}{b} \left[\frac{1}{b!}-\frac{(a-b)!}{a!}\right]$$

105. Inverted sum index

$$\sum_{k=a}^n (-1)^k {k\choose a} {n+k\choose 2k} 2^{2k} \frac{2n+1}{2k+1} = (-1)^n {n+a\choose 2a} 2^{2a}$$

106. MSE 4351714 A Catalan number recurrence

$$\sum_{j=1}^{n+1} {n+j\choose 2j-1} (-1)^{n+j} C_{n+j-1} = 0$$

107. An identity by Graham and Riordan

$$\sum_{k=0}^n \frac{2k+1}{n+k+1} {x-k-1\choose n-k} {x+k\choose n+k} = {x\choose n}^2$$

108. Square root term

$$\sum_{k=0}^{\lfloor n/2\rfloor} {n+1\choose 2k+1} {x+k\choose n} = {2x\choose n}$$ $$\sum_{k=0}^{\lfloor (n+1)/2\rfloor} {n+1\choose 2k} {x+k\choose n} = {2x+1\choose n}$$

109. An identity by Machover and Gould

$$\sum_{k=0}^n {x\choose 2k} {x-2k\choose n-k} 2^{2k} = {2x\choose 2n}$$ $$\sum_{k=0}^n {x+1\choose 2k+1} {x-2k\choose n-k} 2^{2k+1} = {2x+2\choose 2n+1}$$

110. Moriarty identity by H.T.Davis et al.

$$\sum_{k=0}^{n-p} {2n+1\choose 2p+2k+1} {p+k\choose k} = {2n-p\choose p} 2^{2n-2p}$$ $$\sum_{k=0}^{n-p} {2n+1\choose 2p+2k} {p+k\choose k} = \frac{n}{2n-p} {2n-p\choose p} 2^{2n-2p}$$

111. Inverse Moriarty identity by Marcia Ascher.

$$\sum_{k=r}^{\lfloor n/2\rfloor} (-1)^k {n-k\choose k} {k\choose r} 2^{n-2k} = (-1)^r {n+1\choose 2r+1}$$ $$\sum_{k=r}^{\lfloor n/2\rfloor} (-1)^k \frac{n}{n-k} {n-k\choose k} {k\choose r} 2^{n-2k-1} = (-1)^r {n+1\choose 2r+1}$$

112. Moriarty identity by Egorychev

$$\sum_{k=m}^n (-1)^k 2^{2k} {k\choose m} \frac{n}{n+k} {n+k\choose 2k} = (-1)^n 2^{2m} \frac{n}{n+m} {n+m\choose 2m}$$

113. MSE 4462359 Two binomial coefficients

$$\sum_{q=0}^m \frac{(-1)^{q-1}}{q+1} {k+q\choose q} {k\choose q} = \frac{(-1)^{m+1}}{k+1} {k-1\choose m} {k+1+m\choose k}$$

114. Polynomial identity

$$\sum_{k=1}^n (-1)^{k-1} {n\choose k} \frac{f(x-k)}{k} = H_n f(x) - f'(x)$$

115. Polynomial identity II

$$f(x+y) = y {y+n\choose n} \sum_{k=0}^n (-1)^k {n\choose k} \frac{f(x-k)}{y+k}$$

116. Worpitzky-Nielsen series

$$f(x+y) = (-1)^m \sum_{k=0}^{m+1} {x+k-1\choose m} \sum_{j=0}^k (-1)^j {m+1\choose j} f(j-k+y)$$

117. MSE 4517120 A sum of inverse binomial coefficients

$$\sum_{k=0}^n {m+k\choose m}^{-1} = \frac{m}{m-1} \left[1-{m+n\choose m-1}^{-1}\right]$$

118. MSE 4520057 Symmetric Bernoulli number identity

$$(-1)^n \sum_{g=0}^m \frac{B_{n+g+1}}{n+g+1} {m\choose g} + (-1)^m \sum_{g=0}^n \frac{B_{m+g+1}}{m+g+1} {n\choose g} = - \frac{1}{n+m+1} {n+m\choose m}^{-1}$$

119. Polynomial identity III

$$\sum_{k=0}^n (-1)^k {2n\choose n+k} \frac{f(y+k^2)}{x^2-k^2} = (-1)^n \frac{f(x^2+y)}{2x(x-n)} {x+n\choose 2n}^{-1} + \frac{1}{2} {2n\choose n} \frac{f(y)}{x^2}$$

120. Polynomial identity IV

$$\sum_{k=0}^n (-1)^k {n\choose k} {k+r\choose k}^{-1} f(y-k) = - \sum_{k=1}^r (-1)^k {r\choose k} {k+n\choose k}^{-1} f(y+k)$$

121. MSE 4540192 Symmetry in a simple proof

$$\sum_{q=0}^{\lfloor n/2\rfloor} (n-2q)^n {n\choose q} (-1)^q = 2^{n-1} n!$$

122. Free functional term

$$\sum_{k=0}^n (-1)^k {x\choose k} \sum_{j=0}^k (-1)^j {k\choose j} f(j) = (-1)^n {x-1\choose n} \sum_{k=0}^n (-1)^k {n\choose k} \frac{x f(k)}{x-k}$$

123. MSE 4547110 Inverse central binomial coefficient

$$\sum_{k=1}^n \frac{(-1)^{k+1} 2^{2k}}{k} {n\choose k} {2k\choose k}^{-1} = 2 H_{2n} - H_n$$

124. MSE 1402886 Inverse binomial coefficient

$$\sum_{r=0}^n (-1)^r {n\choose r}^{-1} = (1+(-1)^n) \frac{n+1}{n+2}$$

125. MSE 4552694 A pair of binomial transforms

$$\alpha_{n} = \sum_{k=0}^{n} \binom{n+k}{n-k}\beta_{k} \Leftrightarrow \beta_{n} = \sum_{k=0}^{n} (-1)^{n-k}\frac{2k+1}{2n+1} \binom{2n+1}{n-k}\alpha_{k}$$

126. Polynomial with inverse binomial coefficients

$$\sum_{k=0}^n x^k {n\choose k}^{-1} = (n+1) \left(\frac{x}{1+x}\right)^{n+1} \sum_{k=1}^{n+1} \frac{1}{k} \frac{1+x^k}{1+x} \left(\frac{1+x}{x}\right)^k$$

127. Harmonic numbers with inverse binomial coefficients

$$\sum_{k=1}^{2n-1} (-1)^{k-1} {2n\choose k}^{-1} H_k = \frac{1}{2} \frac{n}{(n+1)^2} + \frac{1}{2}\frac{1}{n+1} H_{2n}$$

128. Simon's identity

$$\sum_{k=0}^n {n\choose k} {n+k\choose k} x^k = \sum_{k=0}^n {n\choose k} {n+k\choose k} (-1)^{n-k} (x+1)^k$$

129. Identity from Abramowitz and Stegun / Schläfli's formula

$${n\brack m} = (-1)^{n-m} \sum_{k=0}^{n-m} (-1)^k {n-1+k\choose n-m+k} {2n-m\choose n-m-k} {n-m+k\brace k}, \quad\text{and} \\ {n\brace m} = (-1)^{n-m} \sum_{k=0}^{n-m} (-1)^k {n-1+k\choose n-m+k} {2n-m\choose n-m-k} {n-m+k\brack k}$$

130. Bernoulli / Stirling number identity

$$B_n = \sum_{k=0}^n (-1)^k {n+1\choose k+1} {n+k\brace k} {n+k\choose k}^{-1}$$

131. Recurrence relation from DLMF

$${k\choose h} {n\brack k} = \sum_{j=k-h}^{n-h} {n\choose j} {n-j\brack h} {j\brack k-h}\quad\text{and} \\ {k\choose h} {n\brace k} = \sum_{j=k-h}^{n-h} {n\choose j} {n-j\brace h} {j\brace k-h}$$

132. Bernoulli, Fibonacci and Lucas numbers

$$\sum_{k=0}^{\lfloor n/2\rfloor} {n\choose 2k} \left(\frac{5}{9}\right)^k B_{2k} F_{n-2k} = \frac{n}{6} L_{n-1} + \frac{n}{3^n} L_{2n-2}$$

133. Bernoulli / exponential convolution

$$B_n = \frac{1}{m(1-m^n)} \sum_{k=0}^{n-1} m^k {n\choose k} B_k \sum_{j=1}^{m-1} j^{n-k}$$

134. Bernoulli identity by Munch

$$B_n = \frac{1}{n+1} \sum_{k=1}^n \sum_{j=1}^k (-1)^j j^n {n+1\choose k-j} {n\choose k}^{-1}$$

135. Bernoulli identity by Kronecker

$$B_{2n} = \sum_{j=2}^{2n+1} (-1)^{j-1} {2n+1\choose j} \frac{1}{j} \sum_{k=1}^{j-1} k^{2n}$$

136. Computing Bernoulli numbers

$$B_{n+1} = \frac{n+1}{2(1-2^{n+1})} \sum_{k=0}^n \frac{(-1)^k}{2^k} k! {n\brace k},\quad\text{and}\quad \\ B_{n+1} = \frac{n+1}{2^{n+1}(2^{n+1}-1)} \sum_{k=0}^n (-1)^{k+1} \sum_{j=0}^k (-1)^j {n+1\choose j} (k-j)^n$$

From the Saalschütz text

• Bernoulli numbers I

$$\sum_{k=1}^n {2n+1\choose 2k-1} \left( 2^{n+1-k} - \frac{1}{2^{n+1-k}} \right)^2 B_{2n+2-2k} = (2n+1) \left(\frac{1}{4} + \frac{1}{2^{2n+1}}\right)$$

• Bernoulli numbers II

$$\sum_{k=1}^n {2n\choose 2k} 2^{4k} B_{2k} = 4n-1 - (2^{2n} - 2) B_{2n}$$

• Bernoulli numbers III

$$\sum_{k=1}^{m} \frac{1}{k+1} (-1)^k k! {m\brace k} = B_{m}\quad\text{and}\quad \\ \sum_{k=1}^{m} \frac{1}{k(k+1)} (-1)^{k+1} k! {m\brace k} = B_{m}$$

• Bernoulli numbers IV

$$\sum_{k=1}^m {2m\brack 2k} B_{2k} = \frac{(2m-1)(2m-1)!}{2(2m+1)} \quad\text{and}\quad \\ \sum_{k=1}^m {2m+1\brack 2k} B_{2k} = \frac{m(2m)!}{2m+2}$$

• Bernoulli and Eulerian numbers I

$$B_{2m} = \frac{1}{2m(2m+1)} \sum_{k=0}^{m-1} (-1)^k (2m-1-2k) {2m-1\choose k}^{-1} \left\langle {2m \atop k} \right\rangle$$

• Bernoulli and Eulerian numbers II

$$\frac{1-2^{2m}}{2^{2m-1}} \frac{B_{2m}}{2m} = {m-\frac{1}{2}\choose 2m} \left\langle {2m-1 \atop m-1} \right\rangle + 2 \sum_{k=1}^{m-1} {k-\frac{1}{2}\choose 2m} \left\langle {2m-1 \atop k-1} \right\rangle$$

• Bernoulli numbers V

$$E_{2m} = \frac{1}{2m+1} \left\{ 4m+1 - \sum_{k=1}^{m} {2m+1\choose 2k} B_{2k} 2^{4k}\right\}$$

• Bernoulli numbers and roots of unity

$$B_{2m} = \frac{(2m)!}{2^{4m} (2^{2m}-1)} [z^{2m}] \prod_{q=0}^{2m-1} (\exp(\zeta_{2m}^q z) + \exp(-\zeta_{2m}^q z)) \\ \quad\text{where}\quad \zeta_{2m} = \exp(2\pi i/(2m))$$

138. Worpitzky's identity

$$x^n = \sum_{k=0}^{n-1} {x+k\choose n} \left\langle {n \atop k} \right\rangle$$

139. MSE 4627726: Quadruple binomial coefficient

$$2^N = \sum_{m=0}^N \sum_{r=0}^n \sum_{s=0}^m (-1)^{n+m} (-2)^{r+s} {n\choose r} {m\choose s} {N-r\choose m} {N-s\choose n}$$

140. MSE 4627918: Alternating power sum

$$\sum_{k=0}^m k^\ell (-1)^k {n\choose k} = (-1)^m n {n-1\choose m} \sum_{k=1}^\ell \frac{1}{n-k} m^{\underline{k}} {\ell\brace k}$$

141. MSE 4227433: Squared power sum

$$\sum_{k=1}^n k^\ell {n\choose k}^2 = \sum_{k=1}^\ell {2n-k\choose n} n^{\underline{k}} {\ell\brace k}$$

142. MSE 4428892: Ordinary power sum

$$\sum_{q=1}^n q^k = (n+1) n \sum_{q=1}^k {k\brace q} \frac{(n-1)^{\underline{q-1}}}{q+1}$$

143. MSE 3932757: Stirling numbers and a tree-function like term

$$\sum_{k=0}^m {m\choose k} {n+k+1\brace k+1} k! = \sum_{k=0}^m {m\choose k} (-k)^{m-k} (k+1)^{n+k}$$

144. MSE 4641290: A vanishing variable

$$\sum_{k=1}^n \frac{\prod_{1\le r\le n, r\ne m} (x+k-r)} {\prod_{1\le r\le n, r\ne k} (k-r)} = 1$$

145. MSE 4644963: From trigonometric to rational

$$\sum_{k=1}^N (-1)^k (\cos \frac{k\pi}{N})^{N-m} (\sin\frac{k\pi}{N})^m = \frac{1+(-1)^m}{2} (-1)^{m/2} \frac{N}{2^{N-1}}$$

146. MSE 4657112: Triple combinatorial numbers to constant

$$1=\sum_{p=0}^n (-1)^p {n+q\choose n-p-1} {n+p\choose n-q-1} {p+q\choose p}$$ $$1=(-1)^q \sum_{p=0}^n (-1)^p {n+q\choose n-p-1} {n+p\choose n-q-1} {p+q\brack p}$$

Computer search

• OEIS A106800

  $${n\brace n-m} = (-1)^{n-m} \sum_{k=0}^n (-1)^k {m-1+k\choose m-n+k} {2n-m\choose n-m-k} {n \brace k}$$

• OEIS A079901

  $$n^m = \sum_{k=0}^n (-1)^k {n\brack n-k} {n-k+m\brace n}$$

• OEIS A104684

  $${n\choose m} {2n-m\choose n} = (-1)^{n-m} \sum_{k=0}^{n-m} (-1)^k {n+k\choose n}^2 {2n-m\choose n-m-k}$$

• OEIS A003056

  $$n = (-1)^{n+1} \sum_{k=0}^n (-1)^k {m+k\choose m} {m+n\choose n-k-1} {m-1+k\choose m-n+k} $$

• OEIS A155865

  $${n-2\choose m-1} = \frac{(-1)^{m-1}}{n-1} \sum_{k=0}^n (-1)^k {n+k\choose n-m-1} {n+1\choose k+1} {2k\choose m-1}$$

• OEIS A033276

  $${n+m\choose m-1} {n-1\choose m-1} \frac{1}{m} = (-1)^n \sum_{k=0}^n (-1)^k {k\choose m} \frac{1}{k+1} {2k\choose k} {n+k\choose n-k}$$

• OEIS A051162

  $$n+m = \sum_{k=0}^n (-1)^k {n+m\choose n-k-1} {m-1+k\choose k} {n+m+k\choose n}$$

• OEIS A122899

  $${n\choose m} {m+1\choose n-m} = (-1)^n \sum_{k=0}^n (-1)^k {n\choose k} {k\choose m} {k+1\choose m+1}$$

• OEIS A110555

  $${n-1\choose m} = (-1)^m \sum_{k=0}^n (-1)^k {m+k\choose m} {2n\choose n+k} {n-1+k\choose k}$$

• OEIS A141662

  $$n-m^2 = (-1)^m \sum_{k=0}^n (-1)^k {n+m\choose n-k-1} {m-1+k\choose k} {m-1+k\choose m}$$

• OEIS A046816

  $${n\choose m} {m\choose p} = (-1)^m \sum_{k=0}^n (-1)^k {m\choose k} {k\choose p} {k-p+n\choose k}$$

• OEIS A001700

  $${2p-1\choose p-1} = (-1)^p \sum_{k=0}^{n-m} (-1)^k {2n-m\choose n-m-k} {n-1+k\choose k} {k-p+n\choose p}$$

• OEIS A007318

  $${n-1\choose p} = (-1)^p \sum_{k=0}^{n-m} (-1)^k {p+k\choose k} {2n-m\choose n-m-k} {n-1+ k\choose k}$$ $${2n-m\choose n-1} - {n-1\choose m-2} = (-1)^{n-m} \sum_{k=0}^{n-m} (-1)^k {n-m+1+k\choose k} {2n-m\choose n-m-k} {n-1+ k\choose k}$$

• OEIS A144484

  $${3n+1-m\choose 2n+1} = (-1)^{n-m} \sum_{k=0}^{n-m} (-1)^k {n-m+k\choose k} {2n-k\choose n-m-k} {2n+1\choose k}$$

• OEIS A130595

  $${n\choose m} = (-1)^{n+m} \sum_{k=0}^n (-1)^k {n\choose k} {n-m+k\choose k} {m-k+n\choose m}$$

• OEIS A011973

  $${n-m-1\choose m-1} = \sum_{k=0}^n (-1)^k {n-1+k\choose n-m+k} {2m\choose m+k} {m-1+k\choose k}$$

• OEIS A253909

  $$n^2 = \sum_{k=0}^n (-1)^k {k-n\choose n}^2 {2n+1\choose k}$$

• OEIS A142150

  $$(-1)^{(n+1)/2} \frac{n+1}{2} \times \frac{1+(-1)^{n+1}}{2} = \sum_{k=0}^n (-1)^k {n-k\choose k} {2k-n\choose n} {2k\choose n-1}$$

• OEIS A001147

  $$\frac{(2n)!}{2^n n!} = (-1)^n \sum_{k=0}^n (-1)^k {2n\choose n+k} {n+k\brack k}$$

• OEIS A243594

  $${n\choose m} n^m = (-1)^n \sum_{k=0}^n {n\choose k} (-1)^k {n-m+k\choose k} {kn+m\choose m}$$

• OEIS A013609

  $${n\choose m} 2^m = (-1)^n \sum_{k=0}^n {n\choose k} (-1)^k {2k\choose m} {n-m+k\choose k}$$

• OEIS A181543

  $${n\choose m}^3 = \sum_{k=0}^n {n\choose k} {k\choose m} {m\choose k-m} {n-m+k\choose n}$$

• OEIS A008279

  $${n\choose m} m! = (-1)^n \sum_{k=0}^n {n\choose k} (-1)^k {n-m+k\choose n-m} k^m$$

• OEIS A100100

  $${2n-m-1\choose n-1} = (-1)^n \sum_{k=0}^n (-1)^k {2n\choose n+k} {m-1+k\choose k-n+m} {n-1+k\choose n}$$

• OEIS A076756

  $${2n-m\choose m} = (-1)^{n+m} \sum_{k=0}^n {2n+1\choose k} (-1)^k {2m-k\choose m} {2n-k\choose n}$$

• OEIS A130595

  $${n\choose m} = (-1)^{n+m} \sum_{k=0}^n {n\choose k} (-1)^k {nm-k+m\choose m} {n-m+k\choose k}$$

• OEIS A206735

  $${n\choose m} = (-1)^{n+m} \sum_{k=0}^n {n+m\choose m+k} (-1)^k {m-1+k \choose k-n+m} {n+m+k\choose m}$$

• OEIS A318107

  $${n\choose m} {2n-m\choose n} {3n-2m\choose n-m} = \sum_{k=0}^n {2n-m\choose n-m-k}^2 {m+k\choose k} {n+k\choose m+k}$$

• OEIS A123110

  $$1 = (-1)^m \sum_{k=0}^n (-1)^k {2n\choose n+k} {n-1+k\choose n-m+k} {n-1+k\choose n}$$

• OEIS A202409

  $$\frac{1}{n-m+1} {n+1\choose m+1} {n+1\choose m} \left[ (n+1) {n+1\choose m+1} - m {n\choose m+1} \right] \\ = \sum_{k=0}^n {n+1\choose k+1} {n-k\choose m-k} {n+k+1\choose k+1} {n-m\choose k}$$

• OEIS A001498

  $$\frac{(n+m)!}{2^m \times (n-m)! \times m!} = (-1)^n \sum_{k=0}^n (-1)^k {n+m\choose m+k} {m+k\brack k} {k-m\choose n-m}$$

• OEIS A086810

  $$\frac{1}{n+1} {n+m\choose m} {n-1\choose m-1} = (-1)^n \sum_{k=0}^n (-1)^k {k\choose m} {n+k\choose 2k} \frac{1}{k+1} {2k\choose k}$$

• OEIS A008459

  $${n\choose m}^2 = \sum_{k=0}^n {m+k\choose m-k} {2k\choose k} {n\choose m+k}$$

• OEIS A130321

  $$2^{n-m} = \sum_{k=0}^n (-1)^k {n+m-k\choose k} {2n-2k\choose n-k}$$

148. MSE 4667102: Two different representations of a coefficient

$$\sum_{k=0}^r {n\choose 2k} {n-2k\choose r-k} = \sum_{k=r}^n {n\choose k} {2k\choose 2r} \left(\frac{3}{4}\right)^{n-k} \left(\frac{1}{2}\right)^{2k-2r}$$

149. MSE 4675665: Rational term of constant degree

$$\sum_{k=0}^n k^2 {n+k\choose k} = \frac{1}{2} (n+1)^2 {2n+2\choose n-1}$$

150. MSE 4666141: Double square root

$$2^m \sum_{k=0}^m \sum_{j=0}^p (-1)^j {k\choose j} {m-k\choose p-j} {m\choose k} {1/2(m+k-1)\choose m} = (-1)^p {m\choose p}^2$$

151. MSE 4699857: Four auxiliary variables

$${n+c\choose a} {n+d\choose b} = \sum_{q=0}^{a+b} {a-c+d\choose q-c} {b-d+c\choose q-d} {n+q\choose a+b}$$

152. MSE 4703564: A family of odd polynomials

$$[x^{2p}] P_{m,n}(x) = [x^{2p}] \sum_{k=0}^m {2x+2k\choose 2k+1} {n+m-k-x-1/2\choose m-k} = 0$$

153. MSE 4713851: A sum with a zero value

$$\sum_{k=0}^n (-1)^k \frac{1}{m-k} {m-k\choose k} \frac{1}{m+2n-2k} {m+2n-2k\choose n-k} = 0$$

154. MSE 4722503: Euler numbers and Stirling numbers

$$E_{n} = 2^{2n-1} \sum_{\ell=1}^{n} \frac{(-1)^\ell}{\ell+1} {n\brace \ell} \left(3\left(\frac{1}{4}\right)^{\Large {\overline{\ell}}} - \left(\frac{3}{4}\right)^{\Large {\overline{\ell}}}\right)$$ $$E_{2n} = -4^{2n} \sum_{\ell=1}^{2n} \frac{(-1)^\ell}{\ell+1} {2n\brace \ell} \left(\frac{3}{4}\right)^{\Large {\overline{\ell}}}$$

155. MSE 495371: Even-index binomial coefficient convolution

$$\sum_{j=k}^{\lfloor n/2\rfloor} {n\choose 2j} {j\choose k} = \frac{1}{2} \frac{n}{n-k} 2^{n-2k} {n-k\choose k}$$

156. MSE 4731417: Kravchuk polynomials

$$\begin{align*} K_k & = \sum_{j=0}^k (-q)^j (q-1)^{k-j} {n-j\choose k-j} {X\choose j} \\ K_k & = \sum_{j=0}^k (-1)^j q^{k-j} {n-k+j\choose j} {n-X\choose k-j} \end{align*} $$

157. MSE 4762542: Binomial-Bernoulli convolution

$$\begin{align*} & \sum_{k=0}^{\lfloor (n-1)/2 \rfloor} \frac{1}{\alpha^{2k+1}} \frac{B_{2k+2}}{(n-2k)! (2k+2)!} \\ & = \frac{1}{2} \frac{n+2-2\alpha}{(n+2)!} + \frac{1}{\alpha^{n+1} (n+1)!} \sum_{j=0}^{\alpha-1} j^{n+1}. \end{align*}$$

158. MSE 4774167 : Two probabilities

$$\sum_{k=q}^n {k-1\choose q-1} p^q (1-p)^{k-q} = \sum_{k=q}^n {n\choose k} p^k (1-p)^{n-k}$$

159. MSE 4791957 : Motzkin numbers

$$a_{n+2} = a_{n+1} + \sum_{k=0}^n a_k a_{n-k} \Longrightarrow a_n = \sum_{k=0}^{\lfloor n/2 \rfloor} \frac{1}{k+1} {2k\choose k} {n\choose 2k}$$

160. MSE 4821034 : An inverse binomial coefficient

$$\sum_{q=0}^n {n\choose q} \frac{q}{q+1} {2n\choose q+1}^{-1} = \frac{1}{n+1}$$

161. MSE 4830342 : Euler numbers, Stirling numbers and Touchard polynomials

$$E_n = -\sqrt{2} \;\sum_{k=0}^n {n\brace k} \frac{k!}{\sqrt{2}^k} \cos(3\pi (k+1)/4) = 2 \int_0^\infty \exp(-t) \cos(t) T_n(-t) \; dt$$

162. MSE 4832009 : A triple binomial

$$\sum_{k=j}^{\lfloor n/2\rfloor} \frac{1}{4^k} {n\choose 2k} {k\choose j} {2k\choose k} = \frac{1}{2^n} {2n-2j\choose n-j} {n-j\choose j}$$

163. MSE 4843051 : Double sum with an absolute value

$$\sum_{p=0}^{n-1} \sum_{q=0}^n |n-p-q| {n+p-q\choose p} {n-p+q-1\choose q} = n 4^{n-1}$$

164. MSE 4850609 :Inverse central binomial coefficient in sum

$$\sum_{k=0}^n {n\choose k} {n+r\choose k} {2n\choose 2k}^{-1} = 4^n {2n\choose n}^{-1} \sum_{p=0}^{r-1} {r-1\choose p} {2p\choose p} 4^{-p} {n+1/2\choose n-p}$$

Computer search II

• OEIS A122366

  $${2 n - p \choose m - p} = (-1)^{n+m+p} \sum_{k=0}^n {2 n + 1\choose k} (-1)^k {2 n - k\choose n} {m - k\choose m - p}$$

• OEIS A100100

  $${n-m-1\choose p} = (-1)^{m+1} \sum_{k=0}^n (-1)^k {m-1+k\choose k}^2 {n+m\choose m+k} {n-1+k\choose p}$$

• OEIS A010854

  $${4p-2\choose p} = (-1)^m \sum_{k=0}^n {n+p\choose k+p} (-1)^k {k+p-1\choose k+p-m} {2k+1-p\choose p}$$

• OEIS A001498

  $$\frac{(n+m)!}{2^m (n-m)! m!} = (-1)^n \sum_{k=0}^n (-1)^k {n + m\choose m + k} {n - m + k\choose k} {m + k + 1\brace k + 1}$$

• OEIS A178300

  $${n + m - 1 - p\choose n - 1} = (-1)^{n+p+1} \sum_{k=0}^n {m - k\choose p - k} (-1)^k {2 m\choose k - n + m} {-n + k\choose m}$$

• OEIS A052553

  $${n-m-p \choose m} = \sum_{k=0}^n (-1)^k {p+m\choose p+k} {n-m+k\choose m} {p-1+k\choose k}$$

• OEIS A114607

  $$(2n+1)^p = (-1)^{n+m} \sum_{k=0}^n {2n\choose k-1} {2n-k\choose n-m-k} (-1)^k k^p$$

• OEIS A000984

  $${2p\choose p} = \sum_{k=0}^n (-1)^k {2p\choose k} {m-k+p\choose p} {n+p-k\choose p}$$

• OEIS A101688

  $$1 = (-1)^{n+m+p+1} \sum_{k=0}^{m-p} (-1)^k {m-1+k\choose n-1} {m-1+k\choose p-1} {2m-p\choose m-p-k}$$

• OEIS A008459

  $${n-1\choose p-1}^2 = (-1)^m \sum_{k=0}^n {p-1+k\choose k} (-1)^k {n-1+k\choose m} {2n\choose n+k} {k+n-p\choose k}$$

• OEIS A053126

  $${2n-1\choose p} = (-1)^{m+p} \sum_{k=0}^n {n-1+k\choose k} (-1)^k {n-1+k\choose m} {2n\choose n+k} {2k+p\choose p}$$

• OEIS A356546

  $${2n\choose n} {n\choose m} = \sum_{k=0}^n {n+1\choose 2k+1} {n+k\choose m+k} {m+k\choose m}$$

• OEIS A370232

  $${n+m\choose 2m}^2 = (-1)^n \sum_{k=0}^n {n+k\choose n-k} {2k\choose 2m} {2k-2m\choose k-m} (-1)^k$$

• OEIS A046899

  $${n+m\choose m} = (-1)^n \sum_{k=0}^n (-1)^k {n+k\choose n} {n+m\choose m+k} {p+k\choose m}$$

• OEIS A094527

  $${2n\choose n+m} = \sum_{k=0}^n (-1)^k {n-m+k\choose k} {2n-k\choose n-m-k} {2n\choose n+m-k}$$

• OEIS A008459

  $${n\choose m}^2 = (-1)^m \sum_{k=0}^n (-1)^k {k\choose m} {2n-k\choose k} {2n-2k\choose n-k}$$

• OEIS A123970

  $${n+m\choose 2m} = (-1)^m \sum_{k=0}^n {n+m\choose m+k} (-1)^k {p-k\choose n-m} {2m+k\choose k}$$

• OEIS A013609

  $${n\choose m} 2^m = (-1)^m \sum_{k=0}^n {n\choose k} (-1)^k {2k\choose m} {p-k\choose n-m}$$

• OEIS A001813

  $$\frac{(2p)!}{p!} = (-1)^{p+m} \sum_{k=0}^{p+m} (n-k)^p (-1)^k {2p\choose p+m-k} {r-k\choose p}$$

• OEIS A043302

  $$2^{n-2m} \frac{(n+m)!}{(n-m)! m!} = (-1)^m \sum_{k=0}^n {n+m\choose m+k} (-1)^k {p-2k\choose n-m} {m+k+1\brace k+1}$$

• OEIS A059304

  $$2^p {2p\choose p} = (-1)^m \sum_{k=0}^n {n-k+p\choose p} (-1)^k {2k\choose p} {2p\choose m-k+p}$$

• OEIS A079901

  $$n^m = (-1)^m \sum_{k=0}^n {n-1+k\choose k} (-1)^k k^m {2n\choose n+k}$$

• OEIS A090181

  $${n\choose m} {n-1\choose n-m} \frac{1}{n-m+1} = (-1)^{n+m} \sum_{k=0}^n \frac{1}{k+1} {2k\choose k} (-1)^k {n-k\choose m} {n+k\choose n-k}$$

• OEIS A128908

  $${y-x\choose n} = (-1)^n \sum_{k=0}^{n} {x-k\choose n-k} {x+1\choose k} (-1)^k {y+1-k\choose n}$$

• OEIS A088617

  $${n+m\choose n} {n\choose m} \frac{1}{m+1} = (-1)^n \sum_{k=0}^n (-1)^k \frac{1}{k+1} {2k\choose k} {k+1\choose m+1} {n+k\choose n-k}$$

• OEIS A090802

  $${n\choose m} m! q^{n-m} = \sum_{k=0}^n {n\choose k} (-1)^k {p-qk\choose n-m} (r-k)^m$$

• OEIS A013620

  $$p^{n-m} q^m {n\choose m} = (-1)^m \sum_{k=0}^n {n\choose k} (-1)^k {x-pk\choose n-m} {y+qk\choose m}$$

• OEIS A000332

  $${n-1\choose m-1} = (-1)^{m+1} \sum_{k=0}^n {2n\choose n+k} (-1)^k {m-1+k\choose k} {n-1+k\choose k}$$

• OEIS A370232

  $${n+m\choose 2m}^2 = (-1)^n \sum_{k=0}^n {n+k\choose 2k} {2k\choose m+k} (-1)^k {k+m\choose k-m}$$

• OEIS A002299

  $${2m-1\choose p} = (-1)^{p+1} \sum_{k=0}^n {n+m\choose m+k} (-1)^k {m-1+k\choose m} {k-m+p\choose p}$$

• OEIS A135278

  $${n\choose m} = (-1)^{m+p} \sum_{k=0}^{n-p} (-1)^k {n\choose p+k} {x-k\choose n-m} {m+k\choose k}$$

• OEIS A076112

  $$(n+1)^m = (-1)^{n+m} \sum_{k=0}^n (-1)^k {2n-k\choose n} {2n+1\choose k} (n-k)^m$$

• OEIS A367270

  $${n\choose m} {n-1\choose m} = (-1)^{n+1} \sum_{k=0}^n {2n\choose n+k} (-1)^k {n+k-m-1\choose n-m-1} {m-1+k\choose m} {n-1+k\choose n-1}$$

• OEIS A001725

  $$\frac{(n+m)!}{n!} = (-1)^n \sum_{k=0}^n (r+k)^m {n+k\choose n} (-1)^k {n+m\choose m+k}$$

• OEIS A094305

  $$\frac{(n+p)!}{2^p (n-p)! p!} {n-p\choose m-p} = (-1)^m \sum_{k=0}^m {n-k\choose m-k} (-1)^k {p+k+1\brace k+1} {m+k\choose p+k} {p+n\choose p+k}$$

• OEIS A143219

  $${n-1\choose p-1} {m\choose p} = (-1)^p \sum_{k=0}^n (-1)^k {n+1\choose k+1} {n+k\choose p+k} {k-m+p\choose p}$$

• OEIS A033918

  $$m^m = (-1)^n \sum_{k=0}^n {n+m\choose m+k} (-1)^k k^m {m-1+k\choose m-n+k}$$

• OEIS A000984

  $${2p\choose p} = (-1)^{m+p} \sum_{k=0}^n {n-k+p\choose p} {m-k\choose p} (-1)^k {2p\choose k-m+p}$$

165. MSE 4902676: Inverse central binomial coefficient

     $$\frac{2^{4n}}{2n+1} {2n\choose n}^{-1} = \sum_{m=0}^n \frac{1}{2m+1} {2m\choose m} {2n-2m\choose n-m}$$

166. MSE 4906245: Another inverse binomial coefficient

     $$\frac{1}{q} {n\choose k} = \sum_{p=0}^k (-1)^p {q-1-n+k\choose p} {n+1\choose k-p} \frac{1}{p+1} {q+k\choose p+1}^{-1}$$

Part 3

Egorychev method in complex variables

1. Introductory example for the method

   $$\sum_{k=0}^n (-1)^k {n\choose k} {n+k\choose k} {k\choose j} = (-1)^n {n\choose j} {n+j\choose j}$$

2. Introductory example for the method, convergence about zero

   $$\sum_{k=0}^r {r-k\choose m} {s+k\choose n} = {s+r+1\choose n+m+1}$$

3. Introductory example for the method, an interesting substitution

   $$\sum_{q=0}^{2m} (-1)^q {p-1+q\choose q} {2m+2p+q-1\choose 2m-q} 2^q = (-1)^m {p-1+m\choose m}$$

4. Introductory example for the method, another interesting substitution

   $$\sum_{k=0}^{\lfloor m/2\rfloor} {n\choose k} (-1)^k {m-2k+n-1\choose n-1} = {n\choose m}$$

5. Introductory example for the method, yet another interesting substitution

   $$\sum_{k=0}^n k{2n\choose n+k} = \frac{1}{2} n {2n\choose n}$$

6. Using an Iverson bracket only

   $$\sum_{k=0}^n 2^{-k} {n+k\choose k} = 2^n$$

7. Verifying that a certain sum vanishes

   $$\sum_{m=0}^n {n\choose m} \sum_{k=0}^{n+1} \frac{1}{a+bk+1} {a+bk\choose m} {k-n-1\choose k} = {n\choose m}$$

8. A case of radical cancellation

   $$\sum_{k=0}^n {2n+1\choose 2k+1} {m+k\choose 2n} = {2m\choose 2n}$$

9. Basic usage of exponentiation integral

   $$(-1)^p \sum_{q=r}^p {p\choose q} {q\choose r} (-1)^q q^{p-r} = \frac{p!}{r!}$$

10. Introductory example for the method, eliminating odd-even dependence

    $$\sum_{k=0}^n {n\choose k} 2^{n-k} {k\choose \lfloor k/2\rfloor} = {2n+1\choose n}$$

11. Introductory example for the method, proving equality of two double hypergeometrics

    Verify that $f_1(n,k) = f_2(n,k)$ where $$f_1(n,k) = \sum_{v=0}^n \frac{(2k+2v)!}{(k+v)! \times v! \times (2k+v)!\times (n-v)!} 2^{-v}$$ and $$f_2(n,k) = \sum_{m=0}^{\lfloor n/2\rfloor} \frac{1}{(k+m)!\times m!\times (n-2m)!} 2^{n-4m}$$

12. A remarkable case of factorization

    If $$T(n) = \sum_{k=1}^{\lfloor n/2\rfloor} (-1)^{k+1} {n-k\choose k} T(n-k)$$ for $n\ge 2$ then $$T_n = C_{n-1} = \frac{1}{n} {2n-2\choose n-1}$$

13. Evaluating a quadruple hypergeometric

    $$\sum_{k=0}^n \sum_{l=0}^n (-1)^{k+l} {n+k-l\choose n} {k+l\choose n} {n\choose k} {n\choose l} = (-1)^m {2m\choose m}$$

14. An integral representation of a binomial coefficient involving the floor function

    $$\sum_{k=0}^{2m+1} {n\choose k} 2^k {n-k\choose \lfloor (2m+1-k)/2\rfloor} = {2n+1\choose 2m+1}$$

15. Evaluating another quadruple hypergeometric

    $$\sum_{k=m}^n (-1)^{n+k} \frac{2k+1\choose n+k+1} {n\choose k} {n+k\choose k}^{-1} {k\choose m} {k+m\choose m} = \delta_{mn}$$

16. An identity by Strehl

    $$\sum_{k=0}^n {n\choose k}^3 = \sum_{k=\lceil n/2\rceil}^n {n\choose k}^2 {2k\choose n}$$

17. Shifting the index variable and applying Leibniz' rule

    $$ \sum_s {n+s\choose k+l} {k\choose s} {l\choose s} = {n\choose k} {n\choose l}$$

18. Working with negative indices

    $$\sum_{-\lfloor n/3\rfloor}^{\lfloor n/3\rfloor} (-1)^k {2n\choose n+3k} = 2\times 3^{n-1}$$

19. Two companion identities by Gould

    $$\sum_{k=0}^\rho {2x+1\choose 2k} {x-k\choose \rho-k} = \frac{2x+1}{2\rho+1} {x+\rho\choose 2\rho} 2^{2\rho}$$

20. Exercise 1.3 from Stanley's Enumerative Combinatorics

    $$\sum_{k=0}^{\min(a,b)} {x+y+k\choose k} {x\choose b-k} {y\choose a-k} = {x+a\choose b} {y+b\choose a}$$

21. Counting m-subsets

    $$\sum_{q=0}^n {n\choose 2q} {n-2q\choose p-q} 2^{2q} = {2n\choose 2p}$$

22. Method applied to an iterated sum

    $$\sum_{k=0}^{n-1} \left(\sum_{q=0}^k {n\choose q}\right) \left(\sum_{q=k+1}^n {n\choose q}\right) = \frac{1}{2} n {2n\choose n}$$

23. A pair of two double hypergeometrics

    $$(1-x)^{2k+1} \sum_{n\ge 0} {n+k-1\choose k} {n+k\choose k} x^n = \sum_{j\ge 0} {k-1\choose j-1} {k+1\choose j} x^j$$

24. A two phase application of the method

    $$\sum_{k=0}^{\lfloor n/3\rfloor} (-1)^k {n+1\choose k} {2n-3k\choose n} = \sum_{k=\lfloor n/2\rfloor}^n {n+1\choose k} {k\choose n-k}$$

25. An identity from Mathematical Reflections

    $$\sum_{k=0}^{\lfloor (m+n)/2 \rfloor} {n\choose k} (-1)^k {m+n-2k\choose n-1} = {n\choose m+1}$$

26. A triple Fibonacci-binomial coefficient convolution

    $$\sum_{k=0}^n {n\choose k} {n+k\choose k} F_{k+1} = \sum_{k=0}^n {n\choose k} {n+k\choose k} (-1)^{n-k} F_{2k+1}$$

27. Fibonacci numbers and the residue at infinity

    $$\sum_{p,q\ge 0} {n-p\choose q} {n-q\choose p} = F_{2n+2}$$

28. Permutations containing a given subsequence

    $$\sum_{r=0}^n {r+n-1\choose n-1} {3n-r\choose n} = \frac{1}{2} \left( {4n\choose 2n} + {2n\choose n}^2\right)$$

29. An example of Lagrange inversion

    $$[x^\mu y^\nu] \frac{1}{2} (1-x-y-\sqrt{1-2x-2y-2xy+x^2+y^2}) = \frac{1}{\mu+\nu-1} {\mu+\nu-1\choose \nu} {\mu+\nu-1\choose \mu}$$

30. A binomial coefficient - Catalan number convolution

    $$\sum_{r=1}^{n+1} \frac{1}{r+1} {2r\choose r} {m+n-2r\choose n+1-r} = {m+n\choose n}$$

31. A new obstacle from Concrete Mathematics

    $$\sum_{k\ge 0} {n+k\choose m+2k} {2k\choose k} \frac{(-1)^k}{k+1} = {n-1\choose m-1}$$

32. Abel-Aigner identity from Table 202 of Concrete Mathematics

    $$\sum_k {tk+r\choose k} {tn-tk+s\choose n-k} \frac{r}{tk+r} = {tn+r+s\choose n}$$

33. Reducing the form of a double hypergeometric

    $$\sum_{q=0}^{n-2} \sum_{k=1}^n {k+q\choose k} {2n-q-k-1\choose n-k+1} = n \times {2n\choose n+2}$$

34. Basic usage of the Iverson bracket

    $$\sum_{q=0}^l {q+k\choose k} {l-q\choose k} = {l+k+1\choose 2k+1}$$

35. Basic usage of the Iverson bracket II

    $$\sum_{k=0}^n k {m+k\choose m+1} = \frac{nm+2n+1}{m+3} {n+m+1\choose m+2}$$

36. Use of a double Iverson bracket

    $$\sum_{k=1}^n 2^{n-k} {k\choose\lfloor k/2\rfloor} = -2^{n+1} + (2n+2+(n\mod 2)) {n\choose \lfloor n/2 \rfloor}$$

37. Iverson bracket and an identity by Gosper, generalized

    $$\sum_{q=0}^{m-1} {n-1+q\choose q} x^n (1-x)^q + \sum_{q=0}^{n-1} {m-1+q\choose q} x^q (1-x)^m = 1$$

38. Factoring a triple hypergeometric sum

    $$\sum_{k=0}^n (-1)^k {p+q+1\choose k} {p+n-k\choose n-k} {q+n-k\choose n-k} = {p\choose n} {q\choose n}$$

39. Factoring a triple hypergeometric sum II

    $$\sum_{k=0}^n {n\choose k} {pn-n\choose k} {pn+k\choose k} = {pn\choose n}^2$$

40. Factoring a triple hypergeometric sum III

    $$\sum_{r=0}^{\min(m,n,p)} {m\choose r} {n\choose r} {p+m+n-r\choose m+n} = {p+m\choose m} {p+n\choose n}$$

41. A triple hypergeometric sum IV

    $$\sum_{p=0}^l \sum_{q=0}^p (-1)^q {m-p\choose m-l} {n\choose q} {m-n\choose p-q} = 2^l {m-n\choose l}$$

42. Basic usage of exponentiation integral to obtain Stirling number formulae

    $$\sum_{q=0}^n (n-2q)^k {n\choose 2q+1} = \sum_{q=0}^{k+1} {n\choose q} 2^{n-q-1}\times q!\times {k+1\brace q+1} - \frac{1}{2}\times n!\times {k+1\brace n+1}$$

43. Three phase application including Leibniz' rule

    $$\sum_{q=0}^n q {2n\choose n+q} {m+q-1\choose 2m-1} = m \times 4^{n-m} \times {n\choose m}$$

44. Symmetry of the Euler-Frobenius coefficient

    With $$b_k^n = \sum_{l=1}^k (-1)^{k-l} l^n {n+1\choose k-l}$$ we show that $b_k^n = b_{n+1-k}^n$ where $0\le k\le n+1.$

45. A probability distribution with two parameters

    We have a random variable $X$ where $$\mathrm{P}[X=k] = {N\choose 2n+1}^{-1} {N-k\choose n} {k-1\choose n}$$ for $k=n+1,\ldots, N-n$ and zero otherwise. We show that these probabilities sum to one and compute the mean and the variance.

46. An identity involving Narayana numbers

    The Narayana number is $$N(n,m) = \frac{1}{n} {n\choose m} {n\choose m-1}$$ and we introduce $$A(n,k,l) = \sum_{i_0+i_1+\cdots+i_k=n \atop j_0+j_1+\cdots+j_k=l} \prod_{t=0}^k N(i_t, j_t+1)$$ where the compositions for $n$ are regular and the ones for $l$ are weak. We seek to verify that $$A(n,k,l) = \frac{k+1}{n} {n\choose l} {n\choose l+k+1}.$$

47. Convolution of Narayana polynomials

    Same as previous, generalized.

48. A property of Legendre polynomials

    $$ (-1)^m \frac{(n+m)!}{(n-m)!} \left(\frac{d}{dz}\right)^{n-m} (1-z^2)^n = (1-z^2)^m \left(\frac{d}{dz}\right)^{n+m} (1-z^2)^n$$

49. A sum of factorials, OGF and EGF of the Stirling numbers of the second kind

    $$r^k (r+n)! = \sum_{m=0}^k (r+n+m)! (-1)^{k+m} \sum_{p=0}^{k-m} {k\choose p} {k+1-p\brace m+1} n^p$$

50. Fibonacci, Tribonacci, Tetranacci

    $$\sum_{k=0}^n \sum_{q=0}^k (-1)^q {k\choose q} {n-1-qm\choose k-1} = [z^n] \frac{1}{1-w-w^2-\cdots-w^m}$$

51. Stirling numbers of two kinds, binomial coefficients

    $${n\brace m} = \sum_{k=m}^n {k\choose m} \sum_{q=0}^k (-1)^{n} {n+q-m\brace k} (-1)^{k} {k\brack q} {n\choose n+q-m}$$

52. An identity involving involving two binomial coefficients and a fractional term

    $$\sum_{k=0}^m \frac{q}{pk+q} {pk+q\choose k} {pm-pk\choose m-k} = {mp+q\choose m}$$

53. Double chain of a total of three integrals

    $$\sum_{k=q}^{n-1} \frac{q}{k} {2n-2k-2\choose n-k-1} {2k-q-1\choose k-1} = {2n-q-2\choose n-1}$$

54. Rothe-Hagen identity

    $$\sum_{k=0}^n \frac{x}{x+kz} {x+kz\choose k} \frac{y}{y+(n-k)z} {y+(n-k)z\choose n-k} = \frac{x+y\choose x+y+nz} {x+y+nz\choose n} $$

55. Abel polynomials are of binomial type

    We have $$P_n(x+y) = \sum_{k=0}^n P_k(x) P_{n-k}(y)$$ where $$P_n(x) = x(x+an)^{n-1}$$ is an Abel polynomial.

56. A summation identity with four poles

    $$\sum_{m=0}^n (-1)^m {2n+2m\choose n+m} {n+m\choose n-m} = (-1)^n 2^{2n} $$

57. A summation identity over odd indices with a branch cut

    $$\sum_{k=0 \atop k\,\mathrm{odd}}^m {2n\choose 2n-k} {2m-2n\choose m-k} = \frac{1}{2} {2m\choose m} + (-1)^{m 1} 2^{2m-1} {n-1/2\choose m}$$

58. A Stirling-number identity

    $$\sum_{j=0}^n (-1)^{n+j} {n\brack j} {m+j\brace k} = \frac{n!}{k!} \sum_{q=0}^k {k\choose q} {q\choose n} (-1)^{k-q} q^m$$

59. A Catalan-Central binomial coefficient convolution

    $$[z^k] \frac{1}{\sqrt{1-4z}} \left(\frac{1-\sqrt{1-4z}}{2z}\right)^n = {n+2k\choose k}$$

Post Scriptum sections

1. A trigonometric sum

   $$\sum_{k=1}^{m-1} \sin^{2q}(k\pi/m) = m\frac{1}{2^{2q}} {2q\choose q} + m \frac{1}{2^{2q-1}} \sum_{l=1}^{\lfloor q/m \rfloor} {2q\choose q-lm} (-1)^{lm}$$

2. A class of polynomials similar to Fibonacci and Lucas Polynomials

   The binomial coefficient sum $$\sum_{j=-\lfloor n/p\rfloor}^{\lfloor n/p\rfloor} (-1)^j {2n\choose n-pj}$$ is given by $$[z^n] \left(\sum_{q=0}^{\lfloor p/2\rfloor} \frac{p}{p-q} {p-q\choose q} (-1)^q z^q\right)^{-1} \sum_{q=0}^{\lfloor (p-1)/2\rfloor} {p-1-q\choose q} (-1)^q z^q$$

3. Partial row sums in Pascal's triangle

   $$\sum_{k=0}^n {2k+1\choose k} {m-(2k+1)\choose n-k} = \sum_{k=0}^n {m+1\choose k}$$

4. The tree function and Eulerian numbers of the second order

   $$\sum_{m\ge 0} m^{m+n} \frac{z^m}{m!} = \frac{1}{(1-T(z))^{2n+1}} \sum_{k=0}^n \left\langle\!\!\left\langle {n\atop k} \right\rangle\!\!\right\rangle T(z)^k$$

5. A Stirling set number generating function and Eulerian numbers of the second order

   $$\sum_{n\ge 0} {n+r\brace n} z^n = \frac{1}{(1-z)^{2r+1}} \sum_{k=0}^r \left\langle\!\!\left\langle {r\atop k} \right\rangle\!\!\right\rangle z^k$$

   A Stirling cycle number generating function and Eulerian numbers of the second order (II)

   $$\sum_{n\ge 0} {n+r+1\brack n+1} z^{n} = \frac{1}{(1-z)^{2r+1}} \sum_{k=0}^r \left\langle\!\!\left\langle {r\atop r-k} \right\rangle\!\!\right\rangle z^k$$

6. Another case of factorization

   $${q-j+k\choose k} + (-1)^k {j\choose k} = \sum_{\ell=0}^{\lfloor k/2\rfloor} {q/2+\ell\choose 2\ell} \left({q/2-j+k-\ell\choose k-2\ell} + {q/2-j+k-\ell-1\choose k-2\ell} \right)$$

7. An additional case of factorization

   $$\sum_{j=0}^k {2j\choose j+q} {2k-2j\choose k-j} = 4^k - \sum_{j=k-q+1}^k {2k+1\choose j}$$

8. Contours and a binomial square root

   $$\sum_{k=0}^n {2n+1\choose 2k+1} {m+k\choose 2n} = {2m\choose 2n}$$

9. A careful examination of contours

   $$\sum_{q=0}^n {q\choose n-q} (-1)^{n-q} {2q+1\choose q+1} = 2^{n+1}-1$$

10. Stirling numbers, Bernoulli numbers and Catalan numbers from Concrete Mathematics by Graham, Knuth and Patashnik

    $$\sum_{k=0}^n {n+k\brace k} {2n\choose n+k} \frac{(-1)^k}{k+1} = B_n {2n\choose n} \frac{1}{n+1}$$

11. Transforming an OGF into an EGF

    With $f(z)$ the OGF and $g(w)$ the EGF of a sequence we have $$g(w) = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{f(z)}{z} \exp(w/z) \; dz.$$

12. Stirling numbers of the first and second kind

    $$\sum_{q=0}^r (-1)^{q+r} {r\brack q} {n+q-1\brace k} = \frac{(-1)^{k-r}}{(k-r)!} \sum_{p=0}^{k-r} {k-r\choose p} (-1)^p (p+r)^{n-1} $$

13. An identity by Carlitz

    $$\sum_{k=0}^n {n\choose k} {k/2\choose m} = \frac{n}{m} {n-m-1\choose m-1} 2^{n-2m}$$

14. Logarithm of the Catalan number OGF

    $$[z^n] \log^2 \frac{2}{1+\sqrt{1-4z}} = {2n\choose n} (H_{2n-1}-H_n) \frac{1}{n}$$

15. A Bernoulli / Stirling number identity

    $$\sum_{k=0}^n {n+1\brack k+1} B_k = \frac{n!}{n+1}$$

16. Formal power series vs contour integration

    $$\sum_{q=0}^K (-1)^q {2n+1-q\choose q} {2n-2q\choose K-q} = \frac{1}{2} (1+(-1)^K)$$