path: root / Year 1 / Discrete math / notes.tex

% Document MUST be built with XeLaTeX!
\documentclass[11pt,a4paper]{article}

\usepackage[margin=1.5cm]{geometry}

% Поддръжка на български език
% Thanks to https://tex.stackexchange.com/a/136926
\usepackage{fontspec}
\defaultfontfeatures{Ligatures=TeX}
\setmainfont{CMU Serif}
\setsansfont{CMU Sans Serif}

\usepackage[bulgarian,english]{babel}

\usepackage{amsmath}            % Математически символи
\usepackage{amsfonts}           % Още математически символи
\usepackage{cancel}             % Зачертаване
\usepackage[dvipsnames]{xcolor} % Цветни кутийки + допълнителни цветове
\usepackage{indentfirst}        % Индентация на параграф след секция

\usepackage{enumitem}
\setlist[enumerate]{label=\arabic*.}

\renewcommand{\thesection}{Лекция \arabic{section}}
\renewcommand{\thesubsection}{\quad\arabic{section}.\arabic{subsection}}

\usepackage[pdfauthor={Kamen Mladenov: syndamia.com, gitlab.com/Syndamia},
		    pdftitle={Discrete Math, Computer Science 2021, Winter Semester},
		    pdfsubject={Бележки по Дискретни Структури},
		    pdfkeywords={Съждителна логика, Множества, Релации, Функции, Изброителна комбинаторика, Комбинаторни конфигурации, Рекурентни уравнения}]{hyperref}

\begin{document}

\section{\underline{Съждителна логика}}

\begin{tabular}{l|l}
	\hline \\[-0.9em]
	\textbf{Свойства на константите} & $p \land T \equiv p, \quad p \lor F \equiv p, \quad p \lor T \equiv T, \quad p \land F \equiv F$ \\[0.2em]
	\hline \\[-0.9em]
	\textbf{Свойства на отрицанието} & $p \land \neg p \equiv F, \quad p \lor \neg p \equiv T$ \\[0.2em]
	\hline \\[-0.9em]
	\textbf{Закон за двойното отрицание} & $\neg (\neg p) \equiv p$ \\[0.2em]
	\hline \\[-0.9em]
	\textbf{Идемпотентност} & $p \lor p \equiv p, \quad p \land p \equiv p$ \\[0.2em]
	\hline \\[-0.9em]
	\textbf{Комутативност} & $p \lor q \equiv q \lor p, \quad p \land q \equiv q \land p$ \\[0.2em]
	\hline \\[-0.9em]
	\textbf{Асоциативност} & $(p \lor q) \lor r \equiv p \lor (q \lor r), \quad (p \land q) \land r \equiv p \land (q \land r)$ \\[0.2em]
	\hline \\[-0.9em]
	\textbf{Дистрибутивност} & $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r), \quad p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$ \\[0.2em]
	\hline \\[-0.9em]
	\textbf{Закони на De Morgan} & $\neg (p \lor q) \equiv \neg p \land \neg q, \quad \neg (p \land q) \equiv \neg p \lor \neg q$ \\[0.2em]
	\hline \\[-0.9em]
	\textbf{Поглъщане} & $p \lor (p \land q) \equiv p, \quad p \land (p \lor q) \equiv p$ \\[0.2em]
	\hline \\[-0.9em]
	\textbf{Свойство на импликацията} & $p \rightarrow q \equiv \neg p \lor q$ \\[0.2em]
	\hline \\[-0.9em]
	\textbf{Свойство на би-импликацията} & $p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)$ \\[0.2em]
	\hline
\end{tabular}

  
\section{\underline{Множества}}

Множество, което не съдържа себе си, е обикновено.
Множество, което съдържа себе си, е необикновено.

\subsection{Аксиоми}

