Изменения

|definition = Доказать, что <tex>\sum\limits_{i k = 0}^{2n} (-1)^i k \cdot (i k + 1) \cdot (2n + 1 - ik) = n + 1</tex>

Докажем, что <tex>\sum\limits_{i k = 0}^{2n} (-1)^i k \cdot (i k + 1) \cdot (2n + 1 - ik) = 1 \cdot (2n + 1) - 2 \cdot (2n) + 3 \cdot (2n - 1) + \ldots + (2n + 1) \cdot 1 = n + 1</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>-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> ==См. также==* [[Арифметические действия с формальными степенными рядами| Арифметические действия с формальными степенными рядами]]* [[Производящая функция| Производящая функция]]* [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности | Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности]] == Источники информации ==* Н. Я. Виленкин {{---}} Комбинаторика, стр 190 [[Категория: Дискретная математика и алгоритмы]][[Категория: Комбинаторика]][[Категория: Производящие функции]]