\begin{frame}{Математическая индукция}
Математическая индукция — метод математического доказательства, который используется, чтобы доказать истинность некоторого утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером 1 — база (базис) индукции, а затем доказывается, что если верно утверждение с номером n, то верно и следующее утверждение с номером n + 1 — шаг индукции, или индукционный переход.
\end{frame}

\begin{frame}{Математическая индукция}
Предположим, что требуется установить справедливость бесконечной последовательности утверждений, занумерованных натуральными числами: P_{1},P_{2},...,P_{n},P_{n+1},...
Допустим, что:\begin{itemize}
\item Установлено, что P{1} верно. (Это утверждение называется базой индукции.)
\item Для любого n доказано, что если верно P{n}, то верно P{n+1}. (Это утверждение называется индукционным переходом.)
\end{itemize}
Тогда все утверждения нашей последовательности верны.
\end{frame}

\begin{frame}{Математическая индукция}
 Логическим основанием для этого метода доказательства служит так называемая аксиома индукции, пятая из аксиом Пеано, определяющих натуральные числа.
\end{frame}

\begin{frame}{Аксиома индукции}
 Если какое-либо предложение доказано для 1 и если из допущения, что оно верно для натурального числа n, вытекает, что оно верно для следующего за n натурального числа, то это предложение верно для всех натуральных чисел.
\end{frame}

\begin{frame}{Принцип полной мат. индукции}
Пусть имеется последовательность утверждений Y{1}, Y{2}, Y{3},..\\
И пусть мы умеем доказывать первое из них, а так же то, что из
верности утверждений Y{1},..,Y{k} следует верность Y{k+1}.\\ Тогда все утверждения в этой последовательности верны.В этой вариации база индукции оказывается излишней, поскольку является тривиальным частным случаем индукционного перехода.
\end{frame}

\begin{frame}{Примеры}
    \begin{block}{}
    1+q+q^{2}+...+q^{n}={{{1-q^{n+1}}\over{1-q}}}.\\
    \text{Доказательство. Индукция по n. База, n=1:}
    1+q=(1-q)(1+q)/(1-q)=(1-q^{2})/(1-q).\\
    Переход: предположим, что: \\
    1+q+...+q^{n}={\frac{1-q^{{n+1}}}{1-q}}, \text{ тогда:} \\
    1+q+...+q^{n}+q^{n+1}={\frac{1-q^{{n+1}}}{1-q}}+q^{{n+1}}={\frac  {1-q^{{n+1}}+(1-q)q^{{n+1}}}{1-q}}={\frac  {1-q^{{n+1}}+q^{{n+1}}-q^{{(n+1)+1}}}{1-q}}={\frac  {1-q^{{(n+1)+1}}}{1-q}}, \\
    \text{Что и требовалось доказать.}
    \end{block}
\end{frame}

\begin{frame}{Примеры}
    \begin{block}{}
    Доказать, что (при любом n>=1): \\
    1+4+9+...+n^{2}={{n(n+1)(2n+1)}\over{6}} \\
    \text{Базис n=1: 1 = (1*2*3)/6} \\
    \text{Переход: предположим, что:} \\
    1+4+9+...+(n-1)^{2}={{(n-1)n(2n-1)}\over{6}} \\
    \text{Тогда:} \\
    1+4+9+..+(n-1)^{2}+n^{2}={{(n-1)n(2n-1)+6n^{2}}\over{6}}=
    {{n((n-1)(2n-1)+6n)}\over{6}}={{n(2n^{2}-3n+1+6n)}\over{6}}=
    {{n(2n^{2}+3n+1)}\over{6}}={{n(n+1)(2n+1)}\over{6}} \\
    \text{Что и требовалось доказать.}
    \end{block}
\end{frame}