\begin{enumerate}
	\item \emph{Аксиома за обема} \newline Две множества са равни тстк съдържат едни и същи елементи (редът е без значение)
	
	\item \emph{Аксиома за отделянето} \newline Ако $X$ е множество и $\pi$ е предикат с домейн $X$, то съвкупността $Y$ от елементите на $X$, които имат свойството $\pi$, е множество. \newline \newline $B = \left\{a \in A \mid \pi(a) \right\}$ \quad Казваме, че B е подмножество на A
	
	\item \emph{Аксиома за степенното множество} \newline За всяко множество $X$ съществува множество $2^X$ от всички негови подмножества, което наричаме степенното множество на $X$
	
	\item \emph{Максимално по включване множество} \newline Множество, за което свойството (предикатът) е в сила, но то не е в сила за никое същинско негово надмножество.
	\begin{enumerate}
		\item $\sigma (B)$ и
		\item $\forall C\left( B \subset C \subseteq A \rightarrow \neg \sigma (C) \right)$
	\end{enumerate}
	\emph{Минимално по включване множество} \newline Такова подмножество, за което свойството (предикатът) е в сила, но не е в сила за никое същинско негово подмножество.
	\begin{enumerate}
		\item $\sigma (B)$ и
		\item $\forall C\left( C \subset B \rightarrow \neg \sigma (C) \right)$
	\end{enumerate}
\end{enumerate}

\subsection{Операции}

\begin{enumerate}
	\item \emph{Симетрична разлика} \newline
	$A \triangle B = \left\{ a \mid a \in A \oplus a \in B \right\}$ \qquad\qquad Пример: 
	$\left\{ a, b, c, d \right\} \triangle \left\{ a, b, x, y \right\} = \left\{ c, d, x, y \right\}$
	
	\item \emph{Допълнение}  на множество $A$ до универсум $U$ \newline
	$\overline{A^U} = \left\{ a \mid a \in U \land a \notin A \right\}$ \quad Ако $U$ се подразбира, пишем само $\overline{A}$
\end{enumerate}

\subsection{Наредена двойка}

(Дефиниция на Kuratowski) Всяко множество $\left\{\{a\}, \{a, b\}\right\}$ наричаме наредена двойка с първи елемент a и втори елемент b. Краткият запис е “$(a, b)$”.

\subsection{Разбиване и покриване}

\begin{enumerate}
	\item \emph{Покриване на $A$} \newline
	Всяка фамилия $X = \left\{X_1, X_2, ..., X_k \right\}, k \geq 0$, където
	
	\begin{enumerate}
		\item $\forall i \in \left\{ 1, 2, ..., k \right\} : X_i \subseteq A$
		\item $\forall i \in \left\{ 1, 2, ..., k \right\} : X_i \neq \emptyset$
		\item $\bigcup\limits_{i = 1}^{k} X_i = A$
	\end{enumerate}
	Тоест, всяка фамилия, чието обединение на множества е даденото множество. \newline
	Пример: $A = \left\{ a, b, c, d \right\} \qquad X = \left\{ \{a, b, d\}, \{b, c\}, \{a, b, c, d\} \right\}$
	
	\item \emph{Разбиване на $A$} \newline
	Всяка фамилия $X = \left\{X_1, X_2, ..., X_k \right\}, k \geq 0$, където
	
	\begin{enumerate}
		\item $\forall i \in \left\{ 1, 2, ..., k \right\} : X_i \subseteq A$
		\item $\forall i \in \left\{ 1, 2, ..., k \right\} : X_i \neq \emptyset$
		\item $\bigcup\limits_{i = 1}^{k} X_i = A$
		\item $\forall i \forall j (1 \leq i < j \leq k \rightarrow X_i \cap X_j = \emptyset)$
	\end{enumerate}
	Тоест, покриване, при което няма общи елементи между множествата във фамилията. \newline
	Пример: $A = \left\{ a, b, c, d \right\} \qquad X = \left\{ \{a, c\}, \{b\}, \{c\} \right\}$
	
\end{enumerate}

\subsection{Доказателство по индукция}

