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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 60: Строка 60:
 
|id=lemma1  
 
|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>
 
|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>
+
|proof= По определению [[Арифметические действия с формальными степенными рядами#div | деления формальных степенных рядов]], известно, что  
 +
<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>\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>
 
То есть <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>-ое число Фибоначчи
+
|definition = Доказать, что <tex>f_0 + f_1 + f_2 \ldots f_n = f_{n + 2} - 1</tex>, где <tex>f_n</tex> {{---}} <tex>n</tex>-ое число Числа Фибоначчи
 
}}
 
}}
  
Строка 99: Строка 95:
  
 
Тогда <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>
 
Тогда <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> выполняется.
 
  
 
==См. также==
 
==См. также==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)