A Proof of a Conjecture of Knuth

Peter Paule

Abstract

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} = ⌊R_{n}⌋, involving the floor function. We prove Knuth’s conjecture by applying Zeilberger’s algorithm as well as classical hypergeometric machinery.