\begin{enumerate}
	\item \emph{Обикновена индукция}
	\begin{enumerate}
		\item \emph{База}: Проверяваме за най-ниската възможна стойност \hfill $P(0), n \geq 0$
		\item \emph{Индукционно предположение}: Допускаме че е вярно за произволна стойност \hfill $P(n)$
		\item \emph{Индукционна стъпка}: Доказваме че е вярно за следващата произволна стойност, въз основа на индукционното предположение \hfill $P(n + 1)$
	\end{enumerate}
	
	\item \emph{Силна индукция}
	\begin{enumerate}
		\item \emph{База}: Проверяваме за най-ниската възможна стойност \hfill $P(0), n \geq 0$
		\item \emph{Индукционно предположение}: Допускаме, че е вярно за всички стойности от най-ниската до произволно $n$ \hfill $P(0), P(1), ..., P(n)$
		\item \emph{Индукционна стъпка}: Доказваме че е вярно за следващата произволна стойност, въз основа на индукционното предположение \hfill $P(n + 1)$
	\end{enumerate}
\end{enumerate}

\section{\underline{Релации}}

Релация над декартовото произведение $A_1 \times A_2 \times ... \times A_n$ се нарича всяко множество $R \subseteq A_1 \times A_2 \times ... \times A_n$

\subsection{Свойства на релации от вида $R \subseteq A^2$}

\begin{enumerate}
	\item \emph{Рефлексивност} \qquad\qquad $\forall a \in A : aRa$ \newline
	\emph{Антирефлексивност} \qquad $\forall a \in A : \neg aRa$
	
	\item \emph{Симетричност} \qquad\qquad\qquad $\forall a, b \in A, a \neq b : aRb \rightarrow bRa$ \newline
	\emph{Антисиметричност} \qquad\qquad $\forall a, b \in A, a \neq b : aRb \rightarrow \neg bRa$ \newline
	\emph{Силна антисиметричност} \quad $\forall a, b \in A, a \neq b : aRb \oplus bRa$
	
	\item \emph{Транзитивност} \qquad $\forall a, b, c \in A : aRb \land bRc \rightarrow aRc$
\end{enumerate}

\subsubsection{Затваряне на релации}

\begin{enumerate}
	\item \emph{Рефлексивно затваряне} $R'$
	\begin{enumerate}
		\item $R' \subseteq A^2$
		\item $R \subseteq R'$
		\item $R'$ е рефлексивна
	\end{enumerate}
\end{enumerate}

Аналогично за симетрично и транзитивно затваряне

\subsubsection{Типове релации}

\begin{enumerate}
	\item \emph{Релация на еквивалентност}: рефлексивна, симетрична, транзитивна \newline
	\emph{Класове на еквивалентност}: $[a] = \{ b \in A \mid aRb \}$ \quad Дефакто са разбивания на $R$
	
	\item \emph{Релация на частична наредба}: рефлексивна, антисиметрична, транзитивна \newline
	\emph{Минимален елемент}: \; $a$ е минимален, ако $\neg \exists b \in A, a \neq b : bRa$ \newline
	\emph{Максимален елемент}: $a$ е максимален, ако $\neg \exists b \in A, a \neq b : aRb$ \newline \newline
	\emph{Релация на частична строга наредба}: антирефлексивна, антисиметрична, транзитивна \newline
	
	\emph{Диаграма на Hasse}: Чертаем диаграма на релацията, така че всички стрелки да сочат нагоре, изпускаме примките, изпускаме посоките на стрелките, изпускаме транзитивните стрелки. \newline
	
	Няма контури в частичните наредби!
	
	\item \emph{Релация на линейна наредба}: рефлексивна, силно антисиметрична, транзитивна \newline
	\emph{Линейно разширение}: Частична наредба $R$, линейна наредба $R'$, $R \subseteq R' \implies R'$ е линейно разширение на $R$ \newline \newline
	\emph{Релация на линейна строга наредба}: антирефлексивна, силно антисиметрична, транзитивна
\end{enumerate}

\subsubsection{Верига и контур}

