In this paper we present a method to pass from a given recurrence relation with constant coefficients (in short, a C-finite recurrence) to a finite succession rule defining the same number sequence. Our method consists in two steps: first, we transform the given recurrence relation into an extended succession rule, then we provide a series of operations to reduce such an extended succession rule into an ordinary succession rule, equivalent to the previous one. As a byproduct, our method can be used to investigate the positivity of a C-finite recurrence.

Recurrence relations, succession rules and the positivity problem / Bilotta, Stefano; Pergola, Elisa; Pinzani, Renzo; Rinaldi, Simone. - In: JOURNAL OF COMPUTER AND SYSTEM SCIENCES. - ISSN 0022-0000. - STAMPA. - 104:(2019), pp. 102-118. [10.1016/j.jcss.2016.09.006]

Recurrence relations, succession rules and the positivity problem

BILOTTA, STEFANO
;
PERGOLA, ELISA;PINZANI, RENZO;RINALDI, SIMONE
2019

Abstract

In this paper we present a method to pass from a given recurrence relation with constant coefficients (in short, a C-finite recurrence) to a finite succession rule defining the same number sequence. Our method consists in two steps: first, we transform the given recurrence relation into an extended succession rule, then we provide a series of operations to reduce such an extended succession rule into an ordinary succession rule, equivalent to the previous one. As a byproduct, our method can be used to investigate the positivity of a C-finite recurrence.
2019
104
102
118
Goal 9: Industry, Innovation, and Infrastructure
Bilotta, Stefano; Pergola, Elisa; Pinzani, Renzo; Rinaldi, Simone
File in questo prodotto:
File Dimensione Formato  
RR.pdf

accesso aperto

Tipologia: Altro
Licenza: Tutti i diritti riservati
Dimensione 183.5 kB
Formato Adobe PDF
183.5 kB Adobe PDF
Recurrence relations.pdf

Accesso chiuso

Tipologia: Pdf editoriale (Version of record)
Licenza: Tutti i diritti riservati
Dimensione 506.84 kB
Formato Adobe PDF
506.84 kB Adobe PDF   Richiedi una copia

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/1067924
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact