Изменения

|definition=Последовательность <tex>a_0, a_1, ...\ldots, a_n, ... \ldots </tex> называется заданной линейной рекуррентой, если её члены <tex>a_0 ... \ldots a_{k - 1} </tex> заданы, а <tex>\forall n \geqslant k </tex> выполняется <tex> a_n = c_1 \cdot a_{n - 1} + ... \ldots + c_k \cdot a_{n - k}</tex>

|statement=<tex>a_0, a_1, ...\ldots, a_n, ... \ldots </tex> задана линейной рекуррентой с <tex>k</tex> первыми заданными членами <tex>\Leftrightarrow</tex> её производящая функция <tex>A(t)</tex> является дробно-рациональной, причём она представима в виде <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg Q(t) = k, deg P(t) < k</tex>

<tex>\Leftarrow)</tex>. Пусть <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg Q(t) = k, deg P(t) < k</tex>. Тогда <tex>A(t) \cdot Q(t) = P(t)</tex>. Пусть <tex>Q(t)</tex> имеет вид <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - ... \ldots - c_k \cdot t^k</tex>.

Тогда <tex>a_n \cdot q_0 + a_{n - 1} \cdot q_1 + ... \ldots + a_{n - k} \cdot q_k + a_{n - k - 1} \cdot 0 + a_{n - k - 2} \cdot 0 + ... \ldots + a_{0} \cdot 0 = 0</tex> (так как <tex>deg Q(t) = k</tex>)

<tex>a_n - c_1 \cdot a_{n - 1} - ... \ldots -c_k \cdot a_{n - k} = 0</tex>

Тогда <tex>a_n = c_1 \cdot a_{n - 1} + ... \ldots + c_k \cdot a_{n - k}</tex>

<tex>A(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + ... \ldots + a_k \cdot t^k + ... \ldots + a_n \cdot t^n + ...\ldots</tex>

<tex>-c_1 \cdot t \cdot A(t) = 0 - c_1 \cdot a_0 \cdot t - c_1 \cdot a_1 \cdot t^2 - ... \ldots - c_1 \cdot a_{k - 1} \cdot t^k - ... \ldots - c_1 \cdot a_{n - 1} \cdot t^n - ...\ldots</tex>

<tex>-c_2 \cdot t^2 \cdot A(t) = 0 + 0 - c_2 \cdot a_0 \cdot t^2 - ... \ldots - c_2 \cdot a_{k - 2} \cdot t^k - ... \ldots - c_2 \cdot a_{n - 2} \cdot t^n - ...\ldots</tex>

<tex>-c_k \cdot t^k \cdot A(t) = 0 + 0 + 0 + ... \ldots - c_k \cdot a_0 \cdot t^k - ... \ldots - c_k \cdot a_{n - k} \cdot t^n + ...\ldots</tex>

<tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - ... \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + ... \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1} + (a_k - \sum\limits_{i = 1}^k c_i \cdot a_{k - i}) \cdot t^k + ... \ldots + (a_n - \sum\limits_{i = 1}^n c_i \cdot a_{n - i}) \cdot t^n + ...\ldots</tex>

Тогда <tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - ... \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + ... \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>.

Обозначим <tex>Q(t) = (1 - c_1 \cdot t - c_2 \cdot t^2 - ... \ldots - c_k \cdot t^k)</tex>,

а <tex>P(t) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + ... \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>