\begin{itemize}
	\item \emph{Верига}: всяка редица $a_{i_0}, a_{i_1}, ..., a_{i_k} \;\text{, където }\\ i_0,...,i_k \in \{1,...,n\}, \, a_{i_j} \, R \, a_{i_{j + 1}} \;\text{ и }\; a_{i_j} \neq a_{i_{j + 1}} \;\text{ за }\; 0 \leq j < k$ \newline \newline
	Дефакто, редица от елементи, където всеки два съседни елемента са в релация. \newline Веригите НЕ минават през примки!
	
	\item \emph{Контур}: всяка верига, за която е вярно и, че $a_{i_0} = a_{i_k} \text{ за } k > 0$ \newline \newline
	Дефакто, редица от елементи, където всеки два съседни елемента са в релация и първия и последния също са в релация.
\end{itemize}

\section{\underline{Функции}}

\begin{itemize}
	\item \emph{Тотална функция}: Всяка релация $f \subseteq X \times Y$, където за всяко $x$ има точно едно $y : (x, y) \in f$
	\item \emph{Частична функция}: Всяка релация $f \subseteq X \times Y$, където за всяко $x$ има не повече от едно $y : (x, y) \in f$
\end{itemize}

\subsection{Свойства}

\begin{enumerate}
	\item \emph{Инекция}: Всеки елемент на $Y$ е образ най-много на един елемент на $X$ \newline
	$\forall x_1, x_2 \in X : x_1 \neq x_2 \implies f(x_1) \neq f(x_2)$
	\item \emph{Сюрекция}: Всеки елемент на $Y$ е образ на поне един елемент на $X$ \newline
	$\forall y \in Y \exists x \in X : f(x) = y$
	\item \emph{Биекция}: Ако имаме инекция и сюрекция (взаимозначно съответствие)
\end{enumerate}

\subsubsection{Изброимост}

\begin{itemize}
	\item \emph{Крайно множество}: Ако $A$ е празно, то имаме кардиналност 0. \newline Иначе, трябва да съществува $n$, за което съществува биекция $f : A \rightarrow \{1, 2, ..., n\}$
	
	\item \emph{Безкрайно множество}: Ако не е крайно \newline
	\emph{Изброимо безкрайно мнжоество}: Ако е равномощно на $\mathbb{N}$ \hfill $\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{N}^2, \mathbb{Z}^2, ...$ \newline
	\emph{Неизброимо безкрайно множество}: Ако не е изброимо безкрайно \hfill $\mathbb{R}, \mathbb{C}, 2^{\mathbb{N}}, \mathbb{R}^2, 2^{\mathbb{R}}, ...$
\end{itemize}

\subsubsection{Принцип на Дирихле}

За крайни $X$ и $Y$, $|X| > |Y|$, то не съществува инекция $f : X \rightarrow Y$

Ако имаме $m$ обекта в $n$ чекмеджета, то има поне едно чекмедже с $\left\lceil \frac{m}{n} \right\rceil$ обекта.

\subsection{Рестрикция на функция}

Нека $f : X \rightarrow Y$ и $X' \subseteq X$. Рестрикция на $f$ върху $X'$ е $f' : X' \rightarrow Y,\; \forall x \in X' : f'(x) = f(x)$

