Использование производящих функций для доказательства тождеств — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Создана пустая страница)
 
(Добавлен знак умножения)
 
(не показано 36 промежуточных версий 3 участников)
Строка 1: Строка 1:
 +
С помощью производящих функций можно доказывать различные утверждения о свойствах последовательностей и сумм. Обычно если нужно доказать равенство двух выражений <tex>expr^1_n</tex> и <tex>expr^2_n</tex>, нужно найти производящую функцию последовательности <tex>\{expr^1\}_{n = 1}^{\infty}</tex> и последовательности <tex>\{expr^2\}_{n = 1}^{\infty}</tex> и проверить, что эти производящие функции совпадают. Продемонстрируем применение этого принципа на примерах:
  
 +
В дальнейшем будем обозначать <tex>[x^n]A(x)</tex> коэффициент при <tex>x^n</tex> в формальном степенном ряде <tex>A(x)</tex>
 +
 +
== Пример № 1 ==
 +
 +
{{Задача
 +
|definition = Доказать, что <tex>\sum\limits_{k = 0}^{2n} (-1)^k \cdot (k + 1) \cdot (2n + 1 - k) = n + 1</tex>
 +
}}
 +
 +
Докажем, что <tex>\sum\limits_{k = 0}^{2n} (-1)^k \cdot (k + 1) \cdot (2n + 1 - k) = 1 \cdot (2n + 1) - 2 \cdot (2n) + 3 \cdot (2n - 1) + \ldots + (2n + 1) \cdot 1 = n + 1</tex>
 +
 +
Рассмотрим известную нам производящую функцию
 +
 +
<tex>A(x) = \dfrac{1}{1 - x} = 1 + x + x^2 + \ldots = \sum\limits_{n = 0}^{\infty}x^n</tex>
 +
 +
