%\documentclass{article}
%
%\usepackage[utf8]{inputenc}
%\usepackage[TS1,T2A]{fontenc}
%\usepackage[russian]{babel}
%\usepackage{amsmath}
%\usepackage{amsfonts}
%\usepackage{amssymb}
%\usepackage{amsthm}
%
%\hoffset=-3cm
%\textwidth=18cm
%\voffset=-3cm
%\textheight=26cm
%
%\date{2010-02-19}
%\title{Лекции по дискретке}
%\author{Зайцев Вадим}
%
%\begin{document}
%\maketitle

\subsubsection{Лемма 15}
	Производящая ф-ия для последовательности чисел Фибоначчи $ \{ f_n \}_n^\infty$ имеет вид $ \displaystyle F(t) = \frac{1}{1-t-t^2}$
\begin{proof}\hfil\\
	$ \displaystyle  F(t) = \sum_{n=0}^\infty f_n t^n =
	1+t+\sum_{n=2}^\infty (f_{n-1}+f_{n-2})t^n =
	1+t+\sum_{n=2}^\infty f_{n-1} t^n + \sum_{n=2}^\infty f_{n-2}t^n =\\=
	1 + t\sum_{n=1}^\infty f_{n-1}t^{n-1} + t^2\sum_{n=2}^\infty f_{n-2}t^{n-2} =
	1 + tF(t) + t^2F(t) \Rightarrow F(t) = \frac{1}{1-t-t^2}$
\end{proof}

\subsubsection{Теорема 17}
	$ \displaystyle  \forall n \ge 0 \quad f_n = \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n+1} - \left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right)$
	\begin{proof}\hfil\\
		$ \displaystyle  t^2 +t-1 = 0\\
		t_1 = \frac{\sqrt{5}-1}{2}\\
		t_2 = \frac{-\sqrt{5}-1}{2}$\\
		
		$ \displaystyle F(t) = \frac{-1}{(t-t_1)(t-t_2)} = \frac{1}{\sqrt{5}}\left( \frac{1}{t-t_2} - \frac{1}{t-t_1} \right) =
		\frac{1}{\sqrt{5}t_1}\left(\frac{1}{1-\frac{t}{t_1}}\right) - \frac{1}{\sqrt{5}t_2}\left(\frac{1}{1-\frac{t}{t_2}}\right) =\\=$
		$ \displaystyle \frac{1}{\sqrt{5}t_1}\left(1 + \frac{t}{t_1} + \frac{t^2}{t_1^2} +  \ldots \right) -
		\frac{1}{\sqrt{5}t_2}\left(1 + \frac{t}{t_2}+ \frac{t^2}{t_2^2} +  \ldots \right) $\\
		
		$ \displaystyle f_n = \frac{1}{\sqrt{5}}\left(\frac{1}{t_1^{n+1}} - \frac{1}{t_2^{n+1}}\right) =
		\frac{1}{\sqrt{5}}\cdot \frac{t_2^{n+1} - t_1^{n+1}}{t_1^{n+1}\cdot t_2^{n+1}} =
		\frac{(-1)^{n+1}}{\sqrt{5}}(t_2^{n+1} - t_1^{n+1}) = \\ =
		\frac{(-1)^{n+1}}{\sqrt(5)}\left( \left(\frac{-\sqrt{5}-1}{2}\right)^{n+1} - \left(\frac{\sqrt{5}-1}{2}\right)^{n+1} \right) =
		\frac{1}{\sqrt(5)}\left( \left(\frac{\sqrt{5}+1}{2}\right)^{n+1} - \left(\frac{1-\sqrt{5}}{2}\right)^{n+1} \right) $
	\end{proof}

\subsubsection{Определение}
	Линейное однородное рекуррентное соотношение порядка $k$ для последовательности $\{ a_n \}_{n=0}^\infty$ выглядит:\\
	$(4) \quad a_{n+k} + p_1 a_{n+k-1} +  \ldots  + p_k a_n = 0, \quad p_k \ne 0$.\\
	Если последовательность $\{ a_n \}_{n=0}^\infty$ удовлетворяет $(4)\, \forall n$ она наз-ся однородной возвратной последовательностью порядка $k$.\\
	$ f_{n+2} - f_{n+1} - f_n = 0 \Rightarrow \{ f_n \}_{n=0}^\infty$ - однородная возврат. послед. порядка 2.\\
	
\subsubsection{Теорема 18}
	Если последовательность $\{ a_n \}_{n=0}^\infty$ удовлетворяет $(4)\, \forall n, \, n\ge 0$, то производящая ф-ия $A(T)$ этой последовательности имеет вид:\\
	$ \displaystyle A(t) = \frac{C(t)}{K(t)}$, где $ K(t) = 1 + p_1 t + p_2 t^2 +  \ldots + p_k t^k$, $C(t)$ - многочлен степени, не превосходящей $k-1$.
	\begin{proof}\hfil\\
		Пусть $ \displaystyle A(t) = \sum_{n=0}^\infty a_n t^n$.\\
		\begin{eqnarray*}
			C(t) = A(t)\cdot K(t) = a_0 + a_1t + a_2t^2 +  &\ldots&  + a_kt^k + a_{k+1}t^{k+1} + \\
			+ \ldots  + a_0 p_1t + a_1 p_1 t^2 + &\ldots&  + a_{k-1}p_1 t^k + a_kp_1t^{k+1} + \\
			+ \ldots  + a_0p_2t^2 +  &\ldots&  + a_{k-2}p_2t^k + a_{k-1}p_2t^{k+1} + \\
			+ &\ldots&  + a_0 p_k t^k + a_1 p_k t^{k+1} +  \ldots
		\end{eqnarray*}
		(Все столбцы после первого многоточия будут зануляться, а до первого в сумме образуют $C(t)$.)
	\end{proof}
		
\subsubsection{Определение}
	$ f(t) = t^k + p_1 t^{k-1} +  \ldots  + p_k$ - характеристичесий многочлен для $(4)$.\\
	$ f(t) = (t-\lambda_1)^{r_1} \cdot  \ldots  \cdot ( t-\lambda_s)^{r_s}, \quad \lambda_i \ne \lambda_j,i\ne j, \sum r_i = k$\\
	$ \displaystyle  K(t) = t^k f\left(\frac{1}{t}\right) = t^k \prod_{i=1}^s \left(\frac{1}{t} - \lambda_i\right)^{r_i} 
	= \prod_{i=1}^s \left(\frac{1}{t} - t\lambda_i\right)^{r_i} $\\
	$ \displaystyle  A(t) = \frac{C(t)}{ \displaystyle \prod_{i=1}^s (1 - t\lambda_i)^{r_i}} =
	\sum_{i=1}^s \sum_{j=1}^{r_i} \frac{B_{ij}}{ (1 - t \lambda_i)^j }$\\
	$  \displaystyle (1 - t\lambda_i)^{-j} = 1 + \sum_{n=1}^\infty \binom{-j}{n} (-\lambda_i t)^n =
	1 + \sum_{n=1}^\infty \frac{(-j)(-j-1) \ldots (-j-n+1)}{n!} (-1)^n \lambda_i^n t^n =\\=
	1 + \sum_{n=1}^\infty \frac{j(j+1) \ldots (j+n-1)}{n!} \lambda_i^n t^n =
	1 + \sum_{n=1}^\infty \binom{j+n-1}{n} \lambda_i^n t^n = 1 + \sum_{n=1}^\infty \binom{j+n-1}{j-1} \lambda_i^n t^n$\\
	$ \displaystyle A(t) \sum_{i=1}^s \sum_{j=1}^{r_i} B_{ij}\left( 1 + \sum_{n=1}^\infty \binom{j+n-1}{j-1} \lambda_i^n t^n \right) =
	a_0 + \sum_{n=1}^\infty \left( \sum_{j=1}^{r_i} \lambda_i^n \sum_{i=1}^{s} B_{ij} \binom{j+n-1}{j-1} \right) t^n$.\\
	При этом $\binom{j+n-1}{j-1}$ - многолчен степени, не прев. $n-j+1$.

\subsubsection{Теорема 19}
	Пусть $ \{ a_n \}_{n=0}^\infty$ - линейная, однородная, возвратная последовательность, удовлетворяющая $(4)$. Тогда\\
	$ \displaystyle a_n = \sum_{i=1}^s Q_i(n) \lambda_i^n$, где $\lambda_1, \ldots \lambda_s$ - корни харак. мног. кратного $r_1, \ldots ,r_s$ соответственно.\\
	$ Q_i(t)$ - многолчен степени, не превосходящей $r_i-1$, который находится из начальных условий.

\subsubsection{Следствие 1}
	Если характер. маногочлен имеет только простые корни $\lambda_1, \ldots ,\lambda_k$, то $a_n = c_1\lambda_1^n + c_2\lambda_2^n +  \ldots  + c_k \lambda_k^n$.
\subsubsection{Пример 0}
	Применим это к числам фиббоначи:
	$f_1: \quad \lambda^2-\lambda-1-1 \quad \lambda_1 = \frac{1+\sqrt{5}}{2} \quad \lambda_2 = \frac{1-\sqrt{5}}{2}\\
	f_n = c_1 \cdot (\frac{1+\sqrt{5}}{2})^n + c_2\cdot (\frac{1-\sqrt{5}}{2})^n$
\subsubsection{Пример 1}
	Найти общее решение $ a_{n+1} + 2a_{n+2} + a_n =0$\\
	\textbf{Решение}: характер. многочлен $ x^4 + 2x^2 + 1 =0$\\
	$(x^2+1)^2 = 0 \quad x_1 = -i, \quad x_2 = i$\\
	$a_n(c_1 + c_2n)(-i)^n + (c_3 + c_4n)i^n$.
	
\subsubsection{Следствие 2}
	Если характер. маногочлен имеет 1 корень $\lambda$ кратности $k$, то $ a_n = (c_1 + c_2n + c_3n^2 +  \ldots  + c_kn^{k-1})\lambda^n$.
	
\subsubsection{Определение}
	Линейное неоднородное рекуррентное соотношение для послед.$ \{ a_n \}_{n=0}^\infty$ :\\
	$ (5) \quad  a_{n+k} + p_1 a_{n+k-1} +  \ldots  + p_k a_n = f(n)\\
	\{ a_n \}_{n=0}^\infty $  - удовлетворяет $(5)$ $\forall n \ge 0 \Rightarrow $ линейная неоднородная возвратная последовательности.\\
	Общее решение неоднородного линейного рекуррентного соотношения равно общему решению однородного  + частное решение неоднородного.\\
	Напр., если какой-нить $f(n) = p(n)\cdot \lambda^n$, то пытаемся найти частное решение в виде $ (c_1 + c_2 n +  \ldots  + c_{q+1}n^q)\lambda^n$.

\subsubsection{Упражнение}
$ \displaystyle  \{ S(n,m) \}_{n=0}^\infty \Rightarrow A(t) = \frac{t^m}{(1-t)(1-2t) \ldots (1-mt)}$\\
$ \{ a_n \}_{n=0}^\infty$ - быстро растёт, $ \{ \frac{a_n}{n!} \}_{n=0}^\infty$\\

\subsubsection{Определение}
	Степенной ряд $ \displaystyle  \widehat{A}(t) = \sum_{n=0}^\infty a_n \frac{t^n}{n!}$ - экспонциональная производящая ф-ия послед. $ \{ a_n \}_{n=0}^\infty$.
	
\subsubsection{Лемма 16}
	Пусть $\widehat{A}(t)$ - экспоненциальная производящая ф-ия послед. $ \{ a_n \}_{n=0}^\infty$, Тогда:
	\begin{enumerate}
		\item $t\cdot\widehat{A}(t)$ - экспонц. производящая ф-ия $ \{ n\cdot a_n \}_{n=0}^\infty$
		\item $\widehat{A'}(t)$ - экспонци. производ. ф-ия послед. $\{ \cdot a_{n+1} \}_{n=0}^\infty$
		\item $ \displaystyle \int_0^t \widehat{A}(t)$ - экспонци. производ. ф-ия послед. $0, a_0, a_1, \ldots $
	\end{enumerate}
\begin{proof}
	Упражнение.
\end{proof}

\subsubsection{Лемма 17}
	Пусть $\widehat{A}(t),\widehat{B}(t)$ - экспоненциальная производящая ф-ия послед. $ \{ a_n \}_{n=0}^\infty$ и $ \{ b_n \}_{n=0}^\infty$ соответ.
	$\widehat{A}(t)\widehat{B}(t)$ - эксп. пр. ф-ия послед. $ \{ c_n \}_{n=0}^\infty$\\
	$ \displaystyle \sum_{k=0}^n \binom{n}{k} a_k b_{n-k}$.
	Найдем $\widehat{A_m}(t)$ для  $ \{ s(n,m) \}_{n=0}^\infty$\\
	$ \displaystyle \widehat{A_m}(t)  = \sum_{n=0}^\infty s(n,m)\frac{t^n}{n!}\\
	\sum_{m=0}^\infty \widehat{A_m}(t) \cdot x^m = 
	\sum_{n=0}^\infty( \sum_{m=0}^\infty s(n,m) \cdot x^m )\frac{t^n}{n!} = ([x]_n\\
	\sum_{m=0}^n ( s(n,m) \cdot (-1)^{n-m} x^m)\\
	x(x+1) \ldots (x+n-1) = [-x]_n \cdot (-1)^n$\\
	Возвращаемся к выводам двумя строками выше: $  \displaystyle = \sum_{n=0}^\infty [-x]_m (-1)^n \frac{t^n}{n!} = (1-t)^{-x} =
	e^{-x \log(1-t)} = e^{x\cdot \log(\frac{1}{1-t}} =
	\sum_{m=0}^\infty (\log(\frac{1}{1-t})^m \frac{x^m}{m!}\\
	\widehat{A_m}(t) = \frac{(\log\frac{1}{1-t})^m}{m!}$.

%\end{document}
