Timeline for Determining a recurrence relation
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 1, 2011 at 13:47 | vote | accept | Charles | ||
| Jun 2, 2011 at 22:15 | comment | added | Henry Cohn | On the other hand, as soon as you match $2d+1$ terms something nontrivial is happening, although the pattern might not continue. Berlekamp-Massey finds all these cases, so in particular if there is an actual recurrence of degree $d$ and the algorithm is given more than $2d$ terms, then it is guaranteed to find the true recurrence. | |
| Jun 2, 2011 at 22:15 | comment | added | Henry Cohn | When I say matching $2d$ or fewer terms doesn't mean anything, I mean there is always a rational function with numerator and denominator of degree at most $d$ that matches $2d$ terms. The denominator might vanish at $0$ (which would mess up the recurrence interpretation), but another way to look at it is that one can generically choose $d$ coefficients for the recurrence so that running it starting with the first $d$ terms matches the next $d$. So seeing this happen shouldn't carry much weight. | |
| Jun 2, 2011 at 20:57 | comment | added | Aaron Meyerowitz | I like the answer but wonder abut the comment A degree $d$ linear recurrence must be satisfied by more than $2d$ terms of the sequence to mean anything, and any such recurrence will be detected by this method. I take it that that is a rule of thumb? One never knows for sure if there is an irregularity further ahead. And ( for $d$ not too small) would observing a possible order $d$ recurrence after $2d-2$ steps mean so much less than after $2d$ steps? | |
| Jun 2, 2011 at 11:57 | history | answered | Henry Cohn | CC BY-SA 3.0 |