Combinatorial numbers and Egorychev method (MathJax)

These are binomial coefficients, Stirling numbers, Catalan numbers, Harmonic numbers, Eulerian numbers and Bernoulli numbers, as in the book Integral representation and the Computation of Combinatorial Sums by G. P. Egorychev.

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

and here (part 3, complex variables) This includes a number of identities from H.W. Gould's book Combinatorial identities as well as L. Saalschütz's book on Bernoulli numbers.

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}$$

also featuring Narayana and Catalan numbers. These computer identities have ranges of validity (boundary conditions) which are documented in the text. These are in chronological order so that the most recent work is at the end.

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.

My home page is here. There is a no MathJax version of these formulas if they are not being displayed, it uses images and can be found here.
This is the list of identities in the above document, typeset with MathJax, including links to the posts where they first appeared.

Part 1 and 2

Egorychev method in formal power series

  1. MSE 2384932

    2. $$\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

    3. $$\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

    4. $$\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

    5. $$\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

    6. $$\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

    7. $$(-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

    8. $${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

    9. $$\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

    10. $$\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

    11. $$\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

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

  12. MSE 3245099

    13. $$\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

    14. $${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

    15. $$\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

    16. $$\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

    17. $$\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

    18. $$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

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

  19. MSE 3577193

    20. $$\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

    21. $$\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

    22. $$\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

    23. $$\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

    24. $$\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

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

  25. MSE 3661349

    26. $$\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

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

  27. MSE 3737197

    28. $$\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

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

  29. MSE 3845061

    30. $$\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

    31. $$\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

    32. 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

    33. $$\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

    34. $$\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

    35. $$\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

    36. $$\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

    37. $$\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)

    38. $${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)

    39. 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)

    40. 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)

    41. $${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

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

  42. MSE 4054024

    43. $$\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

    44. $$\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

    45. $$\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

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

  46. MSE 4127695

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

  47. MSE 4131219

    48. 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

    49. $$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

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

  50. MSE 4212878

    51. $$\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

    52. $$\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)

    53. $$\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

    54. $${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

    55. $${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

    56. $${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

    57. $$\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

    58. $$\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

    59. $$\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

    60. $$\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

    61. $$\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

    62. $$\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

    63. $$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

    64. $$\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

    65. $$\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

    66. $$\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

    67. $$\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

    68. $$\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

    69. $$\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

    70. $$\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

    71. $$\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

    72. $$\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

    73. $$\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

    74. $$\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

    75. $$\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

    76. $$\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

    77. $$\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

    78. $$\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

    79. $$\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

    80. $$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

    81. $$\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

    82. $$\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

    83. $$\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

    84. $$\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

    85. $$\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

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

  86. Very basic example

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

  87. Very basic example II

    88. $$\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

    89. $$\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

    90. $$\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

    91. $$\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

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

  92. Legendre Polynomials

    93. $$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

    94. $$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

    95. $$\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

    96. $$\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

    97. $$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

    98. $$\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

    99. $$\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

    100. $$\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

    101. $$[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

    102. $$\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

    103. $$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

    104. $$\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

    105. $$\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

    106. $$\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

    107. $$\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

    108. $$\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

    109. $$\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

    110. $$\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.

    111. $$\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.

    112. $$\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

    113. $$\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

    114. $$\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

    115. $$\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

    116. $$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

    117. $$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

    118. $$\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

    119. $$(-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

    120. $$\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

    121. $$\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

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

  122. Free functional term

    123. $$\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

    124. $$\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

    125. $$\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

    126. $$\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

    127. $$\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

    128. $$\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

    129. $$\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

    130. $${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

    131. $$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

    132. $${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

    133. $$\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

    134. $$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

    135. $$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

    136. $$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

    137. $$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

  1. Worpitzky's identity

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

  2. MSE 4627726: Quadruple binomial coefficient

    3. $$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}$$

  3. MSE 4627918: Alternating power sum

    4. $$\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}$$

  4. MSE 4227433: Squared power sum

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

  5. MSE 4428892: Ordinary power sum

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

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

    7. $$\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}$$

  7. MSE 4641290: A vanishing variable

    8. $$\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$$

  8. MSE 4644963: From trigonometric to rational

    9. $$\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}}$$

  9. MSE 4657112: Triple combinatorial numbers to constant

    10. $$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

  1. MSE 4667102: Two different representations of a coefficient

    2. $$\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}$$

  2. MSE 4675665: Rational term of constant degree

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

  3. MSE 4666141: Double square root

    4. $$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$$

  4. MSE 4699857: Four auxiliary variables

    5. $${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}$$

  5. MSE 4703564: A family of odd polynomials

    6. $$[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$$

  6. MSE 4713851: A sum with a zero value

    7. $$\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$$

  7. MSE 4722503: Euler numbers and Stirling numbers

    8. $$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}}}$$

  8. MSE 495371: Even-index binomial coefficient convolution

    9. $$\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}$$

  9. MSE 4731417: Kravchuk polynomials

    10. $$\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*} $$

  10. MSE 4762542: Binomial-Bernoulli convolution

    11. $$\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*}$$

  11. MSE 4774167 : Two probabilities

    12. $$\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}$$

  12. MSE 4791957 : Motzkin numbers

    13. $$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}$$

  13. MSE 4821034 : An inverse binomial coefficient

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

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

    15. $$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$$

  15. MSE 4832009 : A triple binomial

    16. $$\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}$$

  16. MSE 4843051 : Double sum with an absolute value

    17. $$\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}$$

  17. MSE 4850609 :Inverse central binomial coefficient in sum

    18. $$\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

  1. 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}$$

  2. 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}$$

  3. Quadruple hypergeometric with an inverse binomial coefficient

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

  4. Quadruple hypergeometric with two inverse binomial coefficients

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

  5. MSE 4949815: Inverse binomial coefficient with harmonic numbers

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

  6. MSE 4960823: Binomial coefficient scaled power sum

    $$\sum_{k=0}^n (-1)^{n-k} {n\choose k} k^{n+a} = (n+a)! \sum_{q=1}^a {n\choose q} [z^{a+q}] (\exp(z)-z-1)^q$$

  7. MSE 4964157: Two central binomial coefficients and a fractional term

    $$\sum_{k=0}^n \frac{1}{ak+b} {2k\choose k} {2n-2k\choose n-k} = \frac{4^n}{b} \prod_{k=1}^n \frac{ak+b-a/2}{ak+b}$$

  8. MSE 4976413: Riordan number asymptotics from central trinomial coefficients

    $$\sum_{q\ge 0} {n\choose q} {n-q\choose q} - \sum_{q\ge 0} {n\choose q+1} {n-q-1\choose q} = -\frac{1}{2} [v^{n+1}] \sqrt{\frac{1-3v}{1+v}}$$

  9. MSE 4980771: Polynomials and the residue at infinity

    $$\sum_{k=1}^n x_k \prod_{q=1, q\ne k}^n \frac{x_k+yx_q}{x_k-x_q} = \sum_{k=1}^n x_k$$

  10. MSE 4980771: Kravchuk polynomial and Vandermonde convolution

    $$\sum_{q=0}^n \mathcal{K}_q(m_0;n) \mathcal{K}_q(m_1;n) = (-1)^{\Delta^-/2} \frac{\Delta^+!}{(\Delta^+/2)!} \frac{(2n-\Delta^+)!}{(n-\Delta^+/2)!} \frac{1}{n!}$$

  11. MSE 5003960: A sum of a certain hypergeometric term

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

  12. MSE 5010757: Triple hypergeometric with two square root terms

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

  13. MSE 4989609: An inverse binomial coefficient

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

  14. Both types of Stirling numbers and the logarithm identity

    15. $${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}$$

  15. MSE 5030526: A triple sum identity

    $$\begin{align*} & v_j = \sum_{m=j}^k (-1)^{k-m} {k+m\choose 2m} {m\choose j}\\ & -\frac{1}{2} j(j-1) v_{j-1} + j(j-1)v_j + \frac{3}{2} j(j+1) v_{j+1} = - \frac{1}{2} k(k+1) v_{j-1} \\ \end{align*}$$

  16. A triple hypergeometric and the logarithm identity

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

  17. MSE 5030526: An iterated sum identity

    $$\delta_{m,j} (1+P)^n = \sum_{r=0}^n \sum_{a=0}^m \sum_{b=0}^r {n-m\choose r-m+a} {m\choose a} {n-r\choose j-r+b} {r\choose b} (-1)^{a+b+j-r} P^{a+b}$$

  18. MSE 5041394: Recurrence for a triple hypergeometric

    $$Q(n;a,b) = \sum_{p=0}^a \sum_{q=0}^b {p+q\choose p} {n-p-q\choose a-p} {n-p-q\choose b-q}$$ $$Q(n; a,b) = {n\choose a} {n\choose b} + Q(n-1; a-1,b) + Q(n-1; a,b-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)$$

  17. A sum of the derivatives of inverse powers

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

  18. Shifted central binomial coefficient convolution

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

Computer search III