Бележи се $\left. f \right|_{X'}$ \qquad (Дефакто работим с част от елементите на домейна)

\section{\underline{Изброителна комбинаторика}}

\subsection{Принципи}

\begin{enumerate}
	\item \emph{Принцип на Дирихле}

	\item \emph{Принцип на разбиването} \newline
	Кардиналността е сума от кардиналностите на дяловете на разбиване. \newline
	За множество $X$ и негови разбивания $\left\{ Y_1, ..., Y_k \right\}$, имаме $|A| = |Y_1| + ... + |Y_k| = \sum\limits_{i = 1}^{k} |Y_i|$ \newline \newline
	\emph{Принцип на изваждането} (следствие от Принцип на разбиването) \newline
	За множество $A$ и универсум $U$, имаме $|A| = |U| - \left| \overline{A} \right|$
	
	\item \emph{Принцип на умножението}: $|A \times B| = |A| \cdot |B|$
	
	\item \emph{Принцип на биекцията}: $|A| = |B|$ тстк съществува биекция $f : A \rightarrow B$
	
	\item \emph{Принцип на делението} \newline
	За $k = $ брой класове на еквивалентност, $\left| [a] \right| = m$, имаме $m = \frac{|A|}{k}$
	
	\item \emph{Принцип на включването и изключването} \newline
	Кардиналността е сума от дяловете на покритие със изваждане на техни сечения.
	\begin{align*}
		|A_1 \cup ... \cup A_n| & = \sum\limits_{1 \leq i \leq n} |A_i| - \sum\limits_{1 \leq i < j \leq n} |A_i \cap A_j| + ... + (-1)^{n-1} \cdot |A_1 \cap ... \cap A_n| \\
		|\overline{A_1} \cap ... \cap \overline{A_n}| & = |U| -  \sum\limits_{1 \leq i \leq n} |A_i| + \sum\limits_{1 \leq i < j \leq n} |A_i \cap A_j| - ... + (-1)^{n-1} \cdot |A_1 \cap ... \cap A_n|
	\end{align*}
\end{enumerate}

\section{\underline{Комбинаторни конфигурации}}

Дадено е опорно множество $А = {a1, a2, ..., an}$ чрез което ще изграждаме комбинаторни конфигурации.
Общоприето е, че $n$ е брой елементи в $A$, $m$ е брой елементи в конфигурация.

\begin{enumerate}
	\item \emph{Множество от конфигурации с наредба, с повтаряне} \newline
	$\text{К}_\text{Н, П}(n, m) = A^m \equiv \widetilde{V}_n^m \qquad\qquad \left| \text{К}_\text{Н, П}(n, m) \right| = |A^m| = n^m$
	
	\item \emph{Множество от конфигурации с наредба, без повтаряне} \newline
	$\text{К}_\text{Н}(n, m) \equiv V_n^m \qquad\qquad \left| \text{К}_\text{Н}(n, m) \right| = n \cdot (n-1) \cdot (n-2) \cdot ... \cdot (n - m + 1) = n^{\underline{m}}$ \newline\newline
	\emph{Пермутации с повторения}: частен случай, когато $n = m$. $\left| \text{К}_\text{Н}(n, m) \right| = n!$
	
	\item \emph{Множество от конфигурации без наредба, без повтаряне}: просто комбинации/подмножество \newline
	$\text{К}(n, m) \equiv C^n_m \qquad\qquad \left| \text{К}(n, m) \right| = \frac{\left| \text{К}_\text{Н}(n, m) \right|}{m!} = \frac{n!}{(n-m)!m!} = \frac{n^{\underline{m}}}{m!} = \binom{n}{m}$
\end{enumerate}

\begin{tabular}{l||l|l|l}
	\hline \\[-0.9em]
	& Комбинации & Вариации & Пермутации \\[0.2em]
	Различаваме по: & Съставни елементи & Съставни елементи и ред & Ред \\[0.2em]
	\hline \hline \\[-0.9em]
	Без повторениe & $C^k_n = \frac{n!}{k!(n-k)!} = \binom{n}{k}$ & $V^k_n = \frac{n!}{(n-k)!} = n^{\underline{k}}$ & $P_n = n!$ \\[0.2em]
	\hline \\[-0.9em]
	С повторение & $\widetilde{C}^k_n = \frac{(n + k - 1)!}{k!(n-1)!}$ & $\widetilde{V}^k_n = n^k$ & $\widetilde{P}^{n_1, n_2, ..., n_m}_n = \frac{n!}{n_1!n_2!...n_m!}$ \\[0.2em]
	\hline
\end{tabular}

\subsection{Свойства на биномни коефициенти}

\noindent
\begin{align*}
	& \binom{n}{k} = \frac{n!}{k!(n-k)!} \qquad \binom{n}{k} = \binom{n}{n - k} \qquad \binom{n}{k} + \binom{n}{k + 1} = \binom{n + 1}{k + 1} \qquad \binom{n}{k} = \binom{n - 1}{k} + \binom{n - 1}{k - 1} \\
	& \binom{n}{0} = \binom{n}{n} = 1 \qquad \binom{n}{1} = \binom{n}{n-1} = n \\
	& \textbf{Нютонов бином } \quad (x + y)^n = \sum_{k = 0}^n \binom{n}{k} \cdot n^k \cdot y^{(n - k)} \\
	& \textbf{От комбинаторни разсъждения } \quad \binom{2n}{n} = \sum^n_{k = 0} \binom{n}{k}^2 \qquad \binom{n + m}{m} = \sum^m_{k = 0} \binom{n + k - 1}{k}
\end{align*}

\subsection{Характеристичен вектор}

Булева n-торка, която характеризира/определя дадено множество $X$, където:

Ако $n \in X$, то $a_n = 1$ \qquad Ако $n \notin X$, то $a_n = 0$

\subsubsection{Свойства (за булеви вектора с $n$ единици и $m$ нули)} 
\begin{itemize}
	\item Брой: $\binom{n+m}{n}$
	\item Брой, като след всяка единица има нула: $\binom{m}{n}$
	\item Брой, като няма съседни единици: $\binom{m + 1}{n}$
\end{itemize}

\subsection{Свойства на суми}

\noindent
\begin{align*}
	\sum_{k = 0}^n k = \frac{n(n + 1)}{2} \qquad \sum_{k = 0}^n k^2 = \frac{n(n + 1)(2n + 1)}{6} \qquad \sum_{k = 0}^n k^3 = \frac{n^2(n + 1)^2}{4} \qquad \sum_{k = 0}^n a = a(n+1)
\end{align*}

\section{\underline{Рекурентни уравнения}}

Уравнение, при което дясната му страна включва и самото уравнение и имаме начално условие(ия)
\begin{align*}
	& \text{Пример: } L(n) =
	\begin{cases}
		L(n-1) + n, & \text{ ако } n \in \mathbb{N}^+ \\
		1, & \text{ ако } n = 0
	\end{cases}
\end{align*}

\subsection{Алгоритъм за решаване на линейно рекурентно уравнение с константни коефициенти и крайна история}

\noindent
\begin{align*}
	& F_n = 
	\begin{cases}
		F_{n-1} + F_{n-2}, & \text{ ако } n \geq 2 \\
		1, & \text{ ако } n = 1 \\
		0, & \text{ ако } n = 0
	\end{cases}
	\qquad \text{ е такова валидно уравнение} \\
	& \text{Обаче, следните уравнения не могат да се решат с този метод:} \\
	& T_n = 
	\begin{cases}
		n \cdot T_{n-1} & \text{ ако } n \geq 1 \\
		1, & \text{ ако } n = 0
	\end{cases}
	\qquad \text{ защото не е с константи коефициенти} \\
	& S_n = 
	\begin{cases}
		S_{n-1} + S_{n-2} + ... + S_1 + S_0, & \text{ ако } n \geq 1 \\
		1, & \text{ ако } n = 0
	\end{cases}
	\qquad \text{ защото не е с крайна история}
\end{align*}

За илюстриране на метода, нека да разгледаме $a_n = c_1 a_{n-1} + c_2 a_{n-2} + ... + c_k a_{n-k}$

\begin{enumerate}
	\item \emph{Характеристично уравнение} \newline
	Заместваме $a_n$ с $x^n$, $a_{n-1}$ с $x^{n-1}$ и так. нат. \hfill $x^n = c_1 x^{n-1} + c_2 x^{n-2} + ... + c_k x^{n-k}$ \newline
	След това, делим всичко на $x^{(n-k)}$ \hfill $x^k = c_1 x^{k-1} + c_2 x^{k-2} + ... + c_k$ \qquad\- \newline
	Алтернативно, може да се запише и като \hfill $x^k - c_1 x^{k-1} - c_2 x^{k-2} - ... - c_k = 0$ \, \-
	
	\item \emph{Общо решение} \newline
	Намираме корените на хар. уравнение. \hfill Нека те да са мултимножеството $\{ \alpha_1, \alpha_2, ..., \alpha_k \}_{\text{М}}$ \newline
	Съставяме уравнението \hfill $a_n = A_1 \cdot \alpha_1^n + A_2 \cdot \alpha_2^n + ... + A_k \cdot \alpha_k^n$ \newline\newline
	Ако имаме еднакви корени, умножаваме с $n^r$, където $r \in \mathbb{N}$ е r-тия повтарящ се корен. \newline
	Тоест, ако да имаме 5 корена, за които $\alpha_1 = \alpha_2 = \alpha_3 \neq \alpha_4 \neq \alpha_5$, ще изглежда така: \newline\newline
	\- \hfill $a_n = A_1 \alpha_1^n \cdot n^0 + A_2 \alpha_2^n \cdot n^1 + A_3 \alpha_3^n \cdot n^2 + A_4 \alpha_4^n + A_5 \alpha_5^n$
	
	\item \emph{Точно решение} (Само ако началните условия са ни дадени) \newline
	Вземаме първите $k$ на брой начални условия (ако се наложи допълваме, тоест изчисляваме всички стойности до $a_k$). \newline
	С тях, съставяме система линейни уравнения за $a_1, a_2, a_3, ...$
	\begin{equation*}
		\left| \begin{array}{ccccccccc}
			a_1 & = & A_1 \cdot \alpha_1^1 & + & A_2 \cdot \alpha_2^1 & + & ... & + & A_k \cdot \alpha_k^1 \\
			\vdots \\
			a_k & = & A_1 \cdot \alpha_1^k & + & A_2 \cdot \alpha_2^k & + & ... & + & A_k \cdot \alpha_k^k
		\end{array} \right.
	\end{equation*}
	Чрез нея, намираме стойностите на $A_1, ..., A_k$ и заместваме в Общото решение
\end{enumerate}

\subsection{Решаване на нехомогенно рекурентно уравнение с константни коефициенти и крайна история}

Нека $b_1, ..., b_l$ са различни стойности, а $p_1(n), ..., p_l(n)$ са полиноми на $n$. Уравненията са от типа
\begin{equation*}
	a_n = \underbrace{c_1 a_{n-1} + ... + c_k a_{n-k}}_{\text{xомогенна част}} + \underbrace{p_1(n) \cdot b_1^n + ... + p_l(n) \cdot b_l^n}_{\text{нехомогенна част}}
\end{equation*}

\begin{enumerate}
	\item \emph{Характеристично уравнение} \newline
	Съставя се като при \textbf{7.1}, като просто си представим, че нехомогенната част (тази с $p_l(n)$-вете) не съществува.
	
	\item \emph{Общо решение} \newline
	След като намерим мултимножеството от корени на хомогенната част, разглеждаме нехомогенната. \newline
	Абстрахираме се от всякакви коефициенти и разглеждаме хомогенната част като сборове от комбинации на $n^g \cdot h^n$. \newline
	Образуваме мултимножеството от корени на нехомогенната част, като добавяме съответните $h$ $g+1$ пъти.
	\begin{align*}
		\text{Пример: } & 2n^2 + 3^n + 19n^3 7^n \; \text{ свеждаме до } \; n^2 1^n + n^0 3^n + n^3 7^n \\
		& \text{Корените ни са, три 1-ци, една 3-ка, четири 7-ци: } \{1, 1, 1, 3, 7, 7, 7, 7\}_{\text{М}}
	\end{align*}
	Накрая обединяваме двете мултимножества и продължаваме както при \textbf{7.1}.
	
	\item \emph{Точно решение} \newline
	Следваме същите стъпки като \textbf{7.1}
\end{enumerate}

\end{document}