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?
-
0Do you expect an exact fit, or an approximate regression? – 2012-12-10
-
0@deftfyodor Exact hit – 2012-12-10
-
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.
-
0Right now I indeed use FindLinearRecurrence. But I'd like to figure out how it's done "by hand"/with a computer, if possible. Feels like I'm taking a shortcut otherwise without really being able to do it myself. – 2012-12-10
-
0Well, you know how to do it "by hand" now, right? You can solve the equation by inverting the matrix. – 2012-12-10
-
0Not sure yet. How would you do it for, as an example, 1, 5, 23, 105, 479, 2185, 9967, 45465, 207391... (A107839 from OEIS), deriving "a(n)=5a(n-1)-2a(n-2); a(0)=1, a(1)=5." If I had just given you the number sequence alone. Say we guess it is degree 2 (not sure why we'd make that guess, but say we do) – 2012-12-10
-
0Okay, I'll do this example in my answer. – 2012-12-10
-
0Thanks. But you say you guess that f(n) = -2f(n-2) + 5f(n-1) -- let's say it turns out to be false. What then is the next step? – 2012-12-10
-
0No problem. If this fails, you can try $r=3$, so you use a $3 \times 3$ matrix with the data. If that doesn't work, try $r=4$, and so on. If $r$ gets very large you suspect that it does not obey any linear recurrence relation. – 2012-12-10
-
0Does $r$ here refer to degree? My understanding is that d x d array implies degree d. – 2012-12-10
-
0Yes, I chose $r$ to refer to degree for some reason. – 2012-12-10
-
0I guess what confuses me is that you only seemed to need four values to get the answer to something of degree 2. Is this a general rule? How many values are needed to get something of degree d? Sometimes when I use FindLinearRecurrence it doesn't spit out an answer unless I give it many values. – 2012-12-10
-
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)$.
-
0Can you give an example of what you mean? – 2012-12-10
-
0Actually let me use a random valid OEIS sequence: "1, 5, 23, 105, 479, 2185, 9967, 45465, 207391," – 2012-12-10