4.2: Принцип індукції

Почнемо з доведення теореми, еквівалентної принципу індукції.

ТЕОРЕМА 4.3. Якщо
(1)\(X \subseteq \mathbb{N}\)
(2)\(0 \in X\)
(3)\((\forall n \in \mathbb{N}) n \in X \Rightarrow(n+1) \in X\),

потім\[X=\mathbb{N}\] обговорення. Ми будемо сперечатися протиріччям. Ми припускаємо, що\(X \neq \mathbb{N}\). Дозвольте\(Y\) бути доповненням\(X\) в\(\mathbb{N}\). Оскільки\(Y\) не порожній, він матиме найменший елемент. Третя гіпотеза теореми не допускає найменшого елемента в\(Y\), крім 0, і це неможливо за допомогою другої гіпотези. Тому\(Y\) обов'язково порожній.

Доказ. Дозвольте\(X\) задовольнити гіпотези теореми. Нехай\[Y=\mathbb{N} \backslash X .\] Ми припускаємо\(Y\), що це не порожній. Так як\(Y \subseteq \mathbb{N}, Y\) добре впорядкований\(\leq\). \(a \in Y\)Дозволяти бути найменшим елементом\(Y\). Зауважимо, що\(a\) це не 0, так як\(0 \in X\). Тому\(a \geq 1\) і є наступником, так\(a-1\) є в,\(\mathbb{N}\) а не в\(Y\). Звідси\(a-1\) є в\(X\). Але потім гіпотезою (3) теореми,\(a-1+1 \in X\). Це протиріччя,\(Y\) тому порожній і\(X=\mathbb{N}\).

ЗАУВАЖЕННЯ. Ми іноді включаємо неформальні обговорення з маркуванням у наші докази, щоб направляти вас у читанні. Це не звичайна практика. Ви не повинні включати такі обговорення у свої докази, якщо ваш інструктор не вимагає цього.

\(4.3\)Теорема легше застосовується в наступному вигляді.

НАСЛІДОК 4.4. Принцип індукції\(P(x)\) Дозволяти формулу в одній змінній. Якщо

(1)\(P(0)\)

(2)\((\forall x \in \mathbb{N}) P(x) \Rightarrow P(x+1)\),

потім\[(\forall x \in \mathbb{N}) P(x) .\] Доказ. Нехай\[\chi_{P}=\{x \in \mathbb{N} \mid P(x)\} .\] Ми хочемо показати це\(\chi_{P}=\mathbb{N}\). За припущенням (1)\(P(0)\), так\(0 \in \chi_{P}\). Припустимо, що\(n \in \chi_{P}\). Потім\(P(n)\). За припущенням (2)\[P(n) \Rightarrow P(n+1) .\] Тому\(P(n+1)\) і\(n+1 \in \chi_{P}\). Оскільки\(n\) є довільним,\[(\forall n \in \mathbb{N}) n \in \chi_{P} \Rightarrow n+1 \in \chi_{P} .\] За теоремою 4.3,\(\chi_{P}=\mathbb{N}\) і\[(\forall x \in \mathbb{N}) P(x)\] Припустимо, що ви хочете показати, що формула\(P(x)\) тримає для всіх натуральних чисел. Аргументуючи індукцією, автор повинен показати, що гіпотези для теореми задоволені. Як правило, автор спочатку це доводить\(P(0)\). Це називається базовим випадком доказу індукцією. Це дуже часто легкий, навіть банальний висновок. Тим не менш, необхідно довести базовий випадок, щоб аргументувати індукцією (чи можете ви це продемонструвати?). Довівши базовий випадок, автор потім доведе другу гіпотезу, а саме, що твердження істинне для довільного натурального числа означає, що воно істинне у наступника цього натурального числа. Це крок індукції. Етап індукції вимагає доведення умовного твердження, яке часто доведено безпосередньо. Важливо розуміти, що автор не стверджує, що\(P\) тримає довільне натуральне число, інакше аргумент був би круговим і недійсним. Швидше автор продемонструє, що якби результат був істинним при довільному натуральному числі, то це було б вірно для подальшого натурального числа. Припущення, яке\(P\) тримається при фіксованому і довільному натуральному числі, називається індукційною гіпотезою. Якщо автор успішно доводить базовий випадок і крок індукції, то припущення Слідство\(4.4\) задовольняються, і\(P\) утримує на всіх натуральних числах.

Пропозиція 4.5. Нехай\(N \in \mathbb{N}\). Потім\[\sum_{n=0}^{N} n=\frac{N(N+1)}{2} .\] обговорення. Це хороший перший приклад доказу шляхом індукції. Аргумент - це прямолінійне застосування методики, а результат представляє історичний та практичний інтерес. Аргументуємо індукцією на верхньому показнику суми. Тобто формула, яку ми доводимо для всіх натуральних чисел, є\[P(x): \sum_{n=0}^{x} n=\frac{x(x+1)}{2} .\] Важливо визначити величину, над якою ви застосовуєте принцип індукції, але деякі автори, які пишуть аргумент для читачів, які знайомі з індукцією, можуть явно не вказати формулу.

Доведено базовий випадок\(N=0\), який відповідає сумі з єдиним числом 0. Потім ми аргументуємо крок індукції. Це наш перший аргумент з використанням принципу індукції. Зверніть пильну увагу на структуру цього доказу. Ви повинні прагнути слідувати умовам про докази шляхом індукції, які ми встановлюємо в цій книзі.

Доказ. Базовий корпус:\(N=0\).

Обговорення. Зверніть увагу, що базовим випадком є твердження\(P(0)\).

Так як\[\sum_{n=0}^{0} n=0=\frac{(0)(1)}{2},\]\(P(0)\) тримає.

Індукційний крок:

Обговорення. Доведено універсальне твердження,\[(\forall x \in \mathbb{N}) P(x) \Rightarrow P(x+1) .\] показавши, що для довільного натурального числа\(N\)\[P(N) \Rightarrow P(N+1) .\] Таким чином ми зводимо доведення універсального твердження до доведення абстрактного умовного твердження. Доведемо отриманий умовний оператор безпосередньо. Тобто припускаємо\(P(N)\) і виводимо\(P(N+1)\). Нагадуємо читачеві, що ми не стверджуємо, що результат тримається на\(N\) - тобто ми не претендуємо\(P(N)\). Швидше, ми доводимо умовне твердження, припускаючи попередню гіпотезу, індукційну гіпотезу та виводячи наслідок. Якщо ви не використовуєте індукційну гіпотезу, ви не сперечаєтеся індукцією. Звичайно, в тілі аргументу це прозоро, без прив'язки до лежать в основі логічних принципів.

Нехай\(N \in \mathbb{N}\) і припустимо, що\[\sum_{n=0}^{N} n=\frac{N(N+1)}{2} .\] Тоді\[\begin{aligned} \sum_{n=0}^{N+1} n &=\left(\sum_{n=0}^{N} n\right)+N+1 \\ &={ }_{I H} \frac{N(N+1)}{2}+N+1 \end{aligned}\] індукційною гіпотезою.

Обговорення. Це хороша звичка і міркування для вашого читача, щоб визначити, коли ви посилаєтеся на індукційну гіпотезу. Ми будемо використовувати індекс,\({ }_{I H}\) щоб вказати, де ми викликаємо гіпотезу індукції.

\[\begin{aligned} \sum_{n=0}^{N+1} n &=\frac{N(N+1)}{2}+N+1 \\ &=\frac{N(N+1)}{2}+\frac{2 N+2}{2} \\ &=\frac{N^{2}+3 N+2}{2} \\ &=\frac{(N+1)((N+1)+1)}{2} . \end{aligned}\]Отже,\[(\forall N \in \mathbb{N}) P(N) \Rightarrow P(N+1) .\] за принципом індукції випливає пропозиція.

Пропозиція 4.6. Нехай\(N \in \mathbb{N}\). Тоді\[\sum_{n=0}^{N} n^{2}=\frac{N(N+1)(2 N+1)}{6} .\] Доказ. Твердження\(P(N)\) полягає в тому, що рівняння (4.7) має місце. Базовий випадок\(N=0\) очевидний: крок\[\sum_{n=0}^{0} n^{2}=\frac{0(0+1)(2 \cdot 0+1)}{6} .\] індукції:

Припустимо, що\(N \in \mathbb{N}\) і\[\sum_{n=0}^{N} n^{2}=\frac{N(N+1)(2 N+1)}{6}\] Ми доводимо, що\[\sum_{n=0}^{N+1} n^{2}=\frac{(N+1)(N+2)(2 N+3)}{6}\] Дійсно\[\begin{aligned} \sum_{n=0}^{N+1} n^{2} &=\left(\sum_{n=0}^{N} n^{2}\right)+(N+1)^{2} \\ &=I H \\ &=\frac{N(N+1)(2 N+1)}{6}+(N+1)^{2} . \\ &=\frac{N(N+1)(2 N+1)}{6}+(N+1)^{2} \\ &=\frac{2 N^{3}+9 N^{2}+13 N+6}{6} \\ & \frac{(N+1)(N+2)(2(N+1)+1)}{6} . \end{aligned}\] Пропозиція випливає з принципу індукції.

Обговорення. Доказ Пропозиції\(4.6\) дуже схожий на доказ Пропозиції 4.5. Ви можете підтвердити алгебраїчні ідентичності в останній частині доказу, оскільки вони не очевидні. Включено достатньо деталей, щоб провести вас через доказ наслідків. Автор доказу по індукції буде вважати, що вам комфортно з технікою, і тим самим може надати менше деталей, ніж вам подобається.

ЗАУВАЖЕННЯ. Є більше Пропозицій\(4.6\),\(4.5\) а не просто доказів. Існують і формули. Дійсно, одне використання індукції полягає в тому, що якщо ви вгадаєте формулу, ви можете використовувати індукцію, щоб довести, що ваша формула правильна. Див. Вправи\(4.12\) та 4.16.

Навіщо потрібен базовий кейс? Розглянемо наступний аргумент для помилкового позову\(\sum_{n=0}^{N} n<\frac{N(N+1)}{2}\). Нехай\(N \in \mathbb{N}\) і припустимо\(P(N)\), де\(P(N)\) твердження\[\sum_{n=0}^{N} n<\frac{N(N+1)}{2} .\] Тоді\[\begin{aligned} \sum_{n=0}^{N+1} n &=\left(\sum_{n=0}^{N} n\right)+N+1 \\ <_{I H} & \frac{N(N+1)}{2}+N+1 \\ &=\frac{N^{2}+3 N+2}{2} \\ &=\frac{(N+1)((N+1)+1)}{2} . \end{aligned}\] Отже,\[(\forall N \in \mathbb{N}) P(N) \Rightarrow P(N+1) .\] Звичайно нерівність легко\(P(N)\) демонструється помилковим. Що пішло не так? Без базового випадку доведення\[(\forall N \in \mathbb{N}) P(N) \Rightarrow P(N+1)\] недостатньо для доведення\((\forall N \in \mathbb{N}) P(N)\). \(P(0)\)Якби були правдою, то\(P(1)\) було б правдою, а\(P(1)\) якби правдою, то\(P(2)\) було б і так далі. Дійсно, якщо ми здатні довести\(P(N)\) для будь-якого\(N \in \mathbb{N}\), то ми знаємо\(P(M)\) для будь-якого натурального числа\(M>N\). Але послідовність висловлювань\(\langle P(0), P(1), P(2), \ldots\rangle\) ніколи не запускається. \(P(N)\)зазнає невдачі для всіх\(N\).

Ще один спосіб думати про індукцію - з точки зору гарантій. Припустимо, ви вирішили купити автомобіль. Спочатку ви йдете до чесного Боба. боб гарантує, що будь-яка машина, яку він продає, піде принаймні на одну милю. Ви купуєте автомобіль, виганяєте його з ділянки, і через 3 милі він ламається і не може бути виправлений. Ви йдете назад сердито, але Боб не дасть вам ваші гроші назад, тому що машина дожила до гарантії.

Тоді ви перетинаєте дорогу до Чесного Джона, Джон гарантує, що якщо він продасть вам машину, як тільки вона почне, вона ніколи не зупиниться. Звучить це досить непогано, тому ви купуєте машину, ставите ключі в запалювання, і... нічого. Машина не заводиться. Джон також не поверне вам ваші гроші, тому що машина не зазнала того, що він стверджував.

Відчуваючи відчай, ви потрапляєте в Honest Stewart's Автомобілі Стюарта поставляються з двома гарантіями:

(1) Автомобіль запуститься і проїде хоча б одну милю.

(2) Незалежно від того, наскільки далеко зайшов автомобіль, його завжди можна проїхати зайву милю.

Ви обмірковуєте це, і врешті-решт вирішуєте, що машина поїде назавжди. Найкраще, що оренда становить всього\(\$ 1\) місяць на перші два місяці. Ви підписуєте договір оренди, і їдете додому досить задоволені собою. \({ }^{1}\)

Існує безліч зручних узагальнень принципу індукції. Перший, який ми обговорюємо, називається сильною індукцією. Це так названо, тому що індукційна гіпотеза сильніша, ніж гіпотеза індукції в стандартній індукції, і, отже, крок індукції іноді легше довести в аргументі сильною індукцією.

НАСЛІДОК 4.8. Сильна індукція Нехай\(P(x)\) буде формула така, що

\({ }^{1}\)Ви маєте рацію, що Принцип індукції гарантує, що ваш автомобіль буде їздити назавжди. Однак, як зазначає ваша мати, коли ви показуєте їй оренду, після перших двох місяців ваш платіж кожного місяця є сумою ваших платежів за попередні два місяці. Скільки ви будете платити через 5 років? (1)\(P(0)\)

(2) Для кожного\(n \in \mathbb{N}\),\[[(\forall x<n) P(x)] \Rightarrow[P(n)]\] то\[(\forall x \in \mathbb{N}) P(x)\] інтуїтивно це не сильно відрізняється від базової індукції. Ви починаєте з базового випадку, і після початку ви можете продовжити через решту натуральних чисел. Різниця полягає лише в кількості припущень, які ви використовуєте, коли доводячи щось сильною індукцією. На практиці це дає перевагу, що на етапі індукції можна звести випадок\(N\) до будь-якого попереднього випадку, а не безпосередньо до попереднього випадку\(N-1\). Зокрема, це спрощує аргументи щодо подільності та цілих чисел.

Обговорення. Зводимо принцип сильної індукції до принципу індукції. Ми досягаємо цього, вводячи формулу\(Q(x)\), яка говорить: «P (y) вірно для всіх\(y<x "\). Сильна індукція\(P(x)\) включена еквівалентна основній індукції на\(Q(x) .\)

ДОКАЗ. Припустимо, що\(P(x)\) задовольняє гіпотези слідства. Дозвольте\(Q(x)\) формулі,\[(\forall y \leq x) P(y)\] де\(y\) знаходиться Всесвіт\(\mathbb{N}\). Тоді\(Q(0) \equiv P(0)\), так і правда. Нехай\(N \in \mathbb{N}\)\(N \geq 1\), і припустимо\(Q(N)\). Так\[(\forall y \leq N) P(y)\] і тому\(P(N+1)\). Звідси\[(\forall n \leq N+1) P(y)\] і таким чином\(Q(N+1)\). Тому\[(\forall x \in \mathbb{N}) Q(x) \Rightarrow Q(x+1)\] за принципом індукції,\[(\forall x \in \mathbb{N}) Q(x) .\] Однак для будь-якого\(N \in \mathbb{N}, Q(N) \Rightarrow P(N)\), тому\[(\forall x \in \mathbb{N}) P(x) .\] сильна індукція особливо корисна при доведенні претензій про поділ. Є приклади техніки по всій главі 7. Результати в главі 7 не потребують глави 5 та глави 6, тому ви можете легко пропустити вперед. Дивіться, наприклад, розділ 7.1, де фундаментальна теорема арітеметики доведена за допомогою сильної індукції. Індукція не повинна починатися з 0, а то і з натурального числа.

НАСЛІДОК 4.9. Дозволяти\(k \in \mathbb{Z}\), і\(P(x)\) бути формулою в одній змінній такий, що

(1)\(P(k)\)

(2)\((\forall x \geq k) P(x) \Rightarrow P(x+1)\).

Потім\[(\forall x \in \mathbb{Z}) x \geq k \Rightarrow P(x)\] обговорення. Це можна довести шляхом визначення нової формули, яка може бути доведена стандартною індукцією. Чи можете ви визначити формулу?