Riordan arrays can be used to compute a combinatorial sum by performing a suitable transformation of the involved generating function and then a coefficient extraction. We present an algorithm which returns a recurrence relation for the sequence corresponding to the identity, similarly to what happens with the Zeilberger algorithm. If the recurrence relation can be solved, then we have a constructive proof of the combinatorial identity. Otherwise, the recurrence can be used to verify that the identity holds or, also, to find an asymptotic approximation of the sum.
An algorithm for proving identities with Riordan transformations / D. Merlini; R. Sprugnoli. - STAMPA. - (2009), pp. 169-174. (Intervento presentato al convegno 11th Italian Conference on Theoretical Computer Science,, ICTCS 2009 tenutosi a Cremona, Italy nel September 28-30, 2009).
An algorithm for proving identities with Riordan transformations
MERLINI, DONATELLA;SPRUGNOLI, RENZO
2009
Abstract
Riordan arrays can be used to compute a combinatorial sum by performing a suitable transformation of the involved generating function and then a coefficient extraction. We present an algorithm which returns a recurrence relation for the sequence corresponding to the identity, similarly to what happens with the Zeilberger algorithm. If the recurrence relation can be solved, then we have a constructive proof of the combinatorial identity. Otherwise, the recurrence can be used to verify that the identity holds or, also, to find an asymptotic approximation of the sum.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
