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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 11: Строка 11:
 
<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>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>
+
Возводя её в квадрат, по определению [[Арифметические действия с формальными степенными рядами#def_mul | произведения формальных степенных рядов]], получаем <tex>B(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: Строка 17:
 
То есть <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>\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>-x</tex> вместо <tex>x</tex> в помощью [[Арифметические действия с формальными степенными рядами#def_in| операции подстановки]], получаем <tex>B'(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>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>

Версия 22:45, 22 мая 2018

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


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


Докажем, что [math]\sum\limits_{i = 0}^{2n} (-1)^i \cdot (i + 1) \cdot (2n + 1 - i) = 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(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'(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]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]