C-finite, P-recursive, etc. sequence subclasses?

[Robert Dougherty-Bliss]

I have recently been working with linear recurrence relations with constant and / or polynomial coefficients w.r.t. the index. (These are called C-finite and P-recursive sequences, respectively.) These sequences have some nice properties, such as easy closed-form expressions in the C-finite case from Binet's formula. Ultimately, I would like to do things in the vein of Doron Zeilberger's GuessHolo package for P-recursive sequences, as described in this paper.

Has anyone looked into creating a subclass of SeqBase (or something more appropriate) for recursive sequences? Perhaps specifically for C-finite and P-recursive sequences? It seems like this would be convenient in general. For instance, every sequence implements a method to guess a C-finite sequence that it might be (find_linear_recurrence()), but then just returns a list of coefficients rather than a complete sequence object. Outside of C-finite sequences, memoization could be baked in to make the evaluation of less-trivial recursive sequences nicer.

[Aaron Meurer]

There has been some work on recurrences, if you search the issue
tracker and pull request list for "recurrence" you can find some of
it. I'm not aware of any work along the lines of what you are
suggesting.

Regarding the evaluation of recurrences, there has been some work in
the new sympy.discrete.recurrences submodule.

Making SeqBase support recursive sequences sounds like a good idea.
One would need to make sure that all the methods work properly when
the sequence is recursive.

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at https://groups.google.com/group/sympy.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/sympy/d8c5f383-ee72-4c9a-b9a9-4c18fb91f8dd%40googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Robert Dougherty-Bliss]

The new recurrences submodule isn't quite what I had in mind. If I'm reading it right, it expands a C-finite recurrence into a linear combination of the initial values. This is good, but not a fully-fledged class. (I would like for this and related features to be a method of such a class.)

My proof of concept of this idea looks like this:

https://gist.github.com/rwbogl/06dab1e3b9935b292354b240e1807e75

I'm not sure that SeqBase itself could be modified for recursive sequences without losing generality.

[Aaron Meurer]

That looks like a good start. I would try to represent the sequence
symbolically instead of via a function so that it can be manipulated.

Aaron Meurer

On Mon, Aug 27, 2018 at 2:48 PM, Robert Dougherty-Bliss

> https://groups.google.com/d/msgid/sympy/9f96e0fc-e82a-4a28-b45a-a06cb462ac92%40googlegroups.com.

[Robert Dougherty-Bliss]

Can you explain what you mean by symbolically? I know that there are various classes for operations on sequences in series.sequences, but I feel like you mean something else. (I'm not very familiar with SymPy internals other than the "architecture" section of the contributor's guide.)

[Aaron Meurer]

If I understood your code correctly, "evaluation" is a Python function
that returns s_i, s_{i+1}, ..., s_{j} from the previous terms s_k,
..., s_{i-1}. It would be better to allow this formula to be
represented as a SymPy expression. You'll need another parameter to
specify the variables. This can easily be turned back into a function
using Lambda, but going from Python function to SymPy expression isn't
always possible.

Aaron Meurer

On Mon, Aug 27, 2018 at 4:38 PM, Robert Dougherty-Bliss

> https://groups.google.com/d/msgid/sympy/981fcc48-bc17-403c-91b5-bce094dd3f33%40googlegroups.com.

[Robert Dougherty-Bliss]

Ah, thanks for the explanation!

I updated the above gist to use symbolic recurrences:

https://gist.github.com/rwbogl/06dab1e3b9935b292354b240e1807e75

How does this look?

Related, this implementation doesn't play nicely with sequences not of "finite degree." For example, the Bell numbers (http://mathworld.wolfram.com/BellNumber.html). They have a recurrence that uses all previous Bell numbers, but I'm not sure how to substitute these values with, say, a summation index.