Использование производящих функций для доказательства тождеств — различия между версиями
(→Пример № 2) (Метки: правка с мобильного устройства, правка из мобильной версии) |
|||
(не показано 20 промежуточных версий 1 участника) | |||
Строка 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> | В дальнейшем будем обозначать <tex>[x^n]A(x)</tex> коэффициент при <tex>x^n</tex> в формальном степенном ряде <tex>A(x)</tex> | ||
+ | |||
+ | == Пример № 1 == | ||
{{Задача | {{Задача | ||
Строка 11: | Строка 15: | ||
<tex>A(x) = \dfrac{1}{1 - x} = 1 + x + x^2 + \ldots = \sum\limits_{n = 0}^{\infty}x^n</tex> | <tex>A(x) = \dfrac{1}{1 - x} = 1 + x + x^2 + \ldots = \sum\limits_{n = 0}^{\infty}x^n</tex> | ||
− | Возводя её в квадрат, по определению [[Арифметические действия с формальными степенными рядами#def_mul | произведения формальных степенных рядов]], получаем <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> = \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> | ||
Строка 17: | Строка 21: | ||
То есть <tex>\dfrac{1}{(1 - x)^2} = \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> | + | Подставляя в эту производящую функцию <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>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> | ||
Строка 27: | Строка 31: | ||
<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>[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>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>2k + 1 - 0 + 1</tex> (то есть их чётное число), и каждое слагаемое входит в сумму дважды с противоположными знаками, <tex>[x^{2k + 1}]C(x) = 0 ~~~~ \textbf{(1)}</tex> | ||
Строка 35: | Строка 39: | ||
<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>[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{( | + | Учитывая <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) = \sum\limits_{n = 0}^{\infty}x^{2n} \cdot \sum\limits_{k = 0}^{2n}(k + 1) \cdot (-1)^k \cdot (2n + 1 - k)</tex> | ||
Строка 50: | Строка 54: | ||
Тогда <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) = 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> | ||
+ | |||
+ | ==См. также== | ||
+ | * [[Арифметические действия с формальными степенными рядами| Арифметические действия с формальными степенными рядами]] | ||
+ | * [[Производящая функция| Производящая функция]] | ||
+ | * [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности | Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности]] | ||
+ | |||
+ | == Источники информации == | ||
+ | * Н. Я. Виленкин {{---}} Комбинаторика, стр 190 | ||
+ | |||
+ | [[Категория: Дискретная математика и алгоритмы]] | ||
+ | [[Категория: Комбинаторика]] | ||
+ | [[Категория: Производящие функции]] |
Версия 14:13, 31 мая 2018
С помощью производящих функций можно доказывать различные утверждения о свойствах последовательностей и сумм. Обычно если нужно доказать равенство двух выражений
и , нужно найти производящую функцию последовательности и последовательности и проверить, что эти производящие функции совпадают. Продемонстрируем применение этого принципа на примерах:В дальнейшем будем обозначать
коэффициент при в формальном степенном рядеПример № 1
Задача: |
Доказать, что |
Докажем, что
Рассмотрим известную нам производящую функцию
Возводя её в квадрат, по определению произведения формальных степенных рядов, получаем
То есть
Подставляя в эту производящую функцию операции подстановки, получаем
вместо в помощьюПеремножая степенные ряды
и , получаем
Рассмотрим
Рассмотрим
-ое и -ое слагаемые этой суммы. Модуль -ого равен , а модуль -ого слагаемого равен , то есть слагаемые равны по абсолютной величине. Знак -ого слагаемого определяется выражением , а знак -ого — выражением , то есть эти слагаемые равны по модулю, но противоположны по знаку.Так как слагаемых всего
(то есть их чётное число), и каждое слагаемое входит в сумму дважды с противоположными знаками,Рассмотрим
Учитывая
и , получаем, что
Заметим, что
можно разложить в ряд и другим способом.
Ранее было получено разложение
Подставляя
вместо , получаем разложениеТо есть известно два разложения
в формальный степенной ряд:Тогда
Пример № 2
Лемма: |
Пусть последовательность порождается производящей функцией . Тогда последовательность порождается производящей функцией |
Доказательство: |
Известно, что Рассмотрим производящую функцию То есть , то есть является производящей функцией последовательности |
Определение: |
Числа Фибоначчи — последовательность чисел, задаваемая рекурентным соотношением | , для .
Задача: |
Доказать, что | , где — -ое число Фибоначчи
Найдём производящую функцию последовательности . Согласно утверждению леммы, её производящая функция , где — производящая функция последовательности Фибоначчи.
Найдём производящую функцию последовательности
. Будем искать её в виде
Теперь проверим, что производящие функции последовательностей
и совпадают.Согласно теореме о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности, производящая функция последовательности Фибоначчи имеет вид
Тогда
Тогда
, то есть производящие функции последовательностей и совпадают, а значит, совпадают и эти последовательности. ПоэтомуСм. также
- Арифметические действия с формальными степенными рядами
- Производящая функция
- Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности
Источники информации
- Н. Я. Виленкин — Комбинаторика, стр 190