Dfinite

Dfinite, short for differentiably finite, is a property used for certain functions, power series, and sequences in combinatorics and computer algebra. A formal power series F(x) is D-finite if there exists a nontrivial linear differential equation with polynomial coefficients:

p0(x)F(x) + p1(x)F'(x) + ... + pk(x)F^{(k)}(x) = 0,

where the polynomials pi are not all zero. Equivalently, such a function is holonomic. A sequence (a_n) is called D-finite or P-recursive if it satisfies a linear recurrence with polynomial coefficients in n:

p0(n)a_n + p1(n)a_{n+1} + ... + pk(n)a_{n+k} = 0.

The relationship between these two viewpoints is tight: the ordinary generating function A(z) = sum a_n z^n is D-finite if and only if the sequence (a_n) is P-recursive. Conversely, the coefficients of a D-finite power series satisfy a P-recursive relation. This correspondence makes D-finite objects a bridge between differential equations and recurrences, and underpins many symbolic-computation techniques in combinatorics.

Examples of D-finite objects include polynomials, factorials (a_{n+1} = (n+1)a_n), binomial coefficients, Fibonacci numbers, Catalan numbers, and many other combinatorial sequences. D-finite objects are closed under addition, multiplication, and differentiation; they are stable under several algebraic operations, though not all transformations preserve D-finiteness (for instance, exponentials of general D-finite functions need not be D-finite).

The concept was formalized in the late 1980s, notably by Lipshitz, and is widely used alongside the related notions of holonomic functions and P-recursive sequences. See also holonomic function, P-recursive sequence, and generating functions.