4.3: Повна індукція

Last updated
Save as PDF

Page ID: 65585

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

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

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

\(P(1)\)правда, і
Для всіх\(k \in \mathbb{N}\), якщо\(P(j)\) вірно для всіх\(j\in \mathbb{N}\) таких\(j \leq k\),\(P(k+1)\) то вірно.

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

Зверніть увагу на різницю між звичайною індукцією (теореми 4.2 і 4.9) і повною індукцією. Для індукційного кроку повної індукції ми не тільки припускаємо, що\(P(k)\) це правда, але скоріше\(P(j)\) це вірно для всіх\(j\) від 1 до\(k\). Незважаючи на назву, повна індукція не є сильнішою або потужнішою, ніж звичайна індукція. Варто зазначити, що в будь-який час звичайна індукція є відповідною доказовою технікою, так само як і повна індукція. Отже, коли слід використовувати повну індукцію?

У індуктивному кроці потрібно досягти\(P(k+1)\), і ви повинні запитати себе, в який з попередніх випадків вам потрібно туди потрапити. Якщо все, що вам потрібно, це твердження\(P(k)\), то звичайна індукція - це шлях. Якщо два попередніх випадку,\(P(k - 1)\) і\(P(k)\), необхідно досягти\(P(k + 1)\), то доречна повна індукція. В крайньому випадку, якщо потрібен повний спектр попередніх випадків (тобто всі твердження\(P(1), P(2),\ldots,P(k)\)), то знову слід використовувати повну індукцію.

Зверніть увагу, що в ситуаціях, коли повна індукція доречна, можливо, вам потрібно перевірити більше одного випадку на базовому кроці. Кількість базових випадків, які потрібно перевірити, залежить від того, як потрібно «озирнутися назад» на етапі індукції.

Скелет Доказ 4.26. Ось загальна структура для доказу повною індукцією.

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

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

Таким чином, шляхом повної індукції,\(P(n)\) вірно для всіх цілих чисел\(n \ge a\).

Вирішуючи проблеми в цьому розділі, добре подумайте, скільки базових кроків ви повинні перевірити.

Теорема 4.27. Визначте послідовність чисел по\(a_1 = 1\)\(a_2 = 3\), і\(a_n = 3a_{n-1} - 2a_{n-2}\) для всіх натуральних чисел\(n \geq 3\). Тоді\(a_n = 2^n - 1\) для всіх\(n \in \mathbb{N}\).

Теорема 4.28. Визначте послідовність чисел по\(a_1 = 3, a_2 = 5, a_3 = 9\), і\(a_n = 2a_{n-1} + a_{n-2}-2a_{n-3}\) для всіх натуральних чисел\(n \geq 4\). Тоді\(a_n = 2^n + 1\) для всіх\(n \in \mathbb{N}\).

Проблема 4.29. Послідовність Фібоначчі задається\(f_1=1\)\(f_2=1\), і\(f_n=f_{n-1}+f_{n-2}\) для всіх натуральних чисел\(n \geq 3\). Доведіть, що\(\left(\frac{3}{2}\right)^{n-2}\leq f_n\leq 2^n\) для всіх\(n\in\mathbb{N}\).

Нагадаємо, що теорема 4.9 узагальнена теорема 4.2 і дозволила нам обробляти ситуації, коли базовий випадок був чимось іншим, ніж\(P(1)\). Ми можемо узагальнити повну індукцію таким же чином, але ми не будемо записувати це як формальну теорему.

Проблема 4.30. Доведіть, що кожна сума поштових витрат, яка принаймні\(12\) центів може бути зроблена з\(4\) -cent і\(5\) -cent марок.

Проблема 4.31. Whoziwhatsits приходять у коробках 6, 9 і 20. Доведіть, що для будь-якого натурального числа\(n \geq 44\), можна купити саме\(n\) Whoziwhatsits з комбінацією цих коробок.

Проблема 4.32. Розглянемо сітку квадратів, яка є\(2\) квадратами шириною і\(n\) квадратами довжиною. Використовуючи\(n\) доміно,\(1\) квадратні за\(2\) квадратами, є багато способів ідеально покрити цю шахову дошку без перекриття. Скільки? Доведіть свою відповідь.

Проблема 4.33. Двійковий рядок довжини\(n\) - це впорядкований список\(n\) цифр таким чином, що кожна цифра дорівнює 0 або 1. Наприклад\(011101\) і\(011011\) є окремими двійковими рядками довжиною 6. Ось правила двійкового пасьянсу: На будь-якому етапі вам дозволено:

Поміняти місцями крайню ліву цифру (тобто змінити 0 на 1, або 1 на 0). Наприклад, ми можемо зробити\(011101\to 11101\).

Поміняти місцями цифру відразу праворуч від крайнього лівого входження 1. Наприклад, ми можемо зробити\(011011\to 010011\).

Доведіть, що для всіх\(n\in\mathbb{N}\), ви можете змінити будь-який двійковий рядок довжини\(n\) в будь-який інший двійковий рядок тієї ж довжини.

Проблема 4.34. Доведіть, що кількість двійкових рядків довжини\(n\), які ніколи не мають двох послідовних 1 є числом Фібоначчі\(f_{n+2}\). Див. Задача 4.29 для визначення чисел Фібоначчі.