A sequence \(U=\{u_n\}_{n\in \mathbb Z}\) of complex numbers is called a linear recurrence sequence if it satisfies a relation \(u_n=c_1u_{n-1}+\dots+c_t u_{n-t}\) with \(c_i\in \mathbb C\) and \(c_t\neq 0\). There is only one such relation for which \(t\) is minimal. Given this recurrence relation of minimal length, we call \(t\) the order of the sequence \(U\), and \(P_U(z)=z^t-c_1z^{t-1}-\dots-c_t\) the companion polynomial of \(U\). Writing \(P_U(z)=(z-\alpha_1)^{t_1}\dots (z-\alpha_k)^{t_k}\) we have \(u_n=P_1(n)\alpha^n_1+\dots+P_k(n)\alpha^n_k\) for \(n\in \mathbb Z\), where \(P_i(z)\) is a polynomial of degree \(