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.
2009
Proceedings of the 11th Italian Conference on Computer Science
11th Italian Conference on Theoretical Computer Science,, ICTCS 2009
Cremona, Italy
September 28-30, 2009
D. Merlini; R. Sprugnoli
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/647375
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact