# Tangled up in sequences and recurrence relations

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 dont 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

$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]  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 • @ 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[] – Dr. Wolfgang Hintze Oct 29 '14 at 12:12 • 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]]. – Bob Hanlon Oct 29 '14 at 13:07 • @ Bob Hanlon: yes Bob, thanks. That's what I did already in my question. – Dr. Wolfgang Hintze Oct 31 '14 at 17:57 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} *)  • @ rcollyer: thanks. That explains the usage. Would have expected this in the doc. – Dr. Wolfgang Hintze Oct 28 '14 at 21:20 • @Dr.WolfgangHintze it is in the docs. You just have to dig a little to find it. – rcollyer Oct 28 '14 at 21:21 • @ 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. – Dr. Wolfgang Hintze Oct 28 '14 at 21:28 • @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. – rcollyer Oct 29 '14 at 0:26 • @ 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)" – Dr. Wolfgang Hintze Oct 29 '14 at 12:02

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.

• @ 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. – Dr. Wolfgang Hintze Oct 28 '14 at 21:24
• @ 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? – Dr. Wolfgang Hintze Oct 28 '14 at 21:36
• 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. – Kellen Myers Nov 1 '14 at 19:13