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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 77: Строка 77:
  
 
<tex>= \dfrac{F(t) - 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> совпадают.
 +
 +
[[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности#Примеры применения теоремы]]

Версия 20:42, 26 мая 2018

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


Задача:
Доказать, что [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{(1)}[/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]

Лемма:
Пусть последовательность [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 + 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] совпадают.

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности#Примеры применения теоремы