Немного про производящие функции
Мотивация
Идея данной публикации родилась в процессе чтения статьи на викиконспектах о производящих рядах. Мне показалось очень интересным, что существует способ решения рекуррентных уравнений с помощью бесконечных сумм.
Здесь мы собираемся рассмотреть что такое производящая функция, разложение в ряд Тейлора, а также затронем математическую индукцию.
Ликбез
Для начала, по моему мнению, нужно кратко описать сущности, которые появляются в статье.
Кратко о производящей функции последовательности
Производя́щая фу́нкция после́довательности — алгебраическое понятие, которое позволяет работать с разными комбинаторными объектами аналитическими методами. Они дают гибкий способ описывать соотношения в комбинаторике, а иногда помогают вывести явные формулы для числа комбинаторных объектов определённого типа. (Википедия)
Для последовательности \(\{a_n\}\) производящим рядом называется бесконечная сумма:
\[\Large{
G(z) = \sum_{n=0}^\infty a_nz^n.
}\]
В данной статье описывается, как использовать производящий ряд последовательности для решения рекуррентных уравнений вида:
\[\Large{
a_n = f(a_{n-1}, \dots, a_0).
}\]
Кратко о ряде Тейлора
Ряд Те́йлора — разложение функции в бесконечную сумму степенных функций. (Википедия)
Для бесконечно дифференцируемой функции \(f(x)\) в окрестности точки \(a\) рядом Тейлора называется ряд:
\[\Large{
f(x) = \sum_{n=0}^\infty \frac{f^{(n)}(a)}{n!}(x-a)^n.
}\]
В нашем случае этот ряд будет полезен тем, что когда мы вычислим производящую функцию последовательности в виде дроби, мы сможем разложить её в ряд и найти общую формулу для элементов последовательности.
Кратко о математической индукции
Математическая индукция — метод математического
доказательства, который используется, чтобы доказать
истинность некоторого утверждения для всех натуральных
чисел. Для этого сначала проверяется истинность утверждения
с номером \(1\) — база (базис) индукции, а затем
доказывается, что если верно утверждение с номером \(n\), то
верно и следующее утверждение с номером \(n+1\) — шаг
индукции, или индукционный переход.
(Википедия)
Нам понадобится этот метод для того, чтобы доказать верность формулы, которую мы получим. Применяя к нашему случаю, можно сформулировать идею доказательства так:
- Нужно доказать базу индукции. То есть, что формула верна для \(a_0\) и \(a_1\).
- Нужно доказать переход индукции. В нашем случае, это означает, что нужно проверить, что формула удовлетворяет изначальному рекуррентному уравнению.
Идея доказательства состоит в том, что для любого \(k > 1\) наша формула будет верна, потому что она рекурсивно раскладывается с помощью верного перехода до верных базовых случаев.
Получение ряда в замкнутом виде
Первое, что нам нужно сделать, это найти ряд в замкнутом виде, т. е. в виде дроби.
По определению:
$$
\Large{
G(z) = \sum_{n=0}^\infty a_n z^n
}
$$
Тогда можно вынести первые два члена, которые известны:
\[\Large{
G(z) = a_0 + a_1 z + \sum_{n=2}^\infty a_n z^n
}\]
По формуле чисел Фибоначчи:
\[
\Large{
G(z) = a_0 + a_1 z + \sum_{n=2}^\infty (a_{n-1} + a_{n-2}) z^n =
}
\]
\[
\Large{
= a_0 + a_1 z + \sum_{n=2}^\infty a_{n-1} z^{n-1} z +
\sum_{n=2}^\infty a_{n-2} z^{n-2} z^2 =
}
\]
\[
\Large{
= a_0 + a_1 z + z\underbrace{\sum_{n=2}^\infty a_{n-1} z^{n-1}}_{(I)} +
z^2 \underbrace{\sum_{n=2}^\infty a_{n-2} z^{n-2}}_{(II)}
}
\]
Рассмотрим \((I)\) и \((II)\).
\[\Large{
(I) = \sum_{n=2}^\infty a_{n-1} z^{n-1} = \left<
\begin{split}
k = n-1\\
n = k+1
\end{split}
\right> = \sum_{k=1}^\infty a_{k} z^{k} =
}\]
\[\Large{
= \underbrace{a_0 + \sum_{k=1}^\infty a_{k} z^{k}}_
{\sum_{k=0}^\infty a_{k} z^{k}}
- a_0
= \sum_{k=0}^\infty a_{k} z^{k} - a_0 = G(z) - a_0
}\]
\[\Large{
(II) = \sum_{n=2}^\infty a_{n-2} z^{n-2} =
\left<
\begin{split}
k = n-2\\
n = k+2
\end{split}
\right>
= \sum_{k=0}^\infty a_{k} z^{k} = G(z)
}\]
Здесь мы производим замену и приводим суммы к виду \(\sum\limits_{i=0}^\infty a_iz^i\). Очевидно, значение суммы не зависит от названия счетчика \(i\).
Таким образом:
\[\Large{
G(z) = a_0 + a_1 z + z \left( G\left(z\right) - a_0 \right) + z^2G(z) =
}\]
\[\Large{
= a_0 + a_1 z + z G(z) - a_0 z + z^2 G(z)
}\]
Перенесем все члены с \(G(z)\) влево:
\[\Large{
G(z) - zG(z) - z^2 G(z) = a_0 +a_1z-a_0z
}\]
\[\Large{
G(z)\left(1 - z - z^2\right) = a_0 +a_1z-a_0z
}\]
В итоге, получаем:
\[\Large{
G(z) = \frac{a_0 +a_1z-a_0z}{1 - z - z^2}
}\]
Замечание: получившееся дробь правильная. То есть степень многочлена в знаменателе больше, чем в числителе.
Разложение дроби на элементарные дроби
Мы получили ряд:
\[\Large{
G(z) = \frac{a_0 + a_1 z - a_0 z}{1 - z - z^2}
}\]
Рассмотрим знаменатель:
\[\Large{
-z^2 - z + 1 = 0
}\]
Разложим его на множители:
\[\Large{
D = (-1)^2 - 4 \cdot 1 \cdot (-1) = 5
}\]
\[\Large{
\begin{split}
z_{1} = - \frac{1 + \sqrt{5}}{2}\\
z_{2} = - \frac{1 - \sqrt{5}}{2}
\end{split}
}\]
Тогда:
\[\Large{
-z^2 -z + 1 = -(z - z_1)(z - z_2)
}\]
Таким образом, мы можем записать:
\[\Large{
G(z) = \frac{a_0 + a_1 z - a_0 z}{-(z-z_1)(z-z_2)} =
\frac{A}{z-z_1} + \frac{B}{z - z_2}
}\]
Домножим обе части на \(-(z-z_1)(z-z_2)\):
\[\Large{
a_0 + a_1 z - a_0 z = -A(z-z_2) - B(z-z_1)
}\]
Раскроем скобки и сгруппируем относительно степеней \(z\):
\[\Large{
a_0 + z(a_1 - a_0) = -Az + Az_2 - Bz + Bz_1 = (Az_2 + Bz_1) + z(-A -B)
}\]
Получаем систему линейных уравнений с двумя неизвестными:
\[\Large{
\begin{cases}
&Az_2 &+ &B z_1 &= a_0\\
&A &+ &B &= a_0 - a_1
\end{cases}
}\]
Решение тривиально, опустим его. Приведу только ответ:
\[\Large{
\begin{cases}
&A = a_0 - a_1 - \frac{a_0 - a_0z_2 + a_1z_2}{z_1-z_2}\\
&B = \frac{a_0 - a_0z_2 + a_1z_2}{z_1-z_2}
\end{cases}
}\]
Таким образом, получаем следующий результат:
\[\Large{
\begin{cases}
z_{1} &= - \frac{1 + \sqrt{5}}{2}\\
z_{2} &= - \frac{1 - \sqrt{5}}{2}\\
A &= a_0 - a_1 - \frac{a_0 - a_0z_2 + a_1z_2}{z_1-z_2}\\
B &= \frac{a_0 - a_0z_2 + a_1z_2}{z_1-z_2}\\
G(z) &= \frac{A}{z - z_1} + \frac{B}{z - z_2}
\end{cases}
}\]
Доказательство по индукции
База индукции
\(n = 0\)
Подставим \(n=0\) в полученную формулу:
\[\Large{
a_0 = \left(
-\frac{A}{z_1} - \frac{B}{z_2}
\right)
}\]
Рассмотрим \(A\):
\[\Large{
A = \frac{a_0z_1-a_0z_2-a_1z_1+a_1z_2-a_0+a_0z_2-a_1z_2}{z_1-z_2} =
}\]
\[\Large{
= \frac{a_0z_1-\cancelto{0}{a_0z_2+a_0z_2}-a_1z_1+
\cancelto{0}{a_1z_2-a_1z_2}-a_0}{z_1-z_2} =
}\]
\[\Large{
= \frac{a_0z_1-a_1z_1-a_0}{z_1-z_2} = z_1\frac{a_0-a_1}{z_1-z_2}-\frac{a_0}{z_1-z_2}
}\]
Проведя аналогичные вычисления для \(B\) получим:
\[\Large{
B = \frac{a_0}{z_1-z_2} - z_2 \frac{a_0-a_1}{z_1-z_2}
}\]
Тогда:
\[\Large{
a_0 = \frac{a_0}{z_1(z_1-z_2)} - \frac{z_1}{z_1}\frac{a_0-a_1}{z_1-z_2} +
}\]
\[\Large{
+ \frac{z_2}{z_2}\frac{a_0-a_1}{z_1-z_2} - \frac{a_0}{z_1-z_2} =
}\]
\[\Large{
=\frac{a_0}{z_1(z_1-z_2)} - \cancelto{0}{\frac{a_0-a_1}{z_1-z_2} +
\frac{a_0-a_1}{z_1-z_2}} - \frac{a_0}{z_2(z_1-z_2)} =
}\]
\[\Large{
= \frac{a_0z_2-a_0z_1}{z_1z_2(z_1-z_2)} =
-\frac{a_0(z_1-z_2)}{z_1z_2(z_1-z_2)} = -\frac{a_0}{z_1z_2}
}\]
Рассмотрим \(z_1z_2\):
\[\Large{
z_1z_2 = \frac{(1+\sqrt{5})(1-\sqrt{5})}{2\cdot2} = \frac{1-5}{4} = -1
}\]
Подставив результат в наше выражение:
\[\Large{
-\frac{a_0}{-1} = a_0, \text{ Q.E.D.}
}\]
\(n = 1\)
По нашей формуле:
\[\Large{
a_1 =
-\left(
\frac{A}{z_1^2} +
\frac{B}{z_2^2}
\right) =
}\]
\[\Large{
= -\left(
\frac{a_0-a_1}{z_1(z_1-z_2)} - \frac{a_0}{z_1(z_1-z_2)} +
\frac{a_0}{z_2(z_1-z_2)} - \frac{a_0-a_1}{z_2(z_1-z_2)}
\right) =
}\]
\[\Large{
= -\left(
\frac{a_0-a_1}{z_1-z_2} \left(
\frac{1}{z_1} -
\frac{1}{z_2}
\right) +
\frac{a_0}{z_1-z_2} \left(
\frac{1}{z_1^2} -
\frac{1}{z_2^2}
\right)
\right) =
}\]
\[\Large{
= -\left(
\frac{(a_0-a_1)(z_2-z_1)}{z_1z_2(z_1-z_2)} +
\frac{a_0(z_1^2-z_2^2)}{z_1^2z_2^2(z_1-z_2)} +
\right) =
}\]
Как мы доказали:
\[\Large{
z_1z_2 = -1
}\]
Также рассмотрим \(z_1 + z_2\):
\[\Large{
z_1+z_2 = \frac{-1-
\cancelto{0}{\sqrt{5}+\sqrt{5}}
-1}{2} =
\frac{-1-1}{2} =
-1
}\]
Подставив значения в выражение, получим:
\[\Large{
= -\left(
a_0 - a_1 +
\frac{a_0(z_1-z_2)(z_1+z_2)}{(z_1-z_2)} +
\right) =
}\]
\[\Large{
= -\left(
\cancelto{0}{a_0 - a_0}
-a_1
\right) = -(-a_1) = a_1, \text{ Q.E.D.}
}\]
Переход индукции
По определению чисел Фибоначчи:
\[\Large{
a_{n+2} = a_{n+1}+a_n
}\]
где:
\[\Large{
a_n = \left(
-\frac{A}{z_1^{n+1}}-\frac{B}{z_2^{n+1}}
\right)
}\]
Подставим это в формулу:
\[\Large{
a_{n+2} = a_{n+1}+a_n =
-\frac{A}{z_1^{n+1}}-\frac{B}{z_2^{n+1}}
-\frac{A}{z_1^{n+2}}-\frac{B}{z_2^{n+2}} =
}\]
Сгруппируем по \(A\) и \(B\):
\[\Large{
= -A \underbrace{\left(
\frac{1}{z_1^{n+1}}+
\frac{1}{z_1^{n+2}}
\right)}_{(I)}
%
-B \underbrace{\left(
\frac{1}{z_2^{n+1}}+
\frac{1}{z_2^{n+2}}
\right)}_{(II)}
}\]
Рассмотрим \((I)\) и \((II)\):
\[\Large{
(I) =
\frac{z_1+1}{z_1^{n+2}}
}\]
\[\Large{
z_1 + 1 =
-\frac{1+\sqrt{5}}{2} + 1 =
\frac{-1-\sqrt{5}+2}{2} =
}\]
\[\Large{
=
\frac{1-\sqrt{5}}{2} =
\frac{(1-\sqrt{5})(1+\sqrt{5})}{2(1+\sqrt{5})} =
}\]
\[\Large{
= \frac{1 - 5}{2(1+\sqrt{5})} =
\frac{-4}{2(1+\sqrt{5})} =
- \frac{2}{1+\sqrt{5}} = \frac{1}{z_1}
}\]
Таким образом:
\[\Large{
(I) = \frac{1}{z_1^{n+3}}
}\]
Аналогично для \((II)\):
\[\Large{
(II) =
\frac{z_2+1}{z_2^{n+2}}
}\]
\[\Large{
z_2 + 1 =
-\frac{1-\sqrt{5}}{2} + 1 =
\frac{-1+\sqrt{5}+2}{2} =
}\]
\[\Large{
= \frac{-1+\sqrt{5}+2}{2} =
\frac{1+\sqrt{5}}{2} =
}\]
\[\Large{
= \frac{(1+\sqrt{5})(1-\sqrt{5})}{2(1-\sqrt{5})} =
\frac{1 - 5}{2(1-\sqrt{5})} =
}\]
\[\Large{
= \frac{-4}{2(1-\sqrt{5})} =
-\frac{2}{1-\sqrt{5}} =
\frac{1}{z_2}
}\]
Подставив это в \((II)\):
\[\Large{
(II) = \frac{1}{z_2^{n+3}}
}\]
Подставляя \((I)\) и \((II)\):
\[\Large{
-A \underbrace{\left(
\frac{1}{z_1^{n+1}}+
\frac{1}{z_1^{n+2}}
\right)}_{(I)}
-B \underbrace{\left(
\frac{1}{z_2^{n+1}}+
\frac{1}{z_2^{n+2}}
\right)}_{(II)} =
}\]
\[\Large{
= -A \frac{1}{z_1^{n+3}}
-B \frac{1}{z_2^{n+3}} =
a_{n+2}, \text{ Q.E.D.}
}\]
Выводы
В данной публикации были рассмотрены:
- получение производящей функции из рекуррентного уравнения;
- разложение функции в ряд для нахождения \(n\)-го члена последовательности;
- доказана верность полученной формулы с помощью математической индукции.
Очевидно, что полезность данной формулы в случае чисел Фибоначчи сомнительна. Но она может служить полезным примером того, как можно решить линейное рекуррентное уравнение.