SOME IDENTITIES THAT CAN BE PROVED USING MGFUN

1. Cassini’s identity on the Fibonacci numbers F_{n+2}F_{n} − F_{n+1}^{2} = (−1)^{n},

with F_{0} = F_{1} = 1 and F_{n+2} = F_{n+1} + F_{n}.

2. A double sum identity

∑_{i,j=0}^{∞} \binom{n}{i}\binom{n}{j}\binom{i + j}{i, j} = ∑_{n=0}^{∞} \binom{n}{i}^{2}4^{i}.

This identity was left to me by Philippe Flajolet as an exercise.

3. An identity between Franel and Apéry numbers

∑_{k=0}^{n} \binom{n}{k}^{2}\binom{n + k}{k}^{2} = ∑_{k=0}^{n} \binom{n}{k}\binom{n + k}{k} ∑_{j=0}^{k} \binom{k}{j}^{3}.

Several proofs of this identity were given in [6]. Both sides of this equation satisfy the equation

(n + 2)^{3}u_{n+2} − ((n + 2)^{3} + (n + 1)^{3} + 4(2n + 3)^{3}) u_{n+1} + (n + 1)^{3}u_{n}.

This operator was used by Apéry in his proof of the irrationality of ζ(3) = ∑_{k=1}^{∞} \frac{1}{k^{3}} .

4. Combinatorial sums with non-natural boundaries

The following examples were given in [7].

∑_{k=0}^{n} \binom{n + k}{k}2^{−k} = 2^{n},  ∑_{k=0}^{n} \frac{(2n − 2k)!(2k)!}{k!(k + 1)!(n − k)!^{2}} = \binom{2n + 1}{n}.

5. A challenging sum with non-natural boundaries

The following identity was suggested by William Steiger <steiger@cs.princeton.edu> as a challenge for CAS.

∑_{k=1}^{n−r} \frac{1}{k}\binom{n − k}{r} = \binom{n}{r} ∑_{k=r+1}^{n} \frac{1}{k}.

Both expressions are the probability that in a random permutation, 1 is the first element smaller than the minimum of the first r elements.

6. Generating function of the Jacobi polynomials

∑_{n=0}^{∞} P_{n}^{(a,b)}(x)y^{n} = \frac{1}{\sqrt{1 − 2yx + y^{2}} (1 − y + \sqrt{1 − 2yx + y^{2}})^{a} (1 + y + \sqrt{1 − 2yx + y^{2}})^{b}} ,

where P_{n}^{(a,b)}(x) are the Jacobi polynomials. [Here, Maple’s dsolve is not powerful enough to solve the differential equation found for the left-hand side, but the right-hand satisfies this equation with the right initial conditions.]

7. The Mehler formula for Hermite polynomials

∑_{n=0}^{∞} H_{n}(x)H_{n}(y)\frac{u^{n}}{n!} = \begin{matrix}exp & (\frac{4u(xy−u(x^{2}+y^{2}))}{1−4u^{2}}) \\ √ & \overline{1 − 4u^{2}} \end{matrix},

where H_{n}(x) are the Hermite polynomials. See [4] for a combinatorial proof or [1] for a WZbased proof.

8. Doetsch identity for Hermite polynomials

∫_{y=−∞}^{∞} \frac{(1 + xy + 2y^{2}) exp (\frac{x^{2}y^{2}}{1+2y^{2}} )}{y^{n+1}(1 + 2y^{2})^{\frac{3}{2}}}dx = H_{n}(x),

where H_{n}(x) are the Hermite polynomials. See [3] for a combinatorial proof or [1] for a WZbased proof.

9. A Rogers-Ramanujan identity

The following identity is a finite version due to Andrews of one of the famous Rogers-Ramanujan identities:

∑_{k} \frac{q^{k^{2}}}{(q; q)_{k}(q; q)_{n−k}} = ∑_{k} \frac{(−1)^{k}q^{(5k^{2}−k)/2}}{(q; q)_{n−k}(q; q)_{n+k}} .

10. Dixon’s identity and its q-analogue

∑_{k} (−1)^{k}\binom{a + b}{a + k}\binom{a + c}{c + k}\binom{b + c}{b + k} = \binom{a + b + c}{a, b, c},

and

∑_{k} (−1)^{k}q^{k(3k+1)/2}\binom{a + b}{a + k}_{q}\binom{a + c}{c + k}_{q}\binom{b + c}{b + k}_{q} = \frac{(q; q)_{a+b+c}}{(q; q)_{a}(q; q)_{b}(q; q)_{c}} .

11. A doubly infinite sum of Ramanujan’s

