4.1: Вступ до індукції

Last updated
Save as PDF

Page ID: 65577

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

У цьому розділі ми введемо математичну індукцію, яка є доказовою технікою, яка корисна для доведення тверджень виду (n$\mathbb{N}$) P (n), або більш загально (n ‰$\mathbb{Z}$) (n ≥ a = ⇒ P (n)), де P (n) є деяким присудком і a$\mathbb{Z}$.

Розглянемо претензії:

Для всіх$n\in\mathbb{N}$,$\displaystyle 1+2+3+\cdots +n=\frac{n(n+1)}{2}$.
Для всіх$n\in\mathbb{N}$,$n^{2}+n+41$ це прайм.

Давайте подивимося на потенційні докази.

«Доказ» з (а). Якщо$n=1$, то$1=\frac{1(1+1)}{2}$. Якщо$n=2$, то$1+2=3=\frac{2(2+1)}{2}$. Якщо$n=3$, то$1+2+3=6=\frac{3(3+1)}{2}$, і так далі.

«Доказ» з (б). Якщо$n=1$, то$n^{2}+n+41=43$, який є простим. Якщо$n=2$, то$n^{2}+n+41=47$, який є простим. Якщо$n=3$, то$n^{2}+n+41=53$, який є простим, і так далі.

Чи є ці фактичні докази? Ні! Насправді, друга претензія навіть не відповідає дійсності. Якщо$n=41$, то$n^{2}+n+41=41^{2}+41+41=41(41+1+1)$, який не є простим, оскільки він має 41 як фактор. Виявляється, перше твердження є правдою, але те, що ми написали, не може бути доказом, оскільки той самий тип міркувань при застосуванні до другого твердження, здається, доводить щось, що насправді не відповідає дійсності. Нам потрібен суворий спосіб захоплення «і так далі» і спосіб перевірити, чи дійсно це «і так далі».

Нагадаємо, що аксіома - це основне математичне припущення. Наступна аксіома - одна з аксіом Пеано, яка є сукупністю аксіом для натуральних чисел, введеної в 19 столітті італійським математиком Джузеппе Пеано (1858—1932).

Аксіома 4.1. Нехай$S\subseteq \mathbb{N}$ такі, що обидва

$1\in S$, і
якщо$k\in S$, то$k+1\in S$.

Потім$S=\mathbb{N}$.

Ми можемо думати про набір$S$ як сходи, де перша гіпотеза говорить про те, що у нас є перша сходинка сходів. Друга гіпотеза говорить, що якщо ми знаходимося на будь-якій довільної сходинці сходів, то ми завжди зможемо дістатися до наступної сходинки. Узяті разом це говорить про те, що ми можемо потрапити з першої сходинки на другу, з другої на третю, та$k$ й взагалі, від будь-якої ї сходинки до$(k+1)$ першої сходинки, щоб наша сходи була насправді$\mathbb{N}$. Чи згодні ви, що аксіома індукції є досить розумним припущенням?

Наприкінці розділу 3.2 ми коротко обговорили ZFC, який є стандартним вибором для аксіоматичної теорії множин. Виявляється, можна довести аксіому індукції як теорему в ZFC. Однак це не буде той підхід, який ми приймаємо. Натомість ми припускаємо, що аксіома індукції вірна. Використовуючи цю аксіому, ми можемо довести наступну теорему, відому як Принцип математичної індукції. Один з підходів до доведення цієї теореми полягає в тому, щоб дозволити$S=\{k\in \mathbb{N}\mid P(k) \text{ is true}\}$ і використовувати аксіому індукції. Набір іноді$S$ називають набором істинності. Ваша робота полягає в тому, щоб показати, що істина встановлена все$\mathbb{N}$.

Теорема 4.2. $P(1), P(2), P(3), \ldots$Дозволяти послідовність тверджень, по одному для кожного натурального числа. Припустимо

$P(1)$правда, і
якщо$P(k)$ правда, то$P(k+1)$ істинно.

Тоді$P(n)$ вірно для всіх$n\in\mathbb{N}$.

Принцип математичної індукції надає нам процес доведення тверджень виду: «Для всіх»$n\in\mathbb{N}$$P(n)$, де$P(n)$ є якийсь присудок за участю$n$. Гіпотеза (i) вище називається базовим кроком (або базовим випадком), тоді як (ii) називається індуктивним кроком.

Не слід плутати математичну індукцію з індуктивними міркуваннями, пов'язаними з природничими науками. Індуктивне міркування - це науковий метод, за допомогою якого спостереження індукує загальні принципи. З іншого боку, математична індукція - це дедуктивна форма міркування, яка використовується для встановлення обґрунтованості пропозиції.

Скелет Доказ 4.3. Ось загальна структура для доказу шляхом індукції.

Приступаємо за допомогою індукції.

Базовий крок: [Переконайтеся, що$P(1)$ це правда. Це часто, але не завжди, означає підключення до двох$n=1$ сторін деякого заявленого рівняння і що обидві сторони насправді рівні.]
Індуктивний крок: [Ваша мета полягає в тому, щоб довести: «Для всіх$k\in\mathbb{N}$, якщо$P(k)$ правда, $P(k+1)$то істинно».] Нехай$k\in\mathbb{N}$ і припустимо, що$P(k)$ це правда. [Зробіть щось, щоб вивести $P(k+1)$це правда.] Тому$P(k+1)$ це правда.

Таким чином, за$P(n)$ індукцією, вірно для всіх$n\in\mathbb{N}$.

Доведіть наступні кілька теорем за допомогою індукції. Перший результат може виглядати знайомим з обчислення. Нагадаємо$\displaystyle \sum_{i=1}^{n}i=1+2+3+\cdots +n$, що за визначенням.

Теорема 4.4. Для всіх$n\in\mathbb{N}$,$\displaystyle \sum_{i=1}^{n}i=\frac{n(n+1)}{2}$.

Теорема 4.5. На всіх$n\in\mathbb{N}$ 3 ділення$4^{n}-1$.

Теорема 4.6. На всіх$n\in\mathbb{N}$ 6 ділень$n^{3}-n$.

Теорема 4.7. $p_{1}, p_{2}, \ldots, p_{n}$Дозволяти бути$n$ різні точки, розташовані на колі. Тоді кількість відрізків ліній, що з'єднують всі пари точок, дорівнює$\frac{n^{2}-n}{2}$.

Проблема 4.8. Розглянемо сітку квадратів, тобто$2^n$ квадрати шириною$2^n$ квадратів довжиною, де$n\in\mathbb{N}$. Один з квадратів вирізаний, але ви не знаєте, який саме! У вас є купа L-образних форм, що складаються з$3$ квадратів. Доведіть, що ви можете ідеально покрити цю шахову дошку з L-подібними формами (без перекриття) для будь-якого$n\in\mathbb{N}$. На малюнку 4.1 зображено одне можливе покриття для справи за участю$n=2$.

$4.1.jpg$
Малюнок 4.1: Одне з можливих покриттів для справи за участю n = 2 для завдання 4.8.