# What are some strategies for creating linear recurrence relationships?

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?

-
Do you expect an exact fit, or an approximate regression? –  Micah Dec 10 '12 at 1:23
@deftfyodor Exact hit –  KaliMa Dec 10 '12 at 1:38
@sunflower And how do you know the degree in advance? –  KaliMa Dec 10 '12 at 1:38

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.

-
Right 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. –  KaliMa Dec 10 '12 at 1:41
Well, you know how to do it "by hand" now, right? You can solve the equation by inverting the matrix. –  Jair Taylor Dec 10 '12 at 1:45
Not 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) –  KaliMa Dec 10 '12 at 1:46
Okay, I'll do this example in my answer. –  Jair Taylor Dec 10 '12 at 1:51
For 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. –  Jair Taylor Dec 10 '12 at 2:54

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)$.

-
Can you give an example of what you mean? –  KaliMa Dec 10 '12 at 1:41
Actually let me use a random valid OEIS sequence: "1, 5, 23, 105, 479, 2185, 9967, 45465, 207391," –  KaliMa Dec 10 '12 at 1:45