∑_{−∞}^{∞} \frac{(a; q)_{n}x^{n}}{(b; q)_{n}} = \frac{(ax; q)_{∞} (\frac{q}{ax}; q)_{∞} (q; q)_{∞} (\frac{b}{a}; q)_{∞}}{(x; q)_{∞} (\frac{b}{ax}; q)_{∞} (b; q)_{∞} (\frac{q}{a}; q)_{∞}} .

Here, we found a q recurrence equation for the left-hand side. Resolution would need an implementation of the q-Petkovšek algorithm in Maple, which is not available. However, the right-hand side satisfies this equation with the right initial conditions.

12. An identity between an exp-log integral and a harmonic sum

∫_{0}^{1} \frac{x ln^{2} x exp(−px)}{1 − x}dx = ∑_{n=0}^{∞} \frac{(−1)^{n+1}ψ′′(n + 1)p^{n}}{n!} − 2_{3}F_{3} ({1, 1, 1 \atop 2, 2, 2}; −p) ,

where ψ′′ denotes the second derivative of ψ(s) = \frac{Γ′(s)}{Γ(s)} and satisfies

−\frac{ψ′′(n + 1)}{2} = ∑_{k=n+1}^{∞} \frac{1}{k^{3}} = ζ(3) − ∑_{k=1}^{n} \frac{1}{k^{3}} ,

and the _{3}F_{3}-hypergeometrique function satisfies

−2_{3}F_{3} ({1, 1, 1 \atop 2, 2, 2}; −p) = −\frac{∫_{1}^{p} \frac{E_{1}(u)}{u}dp + 2γ ln p + ln^{2} p − \frac{385019}{216000}}{p} ,

where γ and E_{1} denote Euler’s constant γ = 0.5772156649 … and the exponential integral E_{1}(z) = ∫_{z}^{∞} \frac{exp(−t)}{t}dt respectively.

13. Abel’s identity

∑_{k=0}^{n} \binom{n}{k}(k + r)^{k−1}(n − k + s)^{n−k} = \frac{(n + r + s)^{n}}{r} .

A WZ-based proof can be found in [2, 5]; the more general holonomic approach also extend to Abel-type identities.

14. A sum suggested on the news by Eric Sparla

                     <sparla@mathematik.uni-stuttgart.de>

∑_{j=0}^{d} \binom{d}{j}\binom{d − r − j − 1}{r − j} = \frac{2^{r}}{r!} ∏_{i=0}^{r−1} d − 1 − 2i.

15. A problem suggested on the news by Eric Sparla

                     <sparla@mathematik.uni-stuttgart.de>

The sum u_{l,m}

∑_{i=0}^{m}(−2)^{i}\binom{2l − i}{l}\binom{m}{i}

satisfies

u_{j,2k+1} = 0, for 0 ≤ k < j, and u_{l,2l+1} = (−4)^{l}.

16. A double sum suggested on the news by Len Trigg

                         <trigg@jane.cs.waikato.ac.nz>

∑_{k,l∈ℕ} \frac{(2k + 2l + i + j)!}{(k + i)!(l + j)!k!l!} (\frac{x}{4})^{k+l} = \binom{i + j}{i, j}_{4}F_{3} ( {\frac{i+j}{2} + 1, \frac{i+j}{2} + 1, \frac{i+j+1}{2}, \frac{i+j+1}{2} \atop i + j + 1, i + 1, j + 1} ; 4x) .

This double sum appears when modeling a simple 5-instruction machine which goes to North, East, South or West with probability x/4 each and stops with probability 1 − x.

References

[1] Almkvist, G., and Zeilberger, D. The method of differentiating under the integral sign. Journal of Symbolic Computation 10 (1990), 571–591.

[2] Ekhad, S. B., and Majewicz, J. E. A short WZ-style proof of Abel’s identity. To appear., 1996.

[3] Foata, D. Some Hermite polynomial identities and their combinatorics. Advances in Applied Mathematics, 2 (1981), 250–259.

[4] Foata, D., and Garsia, A. M. A combinatorial approach to the Mehler formulas for Hermite polynomials. In Relations between Combinatorics and other parts of Mathematics (1979), D. K. Ray-Chaudhuri, Ed., A.M.S., pp. 163–179. Proceedings of Symposia in Pure Mathematics No. 34, Providence, 1979.

[5] Majewicz, J. E. WZ-style certification and Sister Celine’s technique for Abel-type sums. To appear., 1996.

[6] Strehl, V. Binomial identities — combinatorial and algorithmic aspects. Discrete Mathematics 136 (1994), 309–346.

[7] Wilf, H. S., and Zeilberger, D. An algorithmic proof theory for hypergeometric (ordinary and “q”) multisum/integral identities. Inventiones Mathematicae 108 (1992), 575–633.