Consideramos la secuencia, $(a_n)_{n \geq 0}$ generado por la fórmula de recurrencia lineal.
La función generadora puede escribirse como $\frac{f(X)}{g(X)}$ donde $\deg g=n$ y $\deg f \leq n-1$ . Sin perder la generalidad, podemos establecer $[X^0] g(X)=1$ .
Según el algoritmo de Berlekamp Massey, para determinar el coeficiente de $f(X)$ y $g(X)$ Sólo necesitamos primero $2n$ términos de $(a_n)$ . Comparando cada término del LHS y del RHS de $f(X)=g(X)\sum_{i=0}^\infty a_iX^i$ (mod $2n$ ), obtenemos $2n$ ecuaciones. Dado que hay $2n$ coeficientes desconocidos, podemos determinar todos ellos si y sólo si el $2n$ Las ecuaciones son linealmente independientes entre sí.
Según el Algoritmo Berlekamp Massey, siempre podemos determinar $f(X)$ y $g(X)$ de la primera $2n$ plazo de $(a_n)$ .
Por qué las euqaciones que obtenemos de $f(X)=g(X)\sum_{i=0}^\infty a_iX^i$ (mod $X^{2N}$ ) son siempre linealmente independientes?
