Editing Generating function (section)

==={{math|''P''}}-recursive sequences and holonomic generating functions===

====Definitions====

A formal power series (or function) {{math|''F''(''z'')}} is said to be '''holonomic''' if it satisfies a linear differential equation of the form<ref>{{harvnb|Flajolet|Sedgewick|2009|loc=§B.4}}</ref>
<math display="block">c_0(z) F^{(r)}(z) + c_1(z) F^{(r-1)}(z) + \cdots + c_r(z) F(z) = 0, </math>

where the coefficients {{math|''c<sub>i</sub>''(''z'')}} are in the field of rational functions, <math>\mathbb{C}(z)</math>. Equivalently, <math>F(z)</math> is holonomic if the vector space over <math>\mathbb{C}(z)</math> spanned by the set of all of its derivatives is finite dimensional.

Since we can clear denominators if need be in the previous equation, we may assume that the functions, {{math|''c<sub>i</sub>''(''z'')}} are polynomials in {{mvar|z}}. Thus we can see an equivalent condition that a generating function is holonomic if its coefficients satisfy a '''{{mvar|P}}-recurrence''' of the form
<math display="block">\widehat{c}_s(n) f_{n+s} + \widehat{c}_{s-1}(n) f_{n+s-1} + \cdots + \widehat{c}_0(n) f_n = 0,</math>

for all large enough {{math|''n'' ≥ ''n''<sub>0</sub>}} and where the {{math|''ĉ<sub>i</sub>''(''n'')}} are fixed finite-degree polynomials in {{mvar|n}}. In other words, the properties that a sequence be ''{{mvar|P}}-recursive'' and have a holonomic generating function are equivalent. Holonomic functions are closed under the [[Generating function transformation#Hadamard products and diagonal generating functions|Hadamard product]] operation {{math|⊙}} on generating functions.

====Examples====

The functions {{math|''e''<sup>''z''</sup>}}, {{math|log ''z''}}, {{math|cos ''z''}}, {{math|arcsin ''z''}}, <math>\sqrt{1 + z}</math>, the [[dilogarithm]] function {{math|Li<sub>2</sub>(''z'')}}, the [[generalized hypergeometric function]]s {{math|''<sub>p</sub>F<sub>q</sub>''(...; ...; ''z'')}} and the functions defined by the power series
<math display="block">\sum_{n = 0}^\infty \frac{z^n}{(n!)^2}</math>

and the non-convergent
<math display="block">
\sum_{n = 0}^\infty n! \cdot z^n
</math>
are all holonomic.

Examples of {{mvar|P}}-recursive sequences with holonomic generating functions include {{math|''f''<sub>''n''</sub> ≔ {{sfrac|1|''n'' + 1}} {{pars|s=150%|{{su|p=2''n''|b=''n''|a=c}}}}}} and {{math|''f''<sub>''n''</sub> ≔ {{sfrac|2<sup>''n''</sup>|''n''<sup>2</sup> + 1}}}}, where sequences such as <math>\sqrt{n}</math> and {{math|log ''n''}} are ''not'' {{mvar|P}}-recursive due to the nature of singularities in their corresponding generating functions. Similarly, functions with infinitely many singularities such as {{math|tan ''z''}}, {{math|sec ''z''}}, and [[Gamma function|{{math|Γ(''z'')}}]] are ''not'' holonomic functions.

====Software for working with ''{{mvar|P}}''-recursive sequences and holonomic generating functions====

Tools for processing and working with {{mvar|P}}-recursive sequences in ''[[Mathematica]]'' include the software packages provided for non-commercial use on the [https://www.risc.jku.at/research/combinat/software/ RISC Combinatorics Group algorithmic combinatorics software] site. Despite being mostly closed-source, particularly powerful tools in this software suite are provided by the <code>'''Guess'''</code> package for guessing ''{{mvar|P}}-recurrences'' for arbitrary input sequences (useful for [[experimental mathematics]] and exploration) and the <code>'''Sigma'''</code> package which is able to find P-recurrences for many sums and solve for closed-form solutions to {{mvar|P}}-recurrences involving generalized [[harmonic number]]s.<ref>{{cite journal|last1=Schneider|first1=C.|title=Symbolic Summation Assists Combinatorics|journal=Sém. Lothar. Combin.|date=2007|volume=56|pages=1–36 |url=http://www.emis.de/journals/SLC/wpapers/s56schneider.html}}</ref> Other packages listed on this particular RISC site are targeted at working with holonomic ''generating functions'' specifically.
<!--Depending on how in depth this article gets on the topic, there are many, many other examples of useful software tools that can be listed here or on this page in another section, or most appropriately, on a dedicated webpage of its own.-->