Given minimal characteristic polynomial how to derive linear recurrence?

Question

I was able to find minimal characteristic polynomial of the sequence of numbers using Berlekamp-Massey algorithm. For example, for a sequence $$ 1,2,3,5,11,25,53,109,227,481,1022,2162,4563,9637,20375,43086 $$ I've found MCP $$ x^8 - 4x^7 + x^6 + 8x^5 - 7x^4 + 7x^3 + 3x^2 + x - 13 $$ How can I derive linear recurrence for a given MCP?

Thanks!

Answer 1

You have probably figured it out by now, anyway you can look in here LINEAR RECURSIVE SEQUENCES

for an explanation. The general rule is that with your minimal polynimial you also get your coefficients for your recurrence. Here it would be

$a_{n-8}=4a_{n-7} -a_{n-6} -8a_{n-5} +7a_{n-4}-7a_{n-3} -3a_{n-2}-a_{n-1}+13a_{n} $

with initial 8 conditions

a(1)=1, a(2)=2, a(3)=3, a(4)=5 etc.