[seqfan] Question about linear recurrence formulas

[Peter Lawrence]

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 ?
Assuming
	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


Thanks,
Peter Lawrence.