5
правок
Изменения
→3 пример
===<tex>3</tex> пример===
Найдём производящую функцию для последовательности квадратов чисел Фибоначчи: $1, 1, 4, 9, 25, \ldots, f_k^2,\ldots$.
По определению последовательности Фибоначчи выполняется:
<br><tex>
\left\{ \begin{array}{ll}
f_{n+2} = f_{n+1} + f_n \\
f_{n-1} = f_{n+1} - f_n
\end{array} \right.
</tex><br>
Возведя в квадрат и сложив, получим:
<br><tex>
\begin{array}{rcl}
f_{n+2}^2 + f_{n-1}^2 = 2f_{n+1}^2 + 2f_n^2, \\
f_{n+2}^2 = 2f_{n+1}^2 + 2f_n^2 - f_{n-1}^2, \\
f_{n}^2 = 2f_{n-1}^2 + 2f_{n-2}^2 - f_{n-3}^2.\\
\end{array}
</tex><br>
Обозначим рассматриваемую последовательность <tex>A</tex>, а её члены <tex>a_n</tex>, тогда:
<br><tex>a_n = 2a_{n-1} + 2a_{n-2} - a_{n-3}</tex><br>
Рекуррентное соотношение:
<br><tex>
\begin{array}{ll}
a_0 = f_0^2 = 1 \\
a_1 = f_1^2 = 1 \\
a_2 = f_2^2 = 4 \\
a_n = 2a_{n-1} + 2a_{n-2} - a_{n-3}, \quad n\geqslant3.\\
\end{array}
</tex><br>
Приведём суммы к замкнутому виду:
<br><tex>
\begin{array}{ll}
A(z) = \displaystyle\sum_{n=0}^{\infty}a_nz^n = 1 + z + 4z^2 + \displaystyle\sum_{n=3}^{\infty}(2a_{n-1} + 2a_{n-2} - a_{n-3})z^n, \\
A(z) = 1 + z + 4z^2 + 2\displaystyle\sum_{n=3}^{\infty}a_{n-1}z^n + 2\displaystyle\sum_{n=3}^{\infty}a_{n-2}z^n - \displaystyle\sum_{n=3}^{\infty}a_{n-3}z^n, \\
A(z) = 1 + z + 4z^2 + 2z\displaystyle\sum_{n=2}^{\infty}a_nz^n + 2z^2\displaystyle\sum_{n=1}^{\infty}a_nz^n - z^3\displaystyle\sum_{n=0}^{\infty}a_nz^n, \\
A(z) = 1 + z + 4z^2 + 2z(A(z) - 1 - z) + 2z^2(A(z) - 1) - z^3A(z), \\
A(z) = 1 + z + 4z^2 + 2zA(z) - 2z - 2z^2 + 2z^2A(z) - 2z^2 - z^3A(z), \\
A(z)(1 - 2z - 2z^2 + z^3) = 1 + z + 4z^2 - 2z - 2z^2 - 2z^2 = 1 - z, \\
\end{array}
</tex><br>
откуда получаем замкнутое выражение для производящей функции:
<br><tex>G(z) = \dfrac{1 - z}{1 - 2z - 2z^2 + z^3}.</tex><br>
===<tex>4</tex> пример===
Рассмотрим следующее рекуррентное соотношение:
<br><tex>\begin{array}{rcl}
\dfrac{7\cdot4^n+6n+20}{18} - 2^{n-1}.
</tex><br>
==См. также==
