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?
Tell me more
×
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.
|
|
|||||||
|
|
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 $$ \left(\begin{matrix} 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{matrix}\right)\left( \begin{matrix} x_1\\ x_2\\ \vdots \\ x_r \\ \end{matrix}\right)=\left( \begin{matrix} f(r+1)\\ f(r+2)\\ \vdots \\ f(2r)\\ \end{matrix}\right).$$ 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 $$\left( \begin{matrix} f(1) & f(2)\\ f(2) & f(3)\\ \end{matrix}\right)\left( \begin{matrix} x_1\\ x_2\\ \end{matrix}\right) = \left( \begin{matrix} f(3)\\ f(4)\\ \end{matrix}\right)$$ or in this case $$\left( \begin{matrix} 1 & 5\\ 5 & 23\\ \end{matrix}\right)\left( \begin{matrix} x_1\\ x_2\\ \end{matrix}\right) = \left( \begin{matrix} 23\\ 105\\ \end{matrix}\right)$$ with solution $$\left( \begin{matrix} x_1\\ x_2\\ \end{matrix}\right) = \left( \begin{matrix} 1 & 5\\ 5 & 23\\ \end{matrix}\right)^{-1}\left( \begin{matrix} 23\\ 105\\ \end{matrix}\right) = \left( \begin{matrix} -2\\ 5\\ \end{matrix}\right).$$ 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. |
|||||||||||
|
|
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)$. |
||||
