Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Do you expect an exact fit, or an approximate regression? –  deftfyodor 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

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
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
1  
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)$.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.