×

A Catalan identity leading to Segner’s recurrence. (English) Zbl 1263.11029

Catalan numbers, \(C_n=\frac{1}{n+1}{2n\choose n}\), \(n=0,1,2,\ldots,\) where \(C_0=1\), arise in a wide selection of combinatorial problems and applications. In this note, using the generating function for odd-numbered Catalan numbers, the author proved the following identity: \[ \sum_{k=0}^nC_{2k+1}C_{2n-2k+1}=C_{2n+3}-4^{n+1}C_{n+1}(1) \] where \(n\) is any nonnegative integer. Notice that the identity (1) is the odd analogue of the identity \[ \sum_{k=0}^nC_{2k}C_{2n-2k}=4^nC_n(2) \] established in 2002 by L.W. Shapiro. Moreover, the identities (1) and (2) are extensions of the following well known Segner’s recurrence relation: \[ \sum_{k=0}^nC_kC_{n-k}=C_{n+1}.(3) \] The author of this note also observed that the identity (3) easily follows from the identities (1) and (2).

MSC:

11B65 Binomial coefficients; factorials; \(q\)-identities
05A19 Combinatorial identities, bijective combinatorics