[seqfan] Re: Question about linear recurrence formulas

Rob Pratt Rob.Pratt at sas.com
Fri May 26 21:34:39 CEST 2017


-----Original Message-----
From: SeqFan [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of Peter Lawrence
Sent: Friday, May 26, 2017 3:31 PM
To: seqfan at list.seqfan.eu
Subject: [seqfan] Question about linear recurrence formulas


Sorry about the dumb question, but…

I don’t find   1,1,1,1,1,2,5,11,21,36,58,92,149,    in the data base,
And I’m five-nines sure it has a linear recurrence due to the way I derived it,

So I plugged this into an online simultaneous linear equation solver
        1  1  1   1   1      2
        1  1  1   1   2      5
        1  1  1   2   5     11
        1  1  2   5 11     21
        1  2  5 11 21     36

And got this output (1, 0, 1, -3, 3)
So the linear recurrence would be A(n) = 3A(n-1) - 3A(n-2) + A(n-3) + A(n-5),

It does seem to correctly compute the next couple terms, 58, 92, 149,

So then I entered in 6-term rows into a 6x6 solver and got
        B(n) = 6B(n-2) - 8B(n-3) + 3B(n-4) + B(n-5) + 3B(n-6) I am guessing B is a linear combination of A(n), A(n-1), …, but haven’t tried to figure it out, ?

Then got courageous and tried 7x7, but the solver said N.G. no solution ?
Perhaps I made a data entry error ?
Or perhaps this indicates the solution is of lower degree ?

is this a legitimate approach to the problem ?
        1) it has a linear recurrence
        2) in this example its degree is at least 5 (since it starts with 5 1’s)

(I am guessing that in the long run I will have to come up with a combinatorial proof of the recurrence formula based on how I initially derived the sequence.)

I did find some info in Wolfram Mathworld on “linear recurrence equation”, But they only handle 2’nd order recurrences (eg Fibonacci, Padovan, …), So perhaps this isn’t so dumb a question after all

Peter Lawrence.

Seqfan Mailing list - http://list.seqfan.eu/

More information about the SeqFan mailing list