# recurrence-guess.gp

This is a spot of Pari/GP code to guess a linear recurrence from a vector of numbers (or vector of polynomials for guessing with further parameters). The result is pretty printed. For example,

recurrence_guess([1, 3, 9, 25, 65, 161, 385, 897, 2049, 4609]);
=>

Recurrence length=3
coefficients
v[n-3]* [4, -8, 5] *v[n-1]  = v[n]
v[n] =  v[n-1]* [5, -8, 4] *v[n-3]

characteristic polynomial
x^3 - 5*x^2 + 8*x - 4
= factors
(x - 2)^2    roots 2.00000
x - 1        roots 1.00000

generating function
(1 - 2*x + 2*x^2)/(1 - 5*x + 8*x^2 - 4*x^3)
= (1 - 2*x + 2*x^2) / ( (1 - x) * (1 - 2*x)^2 )
= partial fractions
1/(1 - x)
- 1/(1 - 2*x)
+ 1/(1 - 2*x)^2

as powers
n * 2^n
+ 1

OEIS
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (5,-8,4).
%F a(n) = 5*a(n-1) - 8*a(n-2) + 4*a(n-3).

The guess is found by a simple matsolve(). Linear recurrences include powers, polynomials, and polynomials times powers. Values given can themselves be GP polynomials for parameterization, or (very) limited symbolic calculation, or bivariate gfs guessed on one variable.

recurrence-guess.gp is free software (free as in freedom), published under the terms of the GNU General Public License (v3 or higher). Download version 15 here. Requires my pol-pfrac.gp.

recurrence-guess.gp (52k, and sig)
recurrence-guess-15.tar.gz (53k, and sig)

Just recurrence-guess.gp and pol-pfrac.gp are enough to run. The sig files are Gnu PG ascii armoured signatures generated from my key.

The tar file includes some self-tests, and the following examples/polmod.gp script illustrating linear recurrence evaluation using t_POLMOD, which is efficient and compact but a little obscure.

polmod.gp (18k, and sig)

## Install

To install so recurrence_guess() is always available interactively, put recurrence-guess.gp in say your ~/gp directory (which is in the GP default(path)) then in file ~/.gprc