Возводя её в квадрат, по определению [[Арифметические действия с формальными степенными рядами#def_mul | произведения формальных степенных рядов]], получаем <tex>B_1(x) = A^2(x) = \dfrac{1}{1 - x} \cdot \dfrac{1}{1 - x} = (\sum\limits_{n = 0}^{\infty}x^n) \cdot (\sum\limits_{n = 0}^{\infty}x^n) = </tex>
 +
 +
<tex> = \sum\limits_{n = 0}^{\infty} x^n \cdot \sum\limits_{i = 0}^{n}([x^i]A(x) \cdot [x^{n - i}]A(x)) = \sum\limits_{n = 0}^{\infty} x^n \cdot \sum\limits_{i = 0}^{n}(1 \cdot 1) = \sum\limits_{n = 0}^{\infty} (n + 1) \cdot x^n</tex>
 +
 +
То есть <tex>\dfrac{1}{(1 - x)^2} = \sum\limits_{n = 0}^{\infty} (n + 1) \cdot x^n</tex>
 +
 +
Подставляя в эту производящую функцию <tex>-x</tex> вместо <tex>x</tex> в помощью [[Арифметические действия с формальными степенными рядами#def_in| операции подстановки]], получаем <tex>B_2(x) = \dfrac{1}{(1 - (-x))^2} = \dfrac{1}{(1 + x)^2} = \sum\limits_{n = 0}^{\infty} (n + 1) \cdot (-x)^n = \sum\limits_{n = 0}^{\infty} (-1)^n \cdot (n + 1) \cdot x^n </tex>
 +
 +
Перемножая степенные ряды <tex>B_1</tex> и <tex>B_2</tex>, получаем
 +
 +
<tex>C(x) = \dfrac{1}{(1 - x)^2} \cdot \dfrac{1}{(1 + x)^2} = (\sum\limits_{n = 0}^{\infty} (n + 1) \cdot x^n) \cdot (\sum\limits_{n = 0}^{\infty} (-1)^n \cdot (n + 1) \cdot x^n) = \sum\limits_{n = 0}^{\infty}x^n \cdot \sum\limits_{i = 0}^{n}((i + 1) \cdot (-1)^{n - i} \cdot (n - i + 1))</tex>
 +
 +
Рассмотрим <tex>[x^{2k + 1}]C(x)</tex>
 +
 +
<tex>[x^{2k + 1}]C(x) = \sum\limits_{i = 0}^{2k + 1}((i + 1) \cdot (-1)^{2k + 1 - i} \cdot (2k + 2 - i))</tex>
 +
 +
Рассмотрим <tex>i</tex>-ое и <tex>2k + 1 - i</tex>-ое слагаемые этой суммы. Модуль <tex>i</tex>-ого равен <tex>(i + 1) \cdot (2k + 2 - i)</tex>, а модуль <tex>2k + 1 - i</tex>-ого слагаемого равен <tex>(2k + 1 - i + 1) \cdot (2k + 2 - (2k + 1 - i)) = (2k + 2 - i) \cdot (i + 1)</tex>, то есть слагаемые равны по абсолютной величине. Знак <tex>i</tex>-ого слагаемого определяется выражением <tex>(-1)^{2k + 1 - i} = (-1)^{1 - i}</tex>, а знак <tex>2k + 1 - i</tex>-ого {{---}} выражением <tex>(-1)^{2k + 1 - (2k + 1 - i)} = (-1)^i</tex>, то есть эти слагаемые равны по модулю, но противоположны по знаку.
 +
 +
Так как слагаемых всего <tex>2k + 1 - 0 + 1</tex> (то есть их чётное число), и каждое слагаемое входит в сумму дважды с противоположными знаками, <tex>[x^{2k + 1}]C(x) = 0 ~~~~ \textbf{(1)}</tex>
 +
 +
Рассмотрим <tex>[x^{2k}]C(x)</tex>
 +
 +
<tex>[x^{2k}]C(x) = \sum\limits_{i = 0}^{2k}(i + 1) \cdot (-1)^{2k - i} \cdot (2k + 1 - i) = \sum\limits_{i = 0}^{2k}(i + 1) \cdot (-1)^i \cdot (2k + 1 - i) ~~~~ \textbf{(2)}</tex>
 +
 +
Учитывая <tex>\textbf{(1)}</tex> и <tex>\textbf{(2)}</tex>, получаем, что
 +
 +
<tex>C(x) = \sum\limits_{n = 0}^{\infty}x^{2n} \cdot \sum\limits_{k = 0}^{2n}(k + 1) \cdot (-1)^k \cdot (2n + 1 - k)</tex>
 +
 +
Заметим, что <tex>C(x)</tex> можно разложить в ряд и другим способом.
 +
 +
<tex>C(x) = \dfrac{1}{(1 - x)^2} \cdot \dfrac{1}{(1 + x)^2} = \dfrac{1}{(1 - x)^2 \cdot (1 + x)^2} = \dfrac{1}{(1 - x^2)^2}</tex>
 +
 +
Ранее было получено разложение <tex>\dfrac{1}{(1 - x)^2} = \sum\limits_{n = 0}^{\infty} (n + 1) \cdot x^n</tex>
 +
 +
Подставляя <tex>x^2</tex> вместо <tex>x</tex>, получаем разложение <tex>C(x) = \dfrac{1}{(1 - x^2)^2} = \sum\limits_{n = 0}^{\infty} (n + 1) \cdot x^{2n}</tex>
 +
 +
То есть известно два разложения <tex>C(x)</tex> в формальный степенной ряд: <tex>C(x) = \dfrac{1}{(1 - x^2)^2} = \sum\limits_{n = 0}^{\infty} (n + 1) \cdot x^{2n} = \sum\limits_{n = 0}^{\infty}x^{2n} \cdot \sum\limits_{k = 0}^{2n}(k + 1) \cdot (-1)^k \cdot (2n + 1 - k)</tex>
 +
 +
Тогда <tex>\sum\limits_{k = 0}^{2n} (-1)^k \cdot (k + 1) \cdot (2n + 1 - k) = n + 1</tex>
 +
 +
== Пример № 2 ==
 +
 +
{{Лемма
 +
|id=lemma1
 +
|statement=Пусть последовательность <tex>a_0, a_1, a_2, \ldots, a_n \ldots</tex> порождается производящей функцией <tex>A(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots + a_n \cdot t^n + \ldots = \sum\limits_{n = 0}^{\infty}a_n \cdot t^n</tex>. Тогда последовательность <tex>a_0, a_0 + a_1, a_0 + a_1 + a_2, \ldots, \sum\limits_{i = 0}^{n}a_i, \ldots</tex> порождается производящей функцией <tex>\dfrac{A(t)}{1 - t} = \dfrac{\sum\limits_{n = 0}^{\infty}a_n \cdot t^n}{1 - t}</tex>
 +
|proof= Известно, что <tex>\dfrac{1}{1 - t} = \sum\limits_{n = 0}^{\infty}t^n</tex>
 +
 +
Рассмотрим производящую функцию <tex>\dfrac{A(t)}{1 - t} = A(t) \cdot \dfrac{1}{1 - t} = (\sum\limits_{n = 0}^{\infty}a_n \cdot t^n) \cdot (\sum\limits_{n = 0}^{\infty}1 \cdot t^n) = \sum\limits_{n = 0}^{\infty}t^n \cdot (\sum\limits_{k = 0}^{n} a_k \cdot 1) = \sum\limits_{n = 0}^{\infty}t^n \cdot (\sum\limits_{k = 0}^{n} a_k)</tex>
 +
 +
То есть <tex>[t^n]\dfrac{A(t)}{1 - t} = \sum\limits_{k = 0}^{n} a_k</tex>, то есть <tex>\dfrac{A(t)}{1 - t}</tex> является производящей функцией последовательности <tex>a_0, a_0 + a_1, a_0 + a_1 + a_2, \ldots, \sum\limits_{k = 0}^{n}a_k, \ldots</tex>
 +
}}
 +
 +
{{Определение
 +
|id=fib.
 +
|definition='''Числа Фибоначчи''' {{---}} последовательность чисел, задаваемая рекурентным соотношением <tex>f_0 = f_1 = 1, f_n = f_{n - 1} + f_{n - 2}</tex>, для <tex>n \geqslant 2</tex>.
 +
}}
 +
 +
{{Задача
 +
|definition = Доказать, что <tex>f_0 + f_1 + f_2 + \ldots + f_n = f_{n + 2} - 1</tex>, где <tex>f_n</tex> {{---}} <tex>n</tex>-ое число Фибоначчи
 +
}}
 +
 +
Найдём производящую функцию последовательности <tex>A: f_0, f_0 + f_1, f_0 + f_1 + f_2, \ldots, \sum\limits_{k = 0}^{n} f_k, \ldots</tex>. Согласно утверждению [[Использование производящих функций для доказательства тождеств#lemma1 | леммы]], её производящая функция <tex>\dfrac{F(t)}{1 - t}</tex>, где <tex>F(t)</tex> {{---}} производящая функция последовательности Фибоначчи.
 +
 +
Найдём производящую функцию последовательности <tex>B: f_2 - 1, f_3 - 1, \ldots, f_{n + 2} - 1, \ldots</tex>. Будем искать её в виде <tex>B(t) = \sum\limits_{n = 0}^{\infty} (f_{n + 2} - 1) \cdot t^n = \sum\limits_{n = 0}^{\infty} f_{n + 2} \cdot t^n - \sum\limits_{n = 0}^{\infty} t^n = (f_2 + f_3 \cdot t + f_4 \cdot t^2 + \ldots f_{n + 2} \cdot t^n + \ldots) - \dfrac{1}{1 - t} = </tex>
 +
 +
<tex>= \dfrac{f_2 \cdot t^2 + f_3 \cdot t^3 + f_4 \cdot t^4 + \ldots f_{n + 2} \cdot t^{n + 2} + \ldots}{t^2} - \dfrac{1}{1 - t} = </tex>
 +
 +
<tex> = \dfrac{(f_0 + f_1 \cdot t + f_2 \cdot t^2 + f_3 \cdot t^3 + f_4 \cdot t^4 + \ldots f_{n + 2} \cdot t^{n + 2} + \ldots) - f_1 \cdot t - f_0}{t^2} - \dfrac{1}{1 - t} = </tex>
 +
 +
<tex>= \dfrac{(f_0 + f_1 \cdot t + f_2 \cdot t^2 + f_3 \cdot t^3 + f_4 \cdot t^4 + \ldots f_{n + 2} \cdot t^{n + 2} + \ldots) - t - 1}{t^2} - \dfrac{1}{1 - t} = \dfrac{(\sum\limits_{n = 0}^{\infty} f_n \cdot t^n) - t - 1}{t^2} - \dfrac{1}{1 - t} = </tex>
 +
 +
<tex>= \dfrac{F(t) - t - 1}{t^2} - \dfrac{1}{1 - t}</tex>
 +
 +
Теперь проверим, что производящие функции последовательностей <tex>A</tex> и <tex>B</tex> совпадают.
 +
 +
Согласно [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности#Примеры применения теоремы | теореме о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности]], производящая функция последовательности Фибоначчи имеет вид <tex>F(t) = \dfrac{1}{1 - t - t^2}</tex>
 +
 +
Тогда <tex>A(t) = \dfrac{F(t)}{1 - t} = \dfrac{\dfrac{1}{1 - t - t^2}}{1 - t} = \dfrac{1}{(1 - t - t^2) \cdot (1 - t)}</tex>
 +
 +
<tex>B(t) = \dfrac{F(t) - t - 1}{t^2} - \dfrac{1}{1 - t} = \dfrac{\dfrac{1}{1 - t - t^2} - t - 1}{t^2} - \dfrac{1}{1 - t} = \dfrac{1 - t +t^2 + t^3 - 1 + t + t^2}{(t^2) \cdot (1 - t - t^2)} - \dfrac{1}{1 - t} = \dfrac{2 \cdot t^2 + t^3}{(t^2) \cdot (1 - t - t^2)} - \dfrac{1}{1 - t} = </tex>
 +
 +
<tex> = \dfrac{2 + t}{1 - t - t^2} - \dfrac{1}{1 - t} = \dfrac{(2 + t) \cdot (1 - t) - 1 \cdot (1 - t - t^2)}{(1 - t - t^2) \cdot (1 - t)} =  \dfrac{2 - 2t + t -t^2 - 1 + t + t^2}{(1 - t - t^2) \cdot (1 - t)} = \dfrac{1}{(1 - t - t^2) \cdot (1 - t)}</tex>
 +
 +
Тогда <tex>A(t) = B(t)</tex>, то есть производящие функции последовательностей <tex>f_0, f_0 + f_1, f_0 + f_1 + f_2, \ldots, \sum\limits_{k = 0}^{n} f_k, \ldots</tex> и <tex>f_2 - 1, f_3 - 1, \ldots, f_{n + 2} - 1, \ldots</tex> совпадают, а значит, совпадают и эти последовательности. Поэтому <tex>f_0 + f_1 + f_2 + \ldots + f_n = f_{n + 2} - 1</tex>
 +
 +
== Пример № 3 ==
 +
 +
{{Задача
 +
|definition = Доказать, что <tex>f_0^2+f_1^2+f_2^2+\ldots+f_n^2=f_n \cdot f_{n+1}</tex>.
 +
}}
 +
[[Решение рекуррентных соотношений#.5Bmath.5D3.5B.2Fmath.5D_.D0.BF.D1.80.D0.B8.D0.BC.D0.B5.D1.80 | Известно]], что производящая функция последовательности <tex>f_0^2, f_1^2, \ldots, f_n^2, \ldots</tex> равна <tex>G(z) = \dfrac{1 - z}{1 - 2z - 2z^2 + z^3}.</tex>
 +
 +
Используя [[Использование производящих функций для доказательства тождеств#lemma1 | лемму]] из примера <tex>2</tex>, найдём производящую функцию для последовательности <tex>f_0^2, f_0^2 + f_1^2, f_0^2 + f_1^2 + f_2^2, \ldots</tex>:
 +
<br><tex>A(z) = \dfrac{1 - z}{(1 - 2z - 2z^2 + z^3)(1 - z)} = \dfrac{1}{1 - 2z - 2z^2 + z^3}.</tex><br>
 +
 +
Теперь получим производящую функцию <tex>B(z)</tex> для последовательности, соответствующей правой части <tex>(f_0 \cdot f_1, f_1 \cdot f_2, \ldots)</tex>:
 +
<br><tex>b_n = f_n \cdot f_{n+1} = f_n(f_{n-1} + f_n) = f_{n-1} \cdot f_n + f_n^2 = b_{n-1} + g_n.</tex><br>
 +
 +
<br><tex>
 +
\begin{array}{ll}
 +
b_0 = 1 \\
 +
b_n = b_{n-1} + g_n, \quad n\geqslant1.\\
 +
\end{array}
 +
</tex><br>
 +
 +
Приведём суммы к замкнутому виду:
 +
<br><tex>
 +
\begin{array}{ll}
 +
B(z) = \displaystyle\sum_{n=0}^{\infty}b_nz^n = 1 + \displaystyle\sum_{n=1}^{\infty}(b_{n-1} + g_n)z^n, \\
 +
B(z) = 1 + \displaystyle\sum_{n=1}^{\infty}b_{n-1}z^n + \displaystyle\sum_{n=1}^{\infty}g_nz^n, \\
 +
B(z) = 1 + z\displaystyle\sum_{n=1}^{\infty}b_{n-1}z^{n-1} + \displaystyle\sum_{n=1}^{\infty}g_nz^n, \\
 +
B(z) = 1 + z\displaystyle\sum_{n=0}^{\infty}b_nz^n + (\displaystyle\sum_{n=0}^{\infty}g_nz^n - 1), \\
 +
B(z) = zB(z) + G(z), \\
 +
B(z)(1 - z) = G(z), \\
 +
\end{array}
 +
</tex><br>
 +
откуда получаем замкнутое выражение для производящей функции:
 +
<br><tex>B(z) = \dfrac{G(z)}{1 - z} = \dfrac{1}{1 - 2z - 2z^2 + z^3} = A(z).</tex><br>
 +
 +
Производящие функции <tex>A(z)</tex> и <tex>B(z)</tex> равны <tex>\Rightarrow</tex> почленно равны задаваемые ими последовательности <tex>f_0^2, f_1^2, f_2^2, \ldots</tex> и <tex>f_0 \cdot f_1, f_1 \cdot f_2, f_2 \cdot f_3, \ldots</tex>, а значит, и исходное равенство <tex>f_0^2+f_1^2+f_2^2+\ldots+f_n^2=f_n \cdot f_{n+1}</tex> выполняется.
 +
 +
==См. также==
 +
* [[Арифметические действия с формальными степенными рядами| Арифметические действия с формальными степенными рядами]]
 +
* [[Производящая функция| Производящая функция]]
 +
* [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности | Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности]]
 +
 +
== Источники информации ==
 +
* Н. Я. Виленкин {{---}} Комбинаторика, стр 190
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Комбинаторика]]
 +
[[Категория: Производящие функции]]

Текущая версия на 14:12, 10 июня 2019

С помощью производящих функций можно доказывать различные утверждения о свойствах последовательностей и сумм. Обычно если нужно доказать равенство двух выражений [math]expr^1_n[/math] и [math]expr^2_n[/math], нужно найти производящую функцию последовательности [math]\{expr^1\}_{n = 1}^{\infty}[/math] и последовательности [math]\{expr^2\}_{n = 1}^{\infty}[/math] и проверить, что эти производящие функции совпадают. Продемонстрируем применение этого принципа на примерах:

В дальнейшем будем обозначать [math][x^n]A(x)[/math] коэффициент при [math]x^n[/math] в формальном степенном ряде [math]A(x)[/math]

Пример № 1[править]

Задача:
Доказать, что [math]\sum\limits_{k = 0}^{2n} (-1)^k \cdot (k + 1) \cdot (2n + 1 - k) = n + 1[/math]


Докажем, что [math]\sum\limits_{k = 0}^{2n} (-1)^k \cdot (k + 1) \cdot (2n + 1 - k) = 1 \cdot (2n + 1) - 2 \cdot (2n) + 3 \cdot (2n - 1) + \ldots + (2n + 1) \cdot 1 = n + 1[/math]

Рассмотрим известную нам производящую функцию

[math]A(x) = \dfrac{1}{1 - x} = 1 + x + x^2 + \ldots = \sum\limits_{n = 0}^{\infty}x^n[/math]

Возводя её в квадрат, по определению произведения формальных степенных рядов, получаем [math]B_1(x) = A^2(x) = \dfrac{1}{1 - x} \cdot \dfrac{1}{1 - x} = (\sum\limits_{n = 0}^{\infty}x^n) \cdot (\sum\limits_{n = 0}^{\infty}x^n) = [/math]

[math] = \sum\limits_{n = 0}^{\infty} x^n \cdot \sum\limits_{i = 0}^{n}([x^i]A(x) \cdot [x^{n - i}]A(x)) = \sum\limits_{n = 0}^{\infty} x^n \cdot \sum\limits_{i = 0}^{n}(1 \cdot 1) = \sum\limits_{n = 0}^{\infty} (n + 1) \cdot x^n[/math]

То есть [math]\dfrac{1}{(1 - x)^2} = \sum\limits_{n = 0}^{\infty} (n + 1) \cdot x^n[/math]

Подставляя в эту производящую функцию [math]-x[/math] вместо [math]x[/math] в помощью операции подстановки, получаем [math]B_2(x) = \dfrac{1}{(1 - (-x))^2} = \dfrac{1}{(1 + x)^2} = \sum\limits_{n = 0}^{\infty} (n + 1) \cdot (-x)^n = \sum\limits_{n = 0}^{\infty} (-1)^n \cdot (n + 1) \cdot x^n [/math]

Перемножая степенные ряды [math]B_1[/math] и [math]B_2[/math], получаем

[math]C(x) = \dfrac{1}{(1 - x)^2} \cdot \dfrac{1}{(1 + x)^2} = (\sum\limits_{n = 0}^{\infty} (n + 1) \cdot x^n) \cdot (\sum\limits_{n = 0}^{\infty} (-1)^n \cdot (n + 1) \cdot x^n) = \sum\limits_{n = 0}^{\infty}x^n \cdot \sum\limits_{i = 0}^{n}((i + 1) \cdot (-1)^{n - i} \cdot (n - i + 1))[/math]

Рассмотрим [math][x^{2k + 1}]C(x)[/math]

[math][x^{2k + 1}]C(x) = \sum\limits_{i = 0}^{2k + 1}((i + 1) \cdot (-1)^{2k + 1 - i} \cdot (2k + 2 - i))[/math]

Рассмотрим [math]i[/math]-ое и [math]2k + 1 - i[/math]-ое слагаемые этой суммы. Модуль [math]i[/math]-ого равен [math](i + 1) \cdot (2k + 2 - i)[/math], а модуль [math]2k + 1 - i[/math]-ого слагаемого равен [math](2k + 1 - i + 1) \cdot (2k + 2 - (2k + 1 - i)) = (2k + 2 - i) \cdot (i + 1)[/math], то есть слагаемые равны по абсолютной величине. Знак [math]i[/math]-ого слагаемого определяется выражением [math](-1)^{2k + 1 - i} = (-1)^{1 - i}[/math], а знак [math]2k + 1 - i[/math]-ого — выражением [math](-1)^{2k + 1 - (2k + 1 - i)} = (-1)^i[/math], то есть эти слагаемые равны по модулю, но противоположны по знаку.

Так как слагаемых всего [math]2k + 1 - 0 + 1[/math] (то есть их чётное число), и каждое слагаемое входит в сумму дважды с противоположными знаками, [math][x^{2k + 1}]C(x) = 0 ~~~~ \textbf{(1)}[/math]

Рассмотрим [math][x^{2k}]C(x)[/math]

[math][x^{2k}]C(x) = \sum\limits_{i = 0}^{2k}(i + 1) \cdot (-1)^{2k - i} \cdot (2k + 1 - i) = \sum\limits_{i = 0}^{2k}(i + 1) \cdot (-1)^i \cdot (2k + 1 - i) ~~~~ \textbf{(2)}[/math]

Учитывая [math]\textbf{(1)}[/math] и [math]\textbf{(2)}[/math], получаем, что

[math]C(x) = \sum\limits_{n = 0}^{\infty}x^{2n} \cdot \sum\limits_{k = 0}^{2n}(k + 1) \cdot (-1)^k \cdot (2n + 1 - k)[/math]

Заметим, что [math]C(x)[/math] можно разложить в ряд и другим способом.

[math]C(x) = \dfrac{1}{(1 - x)^2} \cdot \dfrac{1}{(1 + x)^2} = \dfrac{1}{(1 - x)^2 \cdot (1 + x)^2} = \dfrac{1}{(1 - x^2)^2}[/math]

Ранее было получено разложение [math]\dfrac{1}{(1 - x)^2} = \sum\limits_{n = 0}^{\infty} (n + 1) \cdot x^n[/math]

Подставляя [math]x^2[/math] вместо [math]x[/math], получаем разложение [math]C(x) = \dfrac{1}{(1 - x^2)^2} = \sum\limits_{n = 0}^{\infty} (n + 1) \cdot x^{2n}[/math]

То есть известно два разложения [math]C(x)[/math] в формальный степенной ряд: [math]C(x) = \dfrac{1}{(1 - x^2)^2} = \sum\limits_{n = 0}^{\infty} (n + 1) \cdot x^{2n} = \sum\limits_{n = 0}^{\infty}x^{2n} \cdot \sum\limits_{k = 0}^{2n}(k + 1) \cdot (-1)^k \cdot (2n + 1 - k)[/math]

Тогда [math]\sum\limits_{k = 0}^{2n} (-1)^k \cdot (k + 1) \cdot (2n + 1 - k) = n + 1[/math]

Пример № 2[править]

Лемма:
Пусть последовательность [math]a_0, a_1, a_2, \ldots, a_n \ldots[/math] порождается производящей функцией [math]A(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots + a_n \cdot t^n + \ldots = \sum\limits_{n = 0}^{\infty}a_n \cdot t^n[/math]. Тогда последовательность [math]a_0, a_0 + a_1, a_0 + a_1 + a_2, \ldots, \sum\limits_{i = 0}^{n}a_i, \ldots[/math] порождается производящей функцией [math]\dfrac{A(t)}{1 - t} = \dfrac{\sum\limits_{n = 0}^{\infty}a_n \cdot t^n}{1 - t}[/math]
Доказательство:
[math]\triangleright[/math]

Известно, что [math]\dfrac{1}{1 - t} = \sum\limits_{n = 0}^{\infty}t^n[/math]

Рассмотрим производящую функцию [math]\dfrac{A(t)}{1 - t} = A(t) \cdot \dfrac{1}{1 - t} = (\sum\limits_{n = 0}^{\infty}a_n \cdot t^n) \cdot (\sum\limits_{n = 0}^{\infty}1 \cdot t^n) = \sum\limits_{n = 0}^{\infty}t^n \cdot (\sum\limits_{k = 0}^{n} a_k \cdot 1) = \sum\limits_{n = 0}^{\infty}t^n \cdot (\sum\limits_{k = 0}^{n} a_k)[/math]

То есть [math][t^n]\dfrac{A(t)}{1 - t} = \sum\limits_{k = 0}^{n} a_k[/math], то есть [math]\dfrac{A(t)}{1 - t}[/math] является производящей функцией последовательности [math]a_0, a_0 + a_1, a_0 + a_1 + a_2, \ldots, \sum\limits_{k = 0}^{n}a_k, \ldots[/math]
[math]\triangleleft[/math]


Определение:
Числа Фибоначчи — последовательность чисел, задаваемая рекурентным соотношением [math]f_0 = f_1 = 1, f_n = f_{n - 1} + f_{n - 2}[/math], для [math]n \geqslant 2[/math].


Задача:
Доказать, что [math]f_0 + f_1 + f_2 + \ldots + f_n = f_{n + 2} - 1[/math], где [math]f_n[/math][math]n[/math]-ое число Фибоначчи


Найдём производящую функцию последовательности [math]A: f_0, f_0 + f_1, f_0 + f_1 + f_2, \ldots, \sum\limits_{k = 0}^{n} f_k, \ldots[/math]. Согласно утверждению леммы, её производящая функция [math]\dfrac{F(t)}{1 - t}[/math], где [math]F(t)[/math] — производящая функция последовательности Фибоначчи.

Найдём производящую функцию последовательности [math]B: f_2 - 1, f_3 - 1, \ldots, f_{n + 2} - 1, \ldots[/math]. Будем искать её в виде [math]B(t) = \sum\limits_{n = 0}^{\infty} (f_{n + 2} - 1) \cdot t^n = \sum\limits_{n = 0}^{\infty} f_{n + 2} \cdot t^n - \sum\limits_{n = 0}^{\infty} t^n = (f_2 + f_3 \cdot t + f_4 \cdot t^2 + \ldots f_{n + 2} \cdot t^n + \ldots) - \dfrac{1}{1 - t} = [/math]

[math]= \dfrac{f_2 \cdot t^2 + f_3 \cdot t^3 + f_4 \cdot t^4 + \ldots f_{n + 2} \cdot t^{n + 2} + \ldots}{t^2} - \dfrac{1}{1 - t} = [/math]

[math] = \dfrac{(f_0 + f_1 \cdot t + f_2 \cdot t^2 + f_3 \cdot t^3 + f_4 \cdot t^4 + \ldots f_{n + 2} \cdot t^{n + 2} + \ldots) - f_1 \cdot t - f_0}{t^2} - \dfrac{1}{1 - t} = [/math]

[math]= \dfrac{(f_0 + f_1 \cdot t + f_2 \cdot t^2 + f_3 \cdot t^3 + f_4 \cdot t^4 + \ldots f_{n + 2} \cdot t^{n + 2} + \ldots) - t - 1}{t^2} - \dfrac{1}{1 - t} = \dfrac{(\sum\limits_{n = 0}^{\infty} f_n \cdot t^n) - t - 1}{t^2} - \dfrac{1}{1 - t} = [/math]

[math]= \dfrac{F(t) - t - 1}{t^2} - \dfrac{1}{1 - t}[/math]

Теперь проверим, что производящие функции последовательностей [math]A[/math] и [math]B[/math] совпадают.

Согласно теореме о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности, производящая функция последовательности Фибоначчи имеет вид [math]F(t) = \dfrac{1}{1 - t - t^2}[/math]

Тогда [math]A(t) = \dfrac{F(t)}{1 - t} = \dfrac{\dfrac{1}{1 - t - t^2}}{1 - t} = \dfrac{1}{(1 - t - t^2) \cdot (1 - t)}[/math]

[math]B(t) = \dfrac{F(t) - t - 1}{t^2} - \dfrac{1}{1 - t} = \dfrac{\dfrac{1}{1 - t - t^2} - t - 1}{t^2} - \dfrac{1}{1 - t} = \dfrac{1 - t +t^2 + t^3 - 1 + t + t^2}{(t^2) \cdot (1 - t - t^2)} - \dfrac{1}{1 - t} = \dfrac{2 \cdot t^2 + t^3}{(t^2) \cdot (1 - t - t^2)} - \dfrac{1}{1 - t} = [/math]

[math] = \dfrac{2 + t}{1 - t - t^2} - \dfrac{1}{1 - t} = \dfrac{(2 + t) \cdot (1 - t) - 1 \cdot (1 - t - t^2)}{(1 - t - t^2) \cdot (1 - t)} = \dfrac{2 - 2t + t -t^2 - 1 + t + t^2}{(1 - t - t^2) \cdot (1 - t)} = \dfrac{1}{(1 - t - t^2) \cdot (1 - t)}[/math]

Тогда [math]A(t) = B(t)[/math], то есть производящие функции последовательностей [math]f_0, f_0 + f_1, f_0 + f_1 + f_2, \ldots, \sum\limits_{k = 0}^{n} f_k, \ldots[/math] и [math]f_2 - 1, f_3 - 1, \ldots, f_{n + 2} - 1, \ldots[/math] совпадают, а значит, совпадают и эти последовательности. Поэтому [math]f_0 + f_1 + f_2 + \ldots + f_n = f_{n + 2} - 1[/math]

Пример № 3[править]

Задача:
Доказать, что [math]f_0^2+f_1^2+f_2^2+\ldots+f_n^2=f_n \cdot f_{n+1}[/math].

Известно, что производящая функция последовательности [math]f_0^2, f_1^2, \ldots, f_n^2, \ldots[/math] равна [math]G(z) = \dfrac{1 - z}{1 - 2z - 2z^2 + z^3}.[/math]

Используя лемму из примера [math]2[/math], найдём производящую функцию для последовательности [math]f_0^2, f_0^2 + f_1^2, f_0^2 + f_1^2 + f_2^2, \ldots[/math]:
[math]A(z) = \dfrac{1 - z}{(1 - 2z - 2z^2 + z^3)(1 - z)} = \dfrac{1}{1 - 2z - 2z^2 + z^3}.[/math]

Теперь получим производящую функцию [math]B(z)[/math] для последовательности, соответствующей правой части [math](f_0 \cdot f_1, f_1 \cdot f_2, \ldots)[/math]:
[math]b_n = f_n \cdot f_{n+1} = f_n(f_{n-1} + f_n) = f_{n-1} \cdot f_n + f_n^2 = b_{n-1} + g_n.[/math]


[math] \begin{array}{ll} b_0 = 1 \\ b_n = b_{n-1} + g_n, \quad n\geqslant1.\\ \end{array} [/math]

Приведём суммы к замкнутому виду:
[math] \begin{array}{ll} B(z) = \displaystyle\sum_{n=0}^{\infty}b_nz^n = 1 + \displaystyle\sum_{n=1}^{\infty}(b_{n-1} + g_n)z^n, \\ B(z) = 1 + \displaystyle\sum_{n=1}^{\infty}b_{n-1}z^n + \displaystyle\sum_{n=1}^{\infty}g_nz^n, \\ B(z) = 1 + z\displaystyle\sum_{n=1}^{\infty}b_{n-1}z^{n-1} + \displaystyle\sum_{n=1}^{\infty}g_nz^n, \\ B(z) = 1 + z\displaystyle\sum_{n=0}^{\infty}b_nz^n + (\displaystyle\sum_{n=0}^{\infty}g_nz^n - 1), \\ B(z) = zB(z) + G(z), \\ B(z)(1 - z) = G(z), \\ \end{array} [/math]
откуда получаем замкнутое выражение для производящей функции:
[math]B(z) = \dfrac{G(z)}{1 - z} = \dfrac{1}{1 - 2z - 2z^2 + z^3} = A(z).[/math]

Производящие функции [math]A(z)[/math] и [math]B(z)[/math] равны [math]\Rightarrow[/math] почленно равны задаваемые ими последовательности [math]f_0^2, f_1^2, f_2^2, \ldots[/math] и [math]f_0 \cdot f_1, f_1 \cdot f_2, f_2 \cdot f_3, \ldots[/math], а значит, и исходное равенство [math]f_0^2+f_1^2+f_2^2+\ldots+f_n^2=f_n \cdot f_{n+1}[/math] выполняется.

См. также[править]

Источники информации[править]

  • Н. Я. Виленкин — Комбинаторика, стр 190