3
$\begingroup$

I took a trip through sequences and recurrence relations and I got tangled up since the documentation didn't help much. I'm sure you can.

Given a sequence

s = {0, 1, 2, 5, 12, 27, 58, 121, 248, 503, 1014, 2037, 4084, 8179, 
   16370, 32753};

I'd like to find a recurrence relation for s and try

fr = FindLinearRecurrence[s]

(* Out[150]= {4, -5, 2, 0} *)

Now the question: what does this list of four elements mean? How does the recurrence relation look like? I couldn't find an Explanation in the documentation.

Of course I tried what I would naturally consider the inverse, LinearRecurrence. But I even did not understand which arguments I had to put into the function.

Ok, I found a recurrence relation, but with another approach, which was a little adventurous. My question here is: how is this track to be passed correctly?

Here we go

fs = FindSequenceFunction[s]

(* Out[160]= DifferenceRoot[
 Function[{\[FormalY], \[FormalN]}, {2 - \[FormalN] - 
     2 \[FormalY][\[FormalN]] + \[FormalY][1 + \[FormalN]] == 
    0, \[FormalY][1] == 0, \[FormalY][2] == 1}]] *)

Here we can spot a recurrence relation together with initial conditions (we also replace [FormalX] by X)

eq = {2 - \[FormalN] - 
     2 \[FormalY][\[FormalN]] + \[FormalY][1 + \[FormalN]] == 
    0, \[FormalY][1] == 0, \[FormalY][2] == 1} /. {\[FormalY] -> 
    y, \[FormalN] -> n} 

(* Out[163]= {2 - n - 2 y[n] + y[1 + n] == 0, y[1] == 0, y[2] == 1} *)

Trying to solve it in the usual way

RSolve[eq, y[n], n]

During evaluation of In[164]:= RSolve::bvnul: For some branches of the general solution, the given boundary conditions lead to an empty solution. >>

(* Out[164]= {} *)

Again a failure! I'm not very lucky this time ...

Ok, let's RSolve the equation with only one initial condition (as it should be for a difference equation of order 1, I don`t understand the two Initial conditions under DifferenceRoot[] above):

yy[n_] = y[n] /. 
   RSolve[2 - n - 2 y[n] + y[1 + n] == 0 && y[1] == 1, y[n], n][[1]] // 
  Simplify

(* Out[206]= 1 + 2^(-1 + n) - n *)

This seems to be ok.

Table[yy[n], {n, 1, 16}]

(* Out[210]= {1, 1, 2, 5, 12, 27, 58, 121, 248, 503, 1014, 2037, 4084, 8179, 16370, 32753} *)

Except for the first term it is the case.

I'm sure all this can be done much better and shorter, and I hope you can help.

Regards, Wolfgang

Improve this question
$\endgroup$

3 Answers 3

Reset to default
4
$\begingroup$ 
$Version

"10.0 for Mac OS X x86 (64-bit) (September 10, 2014)"

s = {0, 1, 2, 5, 12, 27, 58, 121, 248, 503, 1014, 2037, 4084, 8179, 16370, 
   32753};

On my setup, FindLinearRecurrence returns unevaluated with this sequence

 fr = FindLinearRecurrence[s]

FindLinearRecurrence[{0, 1, 2, 5, 12, 27, 58, 121, 248, 503, 1014, 2037, 4084, 8179, 16370, 32753}]

fs = FindSequenceFunction[s]

enter image description here

Clear[a]

yy[1] = 0;
yy[n_Integer?Positive] = a[n] /. RSolve[{a[n] ==
      2 a[n - 1] + n - 3, a[2] == 1}, a[n], n][[1]]

1/2 (2 + 2^n - 2 n)

Verifying that FindSequenceFunction and RSolve give equivalent results

With[{r = Range[Length[s]]},
 s == fs /@ r == yy /@ r]

True

Improve this answer
$\endgroup$
3
  • $\begingroup$ @ Bob Hanlon. Hence V10 on Mac is weaker than my V8 on Windows. At least FindLinearRecurrence[s] resulted correctly in {4, -5, 2, 0}. The only weak point was myself then. But now I understand how to interpret this list. Still - as I said before in this discussion - the corresponding recurrence relation differs from the one inside DifferenceRoot[] $\endgroup$
    – Dr. Wolfgang Hintze
    Oct 29, 2014 at 12:12
  • $\begingroup$ I wrote the equations in RSolve from the DifferenceRoot. The second initial condition (yy[1]= 0) handles the anomalous first element in the sequence. You get the same result with a direct use of DifferenceRoot as y[n] /. RSolve[{2 - n - 2 y[n] + y[n + 1] == 0, y[2] == 1}, y[n], n][[1]]. $\endgroup$
    – Bob Hanlon
    Oct 29, 2014 at 13:07
  • $\begingroup$ @ Bob Hanlon: yes Bob, thanks. That's what I did already in my question. $\endgroup$
    – Dr. Wolfgang Hintze
    Oct 31, 2014 at 17:57
3
$\begingroup$

From the details section of ref/FindLinearRecurrence, it says

FindLinearRecurrence gives the shortest kernel ker which reproduces list from LinearRecurrence[ker,init,\[Ellipsis]]. The initial list init comes from the first elements in list.

The key to using LinearRecurrence is that the second argument has to be as long as the first argument (the result from FindLinearRecurrence), e.g.

LinearRecurrence[{4, -5, 2, 0}, {0, 1, 2, 5}, 15]
(*
{0, 1, 2, 5, 12, 27, 58, 121, 248, 503, 1014, 2037, 4084, 8179, 16370}
*)
Improve this answer
$\endgroup$
7
  • $\begingroup$ @ rcollyer: thanks. That explains the usage. Would have expected this in the doc. $\endgroup$
    – Dr. Wolfgang Hintze
    Oct 28, 2014 at 21:20
  • $\begingroup$ @Dr.WolfgangHintze it is in the docs. You just have to dig a little to find it. $\endgroup$
    – rcollyer
    Oct 28, 2014 at 21:21
  • $\begingroup$ @ rcollyer: I dug ... but no nugget I found. Could you tell me the exact location, please? My feeling is that something like your example should appear very early in the doc of this item. $\endgroup$
    – Dr. Wolfgang Hintze
    Oct 28, 2014 at 21:28
  • $\begingroup$ @Dr.WolfgangHintze I list the line I found in the Details section of the docs for FindLinearRecurrence. Its the second, first line there (of two). The link to LinearRecurrence provides use details, but mostly I just guessed. $\endgroup$
    – rcollyer
    Oct 29, 2014 at 0:26
  • $\begingroup$ @ rcollyer: thanks for your effort. But I don't have any Details section. Maybe I'm "vinctim" of $Version -> "8.0 for Microsoft Windows (64-bit) (October 7, 2011)" $\endgroup$
    – Dr. Wolfgang Hintze
    Oct 29, 2014 at 12:02
3
$\begingroup$

First, the correct interpretation of the output {4, -5, 2, 0} is that your sequence satisfies the recurrence $a_n = 4a_{n-1}-5a_{n-2}+2a_{n-3}+0a_{n-4}$.

It might be confusing as to why the 0 term is there, but the reason is that your fourth term would not follow the rule correctly (which, in all honesty, really means that your first term is ``wrong"). You have an order-three recurrence that has four initial values, but Mathematica's brain, that doesn't make sense, so it makes it order 4. Try something like:

FindLinearRecurrence[Join[Table[7,{i,1,10}],Table[Fibonacci[i],{i,1,100}]]

to see how it might over-complicate this type of recurrence (you ought to get {1,1,0,0,0,...}).

Anyway, anomaly aside, you can reproduce your sequence as:

LinearRecurrence[{4, -5, 2, 0}, {0, 1, 2, 5}, 10]

(* output: {0, 1, 2, 5, 12, 27, 58, 121, 248, 503} *)

Note that this is not the same as:

LinearRecurrence[{4, -5, 2}, {0, 1, 2}, 10]

(* output: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} *)

Note that FindSequenceFunction doesn't give you a linear recurrence -- it has other stuff in it. I'm not sure which one is better for you, but if you truly want the linear recurrence, you should use FindLinearRecurrence.

Improve this answer
$\endgroup$
3
  • $\begingroup$ @ Kellen Myers: thanks for the hints. I did not intend to find the recurrence relation by applying FindSequenceFunction. But it accidentially did something like providing just a recurrence relation rather than givin the relatively simple sequence function. $\endgroup$
    – Dr. Wolfgang Hintze
    Oct 28, 2014 at 21:24
  • $\begingroup$ @ Kellen Myers: let me add that the "wrong" way (via FindSequenceFunction) produced even a first order difference equation. But this was inhomogeneous. BTW: how are inhomogeneous difference equations represented? $\endgroup$
    – Dr. Wolfgang Hintze
    Oct 28, 2014 at 21:36
  • $\begingroup$ To my knowledge, just as DifferenceRoot objects. I don't know if there are other ways of representing them analogous to LinearRecurrence but I don't know any. $\endgroup$
    – Kellen Myers
    Nov 1, 2014 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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