For instance if I have a string of numbers outputted from some function $f(1), f(2), f(3), \ldots, f(n)$ that can be expressed in the form of $f(n) = af(n-10) + bf(n-9) + \cdots+ jf(n-1)$ etc (It doesn't have to be $n-10$, just using it as an example), how do you go about deriving such an expression? Just trial and error, guessing the degree and then playing around with numbers until it fits your data?
What are some strategies for creating linear recurrence relationships?
-
0@sunflower And how do you know the degree in advance? – 2012-12-10
2 Answers
You can use the data to get a system of linear equations that you can solve by inverting the appropriate matrix.
Let's suppose you think that $f$ obeys a recurrence of order $r$. You are trying to find numbers $x_1, \ldots, x_r$ so that $f(n) = x_1 f(n-r) + x_2 f(n-r+1) + \ldots + x_r f(n-1)$ for all $n > r$ - but in particular, for $r+1, r+2, \ldots, 2r$. This gives the matrix equation
$ \begin{pmatrix} f(1) & f(2) & \ldots & f(r)\\ f(2) & f(3)& \ldots & f(r+1)\\ \vdots & \vdots & \ddots & \vdots\\ f(r) & f(r+1) &\ldots & f(2r-1) \end{pmatrix}\begin{pmatrix} x_1\\x_2\\\vdots \\x_r \\ \end{pmatrix}=\begin{pmatrix} f(r+1)\\f(r+2)\\\vdots \\f(2r)\\ \end{pmatrix}.$
If you can solve this system, then $f$ may obey a linear recurrence. But if the values of $f$ are chosen randomly, you'll probably be able to solve this system but $f$ won't obey a recurrence relation. To test it, check that the solution for $x_1, \ldots, x_r$ satisfies the additional equation $x_1f(r+1) + \ldots x_r f(2r) = f(2r+1)$. If this happens, it is likely that $f$ obeys the recurrence relation, although of course this is not a proof.
If you're not sure what $r$ might be, you can try this algorithm for larger and larger values of $r$. Google tells me that Mathematica has a function FindLinearRecurrence
, I imagine other software packages have similar functions.
Edit: Here's an explicit example with the sequence $1, 5, 23, 105, 479, 2185, 9967, 45465, 207391$. We'll guess $r=2$. We get the matrix equation
$\begin{pmatrix} f(1) & f(2)\\ f(2) & f(3)\\ \end{pmatrix}\begin{pmatrix} x_1\\x_2\\ \end{pmatrix} = \begin{pmatrix} f(3)\\f(4)\\ \end{pmatrix}$
or in this case
$\begin{pmatrix} 1 & 5\\ 5 & 23\\ \end{pmatrix}\begin{pmatrix} x_1\\x_2\\ \end{pmatrix} = \begin{pmatrix} 23\\105\\ \end{pmatrix}$
with solution
$\begin{pmatrix} x_1\\x_2 \end{pmatrix} = \begin{pmatrix} 1 & 5\\ 5 & 23\\ \end{pmatrix}^{-1}\begin{pmatrix} 23\\105 \end{pmatrix} = \begin{pmatrix} -2\\5 \end{pmatrix}$
So we guess that $f(n) = -2f(n-2) + 5f(n-1)$. We check this against the given data, and it appears to be correct.
-
1For the algorithm outlined above, you need at least $2d+1$ values if you think it has a recurrence of order $d$: $2d$ for the matrix equation and at least $1$ more as a check. I don't know how the Mathematica algorithm works, so I can't comment on that. – 2012-12-10
Find the least $k$ such that the $(n+1-k) \times k$ matrix $A$ with entries $A_{ij} = f(i+j-1)$ has rank less than $k$. If $(c_0, \ldots, c_{k-1})$ is a vector in the null space of $A$, you have the recurrence $c_0 f(j) + c_1 f(j-1) + \ldots + c_k f(j-k) = 0$
EDIT: For your example $1, 5, 23, 105, 479, 2185, 9967, 45465, 207391$, we first try $k=2$, but find $A$ has rank $2$.
Next try $k=3$: $ A = \pmatrix{1&5&23\cr 5&23&105\cr 23&105&479\cr 105&479&2185 \cr 479&2185&9967\cr 2185&9967&45465 \cr 9967&45465&207391\cr } \ \text{has rank } 2$ and a vector in its null space is $ \pmatrix{2\cr -5\cr 1\cr}$ so (at least for the given data) we have $2 f(j) - 5 f(j+1) + f(j+2) = 0$ which you may prefer to write as $f(i) = 5 f(i-1) - 2 f(i-2)$.
-
0Actually let me use a random valid OEIS sequence: "1, 5, 23, 105, 479, 2185, 9967, 45465, 207391," – 2012-12-10