\documentclass{beamer}
\usetheme{Madrid}
\usepackage[english,russian]{babel}
\usepackage{csquotes}
\usepackage{amsmath,amssymb,lmodern}
\usepackage{soul}
\usepackage{soulutf8}
\mathbb {N}

\title{Математическая индукция и метод бесконечного спуска}
\author{}
\centering
\date{20.02.20}
\begin{document}
\maketitle
%\\
%\quad


\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}








\begin{frame}{Вполне упорядоченное множество}
\begin{block}{Вполне упорядоченное множество}
- множество Р с заданным на нем бинарным отношением ≤, удовлетворяющим условиям:\\
1) для любых х, у ∈ Р либо х <= y, либо y <= x;\\
2) если х <= y и у <= x, то х = у;\\
3) если х <= у и у <= z, то x <= z;\\
4) в любом непустом подмножестве X множества Р существует такой элемент а, что а <= х для всех х \in X
\end{block}
\end{frame}

\begin{frame}{Примеры вполне упорядоченных множеств}

\begin{itemize}
\item
{
Простейший пример бесконечного вполне упорядоченного множества — множество натуральных чисел с естественным упорядочением.
}
\item
{
Пустое множество является вполне упорядоченным.
}
\item
{
Множество целых чисел не является вполне упорядоченным, так как, например, среди отрицательных чисел нет наименьшего. Однако его можно сделать вполне упорядоченным, если переопределить отношение <= следующим образом:\\
a \preccurlyeq b \text{, если:}
  \begin{itemize}
  \item\text{либо a = b}
   \item\text{либо |a| = |b|}
    \item\text{либо |a| = |b| и a<0<b}
  \end{itemize}
}
\end{itemize}
\end{frame}

\begin{frame}{Вполне упорядоченность множества \mathbb N }
\begin{block}{Принцип математической индукции}
\text{Если подмножество Е множества натуральных чисел таково, что}\\
1 \in \text{E и вместе с некоторым числом x} \in \text{E множеству E}\\ \text{ принадлежит и число (x+1), то E - множество натуральных чисел}
То есть:\\
(\text{E }\in \mathbb N)\wedge(1 \in \text{E})\wedge(\forall x \in \text{E : }(x \in \text{E} \Rightarrow (x+1) \in \text{E})) \Rightarrow (\text{E} = \mathbb N)
\end{block}
\begin{block}{Покажем, что (n \in \mathbb N)\wedge(n \neq 1)\Rightarrow((n-1) \in \mathbb N)}
Рассмотрим множество E натуральных чисел вида (n-1) для \forall \text{n} \in \mathbb N\\
Поскольку 1 \in\mathbb N, \text{то } 2:=(1+1) \in \mathbb N,\text{ а значит } 1 := (2-1) \in \text{E.}\\
\forall \text{m} \in \text{E , m = n - 1}, \text{где n}  \in \mathbb N;\\ \text{Тогда m+1 = (n+1)-1 и, поскольку (n+1)} \in \mathbb N, \text{ имеем, что }\\ \text{(m+1)} \in \text{E.} \\ \text{Итак, 1}\in \text{E, и } \forall \text{m} \in \text{E : (m+1)}\in \text{E}.\\ \text{Из этого, по принципу индукции} \Rightarrow \text{ E = }\mathbb N
\end{block}
\end{frame}

\begin{frame}{Вполне упорядоченность множества \mathbb N}
\begin{block}{Принцип наименьшего числа - в любом непустом подмножестве натуральных чисел есть минимальный элемент}
\text{Пусть M }\subset \mathbb N. \\
\text{Если 1} \in \text{M},\text{то minM = 1, поскольку }\forall n\in \mathbb N  \text{ (1 }\leq \text{n)}\\
\text{Если 1} \notin \text{M}, \text{ т.е.  1} \in \text{E} = \mathbb N   \setminus \text{M, то в множестве Е должно}\\ \text{ найтись такое натуральное число n} \in \text{E, что}\\ \text{все натуральные числа, не превосходящие n, лежат в Е, }\\
\text{а (n+1)}\in\text{M}.\text{ Если бы такого n не было, то множество }\\ E \subset \mathbb N\text{ , содержащее 1, вместе с n}\in \text{Е, содержало бы и (n+1)} \\\text{и по принципу индукции совпадало бы} с \mathbb N
\text{Последнее невозможно, т.к}
\mathbb N\setminus \text{E = M} \neq \varnothing\\
\text{Найденное число (n+1)} \in\text{M}\text{ и будет минимальным в M,}\\ \text{поскольку между n и (n+1) нет натуральных чисел.}
\end{block}
\end{frame}

\begin{frame}{}
\begin{block}{Вторая формулировка принципа наименьшего числа:}
не сущeствует бесконечно убывающей последовательности натуральных чисел.
\end{block}
\begin{block}{Доказать, что среди всех равных друг другу дробей
непременно найдётся несократимая дробь:}
Предположим, что в нашем множестве дробей нет несократимой. Возьмём произвольную дробь
из этого множества и сократим её. Полученную дробь также сократим, и так далее.
Знаменатели этих дробей будут всё меньшими и меньшими, и возникнет бесконечная убывающая последовательность натуральных
чисел, что невозможно.
\end{block}
\end{frame}

\begin{frame}{Метод бесконечного спуска}
\begin{block}{Метод бесконечного спуска}
Метод бесконечного спуска - метод доказательства от противного, основанный на том, что множество натуральных чисел вполне упорядочено.
Из предположения, что решение существует, вытекает существование другого решения, которое в некотором смысле меньше. Тогда можно построить бесконечную цепочку решений, каждое из которых меньше предыдущего. Это вызывает противоречие с тем, что в любом подмножестве множества натуральных чисел существует минимальный элемент, значит предположение о существовании начального решения неверно.
\end{block}
\end{frame}

\begin{frame}{x^2+y^2 = 3z^2}
\begin{block}{x^2+y^2 = 3z^2}
Доказать, что это уравнение не имеет решений в целых числах при условии, что z \neq 0 \\
Пусть (x,y,z): z \neq 0 \text{ - некоторое решение}\\
Из уравнения видно, что x^2+y^2 \equiv\text{ 0 mod 3}\\
(x^2+y^2 \equiv\text{ 0 mod 3}) \Rightarrow (x^2 \equiv y^2 \equiv\text{ 0 mod 3}) \Rightarrow (x \equiv y \equiv \text{ 0 mod 3} )\\
Обозначив x и y как x=3a и y=3b, получаем:
9a^2+9b^2 = 3z^2 \\
9a^2+9b^2 = 3z^2 \Rightarrow (z \equiv \text{ 0 mod 3} )\\
Обозначив z как z=3c получаем: a^2+b^2 = 3c^2\\
Таким образом, (a,b,c) = (x/3, y/3, z/3) - еще одно решение изначального уравнения.\\
a^2+b^2=3c^2 .\\ \text{ повторяя вышеописанное, строим бесконечную} \\ \text{ цепочку решений, каждое из которых меньше предыдущего}\\
\Rightarrow \text{ Получаем противоречие в связи с п-ом наименьшего числа в } \mathbb N

\end{block}
\end{frame}
%\\%\\%\\%\\%\\%\\%\\%\\%\\%\\%\\%\\%\\%\\%\\%\\%\\%\\%\\%\\
\begin{frame}{8x^4+4y^4+2z^4=t^4}
\begin{block}{8x^4+4y^4+2z^4=t^4}
Доказать, что это уравнение не имеет решений в целых числах при условии, что t \neq 0 \\
Пусть (x,y,z,t): t \neq 0 \text{ - некоторое  целочисленное решение}\\
Из уравнения видно, что t^4 \equiv\text{ 0 mod 2}\\
(t^4 \equiv\text{ 0 mod 2}) \Rightarrow (t \equiv\text{ 0 mod 2}) \\
Пусть t=2t_1, \text{получаем:}\\
8x^4+4y^4+2z^4 = t^4 \Rightarrow 8x^4+4y^4+2z^4 = 16t_1^4 \\
8x^4+4y^4+2z^4 = 16t_1^4 \Rightarrow 4x^4+2y^4+z^4 = 8t_1^4 \Rightarrow z=2z_1:\\
4x^4+2y^4+16z_1^4 = 8t_1^4\Rightarrow 2x^4+y^4+8z_1^4 = 4t_1^4 \Rightarrow y=2y_1:\\
2x^4+16y_1^4+8z_1^4 = 4t_1^4\Rightarrow x^4+8y_1^4+4z_1^4 = 2t_1^4 \Rightarrow x=2x_1\\
16x_1^4+8y_1^4+4z_1^4 = 2t_1^4\Rightarrow 8x_1^4+4y_1^4+2z_1^4 = t_1^4\\
Получаем (x_1,y_1,z_1,t_1) = (x/2, y/2, z/2, t/2) \text{ -новое решение} \\
Таким же образом из решения (x_1, y_1, z_1, t_1)\text{ можно получить}  \\
Решение (x_2, y_2, z_2, t_2) = (x_1/2, y_1/2, z_1/2, t_1/2) \quad...
\end{block}
\end{frame}

\begin{frame}{8x^4+4y^4+2z^4=t^4}
\begin{block}{}
(x_2, y_2, z_2, t_2) = (x_1/2, y_1/2, z_1/2, t_1/2) = (x/4, y/4, z/4, t/4)\\
\text{И так далее}\\
\text{Таким образом, для }\forall n \in \mathbb N \text{ можно получить решение}\\ (x_n, y_n, z_n, t_n) =(x_{n-1}/2, y_{n-1}/2, z_{n_1}/2, t_{n-1})/2) = (x_{n-2}/4, y_{n-2}/4, z_{n-2}/4, t_{n-2}/4) = ... = (x/2^n, y/2^n, z/2^n, t/2^n) \\
\Rightarrow \text{Откуда возникает противоречие в связи принципом}\\ \text{наименьшего числа во множестве натуральных чисел} \mathbb N\\
Таким образом, уравнение 8x^4+4y^4+2z^4=t^4 \text{ не имеет решений в целых числах при t} \neq 0
\end{block}
\end{frame}

\begin{frame}{Иррациональность \sqrt2}
\begin{block}{}
Предположим, что \sqrt2 \text{ рационален и выражается некоторой несократимой дробью m/n}\\
Следовательно, (m/n)^2 =2 \\
Или: m^2 = 2n^2\\
m^2 = 2n^2 \Rightarrow (m^2 \equiv \text{0 mod 2}) \Rightarrow (m \equiv \text{0 mod 2})\\
Значит m=2k при некотором целом k:\\
m^2 = 2n^2 \Rightarrow (2k)^2 = 2n^2 \Rightarrow 4k^2 = 2n^2 \Rightarrow 2k^2 = n^2 \\
или n^2 = 2k^2 \\
Теперь аналогичным образом можно убедиться в том, что
n^2 = 2k^2 \Rightarrow (n^2 \equiv \text{0 mod 2}) \Rightarrow (n \equiv \text{0 mod 2})\\
То есть n также чётное.
Следовательно, дробь m/n можно сократить на два \Rightarrow \text{получаем противоречие в связи с тем},\\ \text{ что дробь  m/n изначально выбрана несократимой }\Rightarrow \sqrt2 \text{ - иррациональное число}

\end{block}
\end{frame}


\begin{frame}{x^4+y^4 = z^4}
\begin{block}{Пифагорова тройка}
комбинация из трёх целых чисел (x,y,z), удовлетворяющих уравнению Пифагора: x^2+y^2=z^2.
\end{block}
\begin{block}{}
Уравнение x^2+y^2=z^2 \text{ однородно, тогда при домножении}\\
\text{чисел x,y,z на
одно и то же число p можно получить другую}\\
\text{ пифагорову тройку : (xp)^2+(\text{yp})^2+(\text{zp})^2
\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad}
\end{block}
\begin{block}{Примитивная пифагорова тройка}
Если некоторая пифагорова тройка не может быть получена подобным образом, то она называется примитивной. То есть x,y,z - взаимно простые числа, НОД(x,y,z)=1
\end{block}
\end{frame}

\begin{frame}{x^4+y^4 = z^4}
\begin{block}{Пифагорова тройка}
В примитивной тройке (x,y,z) числа x и y имеют разную чётность, причём чётное делится на 4, а z — всегда нечётно\\
Любая примитивная пифагорова тройка (x,y,z), где x — нечётно,\\
а y — чётно, однозначно представляется в виде
^.(m^2-n^2, 2mn, m^2+n^2)\\
\text{для некоторых натуральных взаимно простых чисел m>n разной} чётности.
\end{block}
\end{frame}

\begin{frame}{x^4+y^4 = z^4}
\begin{block}{x^4+y^4 = z^4}
Докажем, что у этого уравнения нет решения в целых числах.
Начнем с аналогичного доказательства для уравнения x^4+y^4=z^2\\
Пусть (x,y,z) - наименьшее решение уравнения.\\
У этого наименьшего решения числа x,y,z взаимно простые:\\
Докажем это:\\
Очевидно, что если какие-то два числа из (x,y,z) делятся на некоторое простое число p, то третье число также делится на p.
Тогда^.\quad x=px_1,\quad y=py_1,\quad z=pz_1\\
^.p^4x_1^4+p^4y_1^4 = p^2z_1^2 \Rightarrow p^2x_1^4+p^2y_1^4 = z_1^2
 \Rightarrow x_1^4+y_1^4 = z_2^2\\
 x_1^4+y_1^4 = z_2^2 \\
 Таким образом получено решение (x_1,y_1,z_2) \\
 которое меньше предыдущего (x,y,z) - возникает противоречие\\
 Поэтому если тройка (x,y,z) минимальное решение, то числа x,y,z взаимопростые
\end{block}
\end{frame}

\begin{frame}{x^4+y^4 = z^4}
\begin{block}{x^4+y^4 = z^4}
x^4+y^4=z^2\\
В этом уравнении (x^2,y^2,z) - \text{также пифагорова тройка}\\
По известной о примитивных пифагоровых тройках информации:\\
z - обязательно нечетно\\
числа x и y - разной четности, возьмем x - четным, а y -нечетным\\
Тогда x можно представить в виде x=2x_1\\
4x_1^2 = 2mn,\: y^2 = m^2 - n^2,\:z = m^2 + n^2 \\
В y^2 = m^2 - n^2 \text{ получаем, что m - нечетное, n - четное }\\
Так как n=2n_1\\
Тогда из 4x_1^2=2mn \Rightarrow 4x_1^2 = 4mn_1 \Rightarrow x_1^2=mn_1\\
x_1^2=mn_1 \Rightarrow m = a^2, n_1 = b^2\text{(из взаимной простоты m и n)}\\
\end{block}
\end{frame}

\begin{frame}{x^4+y^4 = z^4}
\begin{block}{x^4+y^4 = z^4}
y^2 = m^2 - n^2 \Rightarrow m^2 = y^2 + n^2\\
Так как n=2n_1,\text{ получаем:}\\
m^2=y^2+n^2 \Rightarrow m^2=y^2+4n_1^2\\
\\Из свойств примитивных пифагоровых троек:\\
m = q^2+ r^2, \: y= q^2 -r^2\\
и 2n_1 = 2qr \Rightarrow n_1-qr\\
\\
b^2 = n_1 = qr \Rightarrow \text{из взаимной простоты q и r получаем:}\\
q=t^2, \: r=s^2\\
Тогда a^2 = m = q^2 + r^2 = t^4 + s^4\\
Итак, a^2 = t^4 + s^4\\
Получаем противоречие, так как число a заведомо меньше числа z\\
\end{block}
\end{frame}

\end{document}