A proof of a conjecture of Knuth. (English) Zbl 0984.33009

Summary: From numerical experiments, D. E. Knuth conjectured that \(0<D_{n+4}<D_n\) for a combinatorial sequence \((D_n)\) defined as the difference \(D_n=R_n-L_n\) of two definite hypergeometric sums. The conjecture implies an identity of type \[ L_n=\sum^n_{k=0} {2k\choose k}= \left\lfloor \sum^{\bigl\lfloor (3n+2)/4 \bigr\rfloor}_{k=0} {4\over 3}\left(-{1\over 3} \right)^k{k-1/2 \choose n}(-4)^n \right\rfloor. \tag{*} \] involving the floor function. We prove Knuth’s conjecture by applying D. Zeilberger’s algorithm [D. Zeilberger, Discrete Math. 80, No. 2, 207-211 (1990; Zbl 0701.05001)] as well as classical hypergeometric machinery.


33F10 Symbolic computation of special functions (Gosper and Zeilberger algorithms, etc.)
33C20 Generalized hypergeometric series, \({}_pF_q\)
05A10 Factorials, binomial coefficients, combinatorial functions
05A19 Combinatorial identities, bijective combinatorics
11B65 Binomial coefficients; factorials; \(q\)-identities
33C05 Classical hypergeometric functions, \({}_2F_1\)


[1] Andrews G. E., Electronic. J. Comb. 21 (1996)
[2] Andrews G. E., ”Pfaff’s method I: the Mills-Robbins-Rumsey determinant” · Zbl 1069.15009
[3] Andrews G. E., ”PfafF’s method II: diverse applications” · Zbl 0862.33003
[4] DOI: 10.1112/plms/s2-28.1.242 · JFM 54.0392.04
[5] DOI: 10.1137/0513021 · Zbl 0486.33003
[6] Graham R. L., Concrete Mathematics, A Foundation for Computer Science,, 2. ed. (1994)
[7] Karlsson P. W., Clausen’s hypergeometric series with variable {\(\tfrac14\)}J. Math. Anal. Appl. 196 pp 172– (1995) · Zbl 0846.33010
[8] Knuth, D. E. 1994. [Knuth 1994], letter of August 30, to the editor
[9] Krattenthaler C., J. Symb. Comput.
[10] Paule P., ”A Mathematica version of Zeilberger’s algorithm for proving binomial coefficient identities” · Zbl 0851.68052
[11] Takayama N., J. Symb. Comput. (special issue on ”Symbolic Computation in Combinatorics dgr;i”
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.