2.5: Індукція

Template:MathJaxLevin

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

Штампи

Досліджуйте!

Вам потрібно надіслати посилку, але поки не знаєте, скільки поштових витрат вам знадобиться. У вас великий запас 8-центових марок і 5-центових марок. Які суми поштових витрат ви можете зробити саме за допомогою цих марок? Які суми неможливо внести?

Можливо, розслідуючи проблему вище, ви вибрали деякі суми поштових витрат, а потім з'ясували, чи можете ви зробити цю суму, використовуючи лише 8-центові та 5-центові марки. Можливо, ви зробили це по порядку: чи можете ви зробити 1 цент поштових витрат? Чи можете ви зробити 2 центи? 3 центи? І так далі. Якщо це те, що ви зробили, ви насправді відповідали на послідовність питань. У нас є методи для роботи з послідовностями. Давайте подивимося, чи це допомагає.

Власне, ми будемо складати не послідовність питань, а скоріше послідовність висловлювань. Нехай\(P(n)\) буде твердження «ви можете зробити\(n\) копійки поштових, використовуючи лише 8-центові та 5-центові марки». Оскільки для кожного значення\(n\text{,}\)\(P(n)\) є твердженням, воно є або істинним, або помилковим. Так що, якщо ми формуємо послідовність тверджень

\ почати {рівняння*} P (1), P (2), P (3), P (4),\ ldots\ end {рівняння*}

послідовність буде складатися з\(T\)'s (для true) та\(F\)'s (для false). У нашому конкретному випадку послідовність починається

\ почати {рівняння*} F, F, F, F, T, F, T, F, F, F, F, F, T,\ ldots\ end {рівняння*}

тому що\(P(1), P(2), P(3), P(4)\) всі неправдиві (ви не можете зробити 1, 2, 3 або 4 центи поштових витрат), але\(P(5)\) це правда (використовуйте один 5-центовий штамп), і так далі.

Давайте трохи подумаємо про те, як ми могли б знайти значення\(P(n)\) для якогось конкретного\(n\) («значення» буде\(T\) або\(F\)). Як ми знайшли значення\(n\) го члена послідовності чисел? Як ми знайшли\(a_n\text{?}\) Існували два способи, які ми могли б зробити це: або була замкнута формула,\(a_n\text{,}\) щоб ми могли підключитися до формули і отримати наше вихідне значення, або ми мали рекурсивне визначення для послідовності, так що ми могли б використовувати попередні терміни послідовності для обчислення\(n\) \(n\)термін. При роботі з послідовностями тверджень, ми могли б використовувати будь-який з цих методів, а також. Можливо, є спосіб використовувати\(n\) себе, щоб визначити, чи можемо ми зробити\(n\) копійки поштових витрат. Це було б щось на зразок закритої формули. Або замість цього ми могли б використовувати попередні терміни в послідовності (заяв), щоб визначити, чи можемо ми зробити\(n\) центи поштових витрат. Тобто, якщо ми знаємо значення\(P(n-1)\text{,}\) може ми отримати від цього до значення Це було б\(P(n)\text{?}\) щось на зразок рекурсивного визначення для послідовності. Пам'ятайте, що пошук рекурсивних визначень для послідовностей часто було простіше, ніж пошук замкнутих формул. Те ж саме і тут.

Припустимо, я сказав вам,\(P(43)\) що це правда (це так). Чи можете ви визначити з цього факту значення\(P(44)\) (правда воно чи брехня)? Так, ви можете. Навіть якщо ми не знаємо, як саме ми зробили 43 центи з 5-центових і 8-центових марок, ми знаємо, що існує якийсь спосіб зробити це. Що робити, якщо таким чином використовується щонайменше три 5-центові марки (15 центів)? Ми могли б замінити ці три 5-центові марки двома 8-центовими марками (16 центів). Загальна вартість поштових витрат зросла на 1, тому у нас є спосіб зробити 44 центи, так\(P(44)\) це правда. Звичайно, ми припускали, що у нас є як мінімум три 5-центові марки. Що робити, якщо ми цього не зробили? Тоді ми повинні мати принаймні три 8-центові марки (що складають 24 центи). Якщо ми замінимо ці три 8-центові марки з п'ятьма 5-центовими марками (що робить 25 центів), то знову ми наштовхнулися на нашу загальну суму на 1 цент, так що ми можемо зробити 44 центів, так що\(P(44)\) це правда.

Зверніть увагу, що ми не сказали, як зробити 44 центи, тільки що ми можемо, виходячи з того, що ми можемо зробити 43 центи. Звідки ми знаємо, що можемо зробити 43 центи? Можливо тому, що ми знаємо, що можемо\(42\) заробляти центи, що ми знаємо, що можемо зробити, тому що знаємо, що можемо зробити 41 цент, і так далі. Це рекурсія! Як і при рекурсивному визначенні числової послідовності, ми повинні вказати наше початкове значення. У цьому випадку початковим значенням\(P(1)\) є «false». Це не добре, оскільки наше відношення повторення просто говорить, що\(P(k+1)\) це правда, якщо\(P(k)\) це також правда. Починати процес потрібно з істинного\(P(k)\). Таким чином, замість цього, ми могли б хотіти використовувати «\(P(31)\)є істинним» як початкова умова.

Збираючи це все разом, ми приходимо до наступного факту: можна (точно) зробити будь-яку суму поштових витрат більше 27 центів, використовуючи лише 5-центові та 8-центові марки. ⁴ Це не стверджує, що немає сум менше 27 центів, які також можна зробити. Іншими словами,\(P(k)\) вірно для будь-якого\(k \ge 28\). Щоб довести це, ми могли б зробити наступне:

1. Продемонструйте, що\(P(28)\) це правда.
2. Доведіть, що якщо\(P(k)\) це правда, то\(P(k+1)\) є істинним (для будь-якого\(k \ge 28\)).

Припустимо, ми це зробили. Тоді ми знаємо, що 28-й член послідовності вище є\(T\) (використовуючи крок 1, початкова умова або базовий випадок), і що кожен член після 28-го\(T\) також (використовуючи крок 2, рекурсивну частину або індуктивний випадок). Ось як насправді виглядатиме доказ.

Доказ

Нехай\(P(n)\) буде твердження «можна зробити рівно\(n\) копійки поштових відправлень, використовуючи 5-центові і 8-центові марки». Ми покажемо\(P(n)\) вірно для всіх\(n \ge 28\).

По-перше, ми показуємо, що\(P(28)\) це правда:\(28 = 4 \cdot 5+ 1\cdot 8\text{,}\) тому ми можемо зробити\(28\) центи, використовуючи чотири 5-центові марки та одну 8-центову марку.

Тепер\(P(k)\) припустимо, вірно для деяких довільних\(k \ge 28\). Тоді можна зробити\(k\) центи, використовуючи 5-центові і 8-центові марки. Зауважте, що\(k \ge 28\text{,}\) оскільки не може бути, що ми використовуємо менше трьох 5-центових марок і менше трьох 8-центових марок: використання двох з кожного дасть лише 26 центів. Тепер, якщо ми зробили\(k\) центи, використовуючи принаймні три 5-центові марки, замініть три 5-центові марки двома 8-центовими марками. Це замінює 15 центів поштових витрат на 16 центів, переходячи від загальної кількості\(k\) центів до\(k+1\) центів. \(P(k+1)\)Це правда. З іншого боку, якщо ми зробили\(k\) центи, використовуючи принаймні три 8-центові марки, то ми можемо замінити три 8-центові марки п'ятьма 5-центовими марками, рухаючись від 24 центів до 25 центів, даючи загальну суму\(k+1\) копійок поштових витрат. Так що і в цьому випадку так само\(P(k+1)\) вірно.

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

Формалізація доказів

Те, що ми зробили в прикладі штампа вище, працює для багатьох типів проблем. Доказ індукцією корисний при спробі довести твердження про всі натуральні числа, або всі натуральні числа, більші за певний фіксований перший випадок (як 28 у прикладі вище), і в деяких інших ситуаціях теж. Зокрема, індукцію слід використовувати, коли є якийсь спосіб перейти від одного випадку до іншого — коли можна побачити, як завжди «зробити ще один».

Це велика ідея. Мислення про проблему індуктивно може дати нове розуміння проблеми. Наприклад, щоб дійсно зрозуміти проблему штампа, вам слід подумати про те, як може бути здійснена будь-яка сума поштових відправлень (більше 28 центів) (це неіндуктивні міркування), а також про те, як змінюються способи, за допомогою яких поштові витрати можуть бути внесені у міру збільшення суми (індуктивні міркування). Коли вас просять надати доказ шляхом індукції, вас просять динамічно думати про проблему; як збільшення\(n\) змінює проблему?

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

Ось загальна структура доказу математичною індукцією:

Індукційна доказ Структура

Почніть з того, що твердження полягає в тому, що ви хочете довести: «Нехай\(P(n)\) буде твердженням...» Щоб довести, що\(P(n)\) це вірно для всіх,\(n \ge 0\text{,}\) ви повинні довести два факти:

1. Базовий випадок: Доведіть, що\(P(0)\) це правда. Ви робите це безпосередньо. Це часто легко.
2. Індуктивний випадок: Доведіть, що\(P(k) \imp P(k+1)\) для всіх\(k \ge 0\). Тобто довести, що для будь-якого\(k \ge 0\) якщо\(P(k)\) вірно, то\(P(k+1)\) вірно, а також. Це є доказом if... then... твердження, так що ви можете припустити, що\(P(k)\) це правда (\(P(k)\)називається індуктивною гіпотезою). Потім ви повинні пояснити, чому\(P(k+1)\) це також правда, враховуючи це припущення.

Припускаючи, що ви успішні з обох частин вище, ви можете зробити висновок: «Тому за принципом математичної індукції твердження\(P(n)\) вірно для всіх»\(n \ge 0\).

Іноді твердження\(P(n)\) буде істинним лише для значень,\(n \ge 4\text{,}\) наприклад, або якогось іншого значення. У таких випадках замініть всі 0 вище на 4 (або інше значення).

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

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

Подумайте про наше вивчення послідовностей. Легше знайти рекурсивні визначення для послідовностей, ніж замкнуті формули. Переходити від одного випадку до іншого простіше, ніж перейти безпосередньо до конкретного випадку. Ось що так чудово в індукції. Замість того, щоб перейти безпосередньо до (довільного) випадку для\(n\text{,}\) нас просто потрібно сказати, як перейти від одного випадку до іншого.

Коли вас просять довести твердження математичною індукцією, слід спочатку задуматися про те, чому твердження вірно, використовуючи індуктивні міркування. Поясніть, чому індукція - це правильно робити, і приблизно чому індуктивний випадок буде працювати. Потім сядьте і випишіть ретельне, формальне доказ, використовуючи структуру вище.

Приклади

Ось кілька прикладів доказів математичною індукцією.

Приклад\(\PageIndex{1}\)

Доведіть для кожного натурального числа\(n \ge 1\), що\(1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}\).

Відповідь

По-перше, давайте індуктивно подумаємо про це рівняння. Насправді ми знаємо, що це вірно з інших причин (зворотне і додавання приходить на розум). Але чому може бути застосована індукція? Ліва сторона складає цифри від 1 до\(n\). If we know how to do that, adding just one more term (\(n+1\)) would not be that hard. For example, if \(n = 100\text{,}\) suppose we know that the sum of the first 100 numbers is \(5050\) (so \(1 + 2 + 3 + \cdots + 100 = 5050\text{,}\) which is true). Now to find the sum of the first 101 numbers, it makes more sense to just add 101 to 5050, instead of computing the entire sum again. We would have \(1 + 2 + 3 + \cdots + 100 + 101 = 5050 + 101 = 5151\). In fact, it would always be easy to add just one more term. This is why we should use induction.

Тепер формальний доказ:

Доказ

Нехай\(P(n)\) be the statement \(1 + 2 + 3 + \cdots + n = \frac{n(n+2)}{2}\). We will show that \(P(n)\) is true for all natural numbers \(n \ge 1\).

Базовий випадок:\(P(1)\) is the statement \(1 = \frac{1(1+1)}{2}\) which is clearly true.

Індуктивний випадок: Нехай\(k \ge 1\) be a natural number. Assume (for induction) that \(P(k)\) is true. That means \(1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}\). We will prove that \(P(k+1)\) is true as well. That is, we must prove that \(1 + 2 + 3 + \cdots + k + (k+1) = \frac{(k+1)(k+2)}{2}\). To prove this equation, start by adding \(k+1\) to both sides of the inductive hypothesis:

\ begin {рівняння*} 1 + 2 + 3 +\ cdots + k + (k+1) =\ frac {k (k+1)} {2} + (k+1). \ end {рівняння*}

Тепер, спрощуючи праву сторону, отримуємо:

\ почати {вирівнювати*}\ розрив {k (k+1)} {2} + k+1\ амп =\ frac {k (k+1)} {2} +\ гідророзриву {2 (k+1)} {2}\\ амп =\ frac {k (k+1) + 2 (к+1)} {2}\\ амп =\ frac {(k+2) (к+1)} {2}\\ амп =\ frac {(к+2) (к+1) {2}. \ end {вирівнювати*}

Таким чином\(P(k+1)\) is true, so by the principle of mathematical induction \(P(n)\) is true for all natural numbers \(n \ge 1\).

Зауважимо, що в тій частині доказу, в якій ми довели\(P(k+1)\),\(P(k)\text{,}\) ми використовували рівняння\(P(k)\). Це була індуктивна гіпотеза. Бачити, як використовувати індуктивні гіпотези, як правило, прямо вперед при доведенні факту про таку суму. В інших доказах це може бути менш очевидним, де він вписується.

Приклад\(\PageIndex{2}\)

Доведіть, що для всіх\(n \in \N\text{,}\)\(6^n - 1\) кратна 5.

Рішення

Знову почніть з розуміння динаміки проблеми. Що означає збільшення\(n\) do? Let's try with a few examples. If \(n = 1\text{,}\) then yes, \(6^1 - 1 = 5\) is a multiple of 5. What does incrementing \(n\) to 2 look like? We get \(6^2 - 1 = 35\text{,}\) which again is a multiple of 5. Next, \(n = 3\text{:}\) but instead of just finding \(6^3 - 1\text{,}\) what did the increase in \(n\) do? We will still subtract 1, but now we are multiplying by another 6 first. Viewed another way, we are multiplying a number which is one more than a multiple of 5 by 6 (because \(6^2 - 1\) is a multiple of 5, so \(6^2\) is one more than a multiple of 5). What do numbers which are one more than a multiple of 5 look like? They must have last digit 1 or 6. What happens when you multiply such a number by 6? Depends on the number, but in any case, the last digit of the new number must be a 6. And then if you subtract 1, you get last digit 5, so a multiple of 5.

Справа в тому, що кожен раз, коли ми множимо лише на ще одну шість, ми все одно отримуємо число з останньою цифрою 6, тому віднімання 1 дає нам кратну 5. Тепер формальний доказ:

Доказ

Нехай\(P(n)\) be the statement, “\(6^n - 1\) is a multiple of 5.” We will prove that \(P(n)\) is true for all \(n \in \N\).

Базовий випадок:\(P(0)\) is true: \(6^0 -1 = 0\) which is a multiple of 5.

Індуктивний випадок: Нехай\(k\) be an arbitrary natural number. Assume, for induction, that \(P(k)\) is true. That is, \(6^k - 1\) is a multiple of \(5\). Then \(6^k - 1 = 5j\) for some integer \(j\). This means that \(6^k = 5j + 1\). Multiply both sides by \(6\text{:}\)

\ почати {рівняння*} 6^ {k+1} = 6 (5j+1) = 30j + 6. \ end {рівняння*}

Але ми хочемо знати про\(6^{k+1} - 1\text{,}\) so subtract 1 from both sides:

\ begin {рівняння*} 6^ {k+1} - 1 = 30j + 5. \ end {рівняння*}

Звичайно\(30j+5 = 5(6j+1)\text{,}\) so is a multiple of 5.

Тому\(6^{k+1} - 1\) is a multiple of 5, or in other words, \(P(k+1)\) is true. Thus, by the principle of mathematical induction \(P(n)\) is true for all \(n \in \N\).

Ми повинні були бути трохи розумними (тобто використовувати деяку алгебру), щоб знайти\(6^k - 1\) внутрішню частину,\(6^{k+1} - 1\) перш ніж ми могли застосувати індуктивну гіпотезу. Це те, що може зробити індуктивні докази складними.

У двох прикладах вище ми почали з\(n = 1\) або\(n = 0\). Ми можемо почати пізніше, якщо нам потрібно.

Приклад\(\PageIndex{3}\)

Доведіть, що\(n^2 \lt 2^n\) для всіх цілих чисел\(n \ge 5\).

Рішення

По-перше, ідея аргументу. Що відбувається, коли ми збільшуємо\(n\) by 1? On the left-hand side, we increase the base of the square and go to the next square number. On the right-hand side, we increase the power of 2. This means we double the number. So the question is, how does doubling a number relate to increasing to the next square? Think about what the difference of two consecutive squares looks like. We have \((n+1)^2 - n^2\). This factors:

\ почати {рівняння*} (n+1) ^2 - n^2 = (n+1-n) (n+1+n) = 2n+1. \ end {рівняння*}

Але подвоєння правої сторони збільшує її на\(2^n\text{,}\) since \(2^{n+1} = 2^n + 2^n\). When \(n\) is large enough, \(2^n > 2n + 1\).

Те, що ми говоримо тут, це те, що кожного разу\(n\) increases, the left-hand side grows by less than the right-hand side. So if the left-hand side starts smaller (as it does when \(n = 5\)), it will never catch up.

Тепер формальний доказ:

Нехай\(P(n)\) be the statement \(n^2 \lt 2^n\). We will prove \(P(n)\) is true for all integers \(n \ge 5\).

Базовий випадок:\(P(5)\) is the statement \(5^2 \lt 2^5\). Since \(5^2 = 25\) and \(2^5 = 32\text{,}\) we see that \(P(5)\) is indeed true.

Індуктивний випадок: Нехай\(k \ge 5\) be an arbitrary integer. Assume, for induction, that \(P(k)\) is true. That is, assume \(k^2 \lt 2^k\). We will prove that \(P(k+1)\) is true, i.e., \((k+1)^2 \lt 2^{k+1}\). To prove such an inequality, start with the left-hand side and work towards the right-hand side:

\ begin {align*} (k+1) ^2\ amp = k^2k+ 1\ ампер\\ ампер\ lt 2^k + 1\ ампер\ ldots\ текст {за індуктивною гіпотезою.}\\ ампер\ lt 2^k\ ампер\ ldots\ текст {з} 2k + 1\ lt 2^k\ text {для} k\ ge 5.\\ ампер = 2^ {к+1}. \ amp\ end {вирівнювати*}

Слідуючи рівності та нерівності через, ми отримуємо\((k+1)^2 \lt 2^{k+1}\text{,}\) in other words, \(P(k+1)\). Therefore by the principle of mathematical induction, \(P(n)\) is true for all \(n \ge 5\).

\(\square\)

Попередній приклад може нагадати вам про принцип іподрому з обчислення, який говорить, що якщо\(f(a) \lt g(a)\text{,}\) і\(f'(x) \lt g'(x)\) для того\(x > a\text{,}\),\(f(x) \lt g(x)\) для\(x > a\). Та ж ідея: більша функція збільшується швидше, ніж менша функція, тому більша функція залишатиметься більшою. У дискретній математиці ми не маємо похідних, тому ми дивимося на відмінності. Таким чином, індукція - це шлях.

Попередження:

З великою силою настає велика відповідальність. Індукція - це не магія. Це здається дуже потужним, щоб мати можливість припустити\(P(k)\), що це правда. Адже ми намагаємося довести, що\(P(n)\) це правда і різниця лише в змінній:\(k\) vs\(n\). Чи припускаємо ми, що те, що ми хочемо довести, є правдою? Не зовсім. Ми припускаємо\(P(k)\), що це правда тільки заради того, щоб довести, що\(P(k+1)\) це правда.

Тим не менш, ви можете почати вірити, що ви можете довести що завгодно за допомогою індукції. Розглянемо це некоректне «доказ» того, що кожен канадець має однаковий колір очей:\(P(n)\) Нехай твердження про те, що будь-які\(n\) канадці мають однаковий колір очей. \(P(1)\)правда, так як кожен має такий же колір очей, як і вони самі. Тепер припустимо\(P(k)\), що це правда. Тобто припустимо, що в будь-якій групі\(k\) канадців у всіх однаковий колір очей. Тепер розглянемо довільну групу\(k+1\) канадців. Перший\(k\) з них повинен мати однаковий колір очей, оскільки\(P(k)\) це правда. Крім того, останній\(k\) з них повинен мати однаковий колір очей, оскільки\(P(k)\) це правда. Так що насправді, всі групи повинні мати однаковий колір очей. \(P(k+1)\)Це правда. Так що за принципом математичної індукції,\(P(n)\) вірно для всіх\(n\).

Ясно щось пішло не так. Проблема полягає в тому, що доказ, який\(P(k)\) має на увазі,\(P(k+1)\) передбачає це\(k \ge 2\). Ми тільки показали,\(P(1)\) що це правда. По суті,\(P(2)\) є помилковим.

Сильна індукція

Досліджуйте!

Почніть з квадратного аркуша паперу. Ви хочете розрізати цей квадрат на менші квадрати, не залишаючи відходів (кожен аркуш паперу, з яким ви закінчуєте, повинен бути квадратом). Очевидно, що можна розрізати квадрат на 4 квадрата. Також можна розрізати його на 9 квадратів. Виходить можна розрізати квадрат на 7 квадратів (хоча і не всі однакового розміру). Які ще числа квадратів ви могли б в кінцевому підсумку з?

Іноді, щоб довести, що\(P(k+1)\) це правда, було б корисно знати, що\(P(k)\) \(P(k-1)\)і\(P(k-2)\) все вірно. Розглянемо наступну головоломку:

У вас є прямокутна плитка шоколаду, складена з\(n\) однакових квадратів шоколаду. Можна взяти таку планку і розбити її уздовж будь-якого ряду або стовпчика. Скільки разів доведеться розбивати плитку, щоб зменшити її до\(n\) одиничних шоколадних квадратів?

Спочатку це питання може здатися неможливим. Можливо, я мав на увазі попросити найменшу кількість перерв, необхідних? Давайте розслідувати.

Почніть з деяких невеликих випадків. Якщо у\(n=2\text{,}\) вас повинен бути\(1\times 2\) прямокутник, який можна звести до одиничних шматочків за один розрив. При\(n=3\text{,}\) цьому ми повинні мати\(1\times 3\) планку, яка вимагає двох перерв: перший розрив створює єдиний квадрат, а\(1\times 2\) бар, який, як ми знаємо, займає один (більше) перерву.

А як щодо\(n=4\text{?}\) Тепер у нас може бути\(2\times 2\) бар, або\(1 \times 4\) бар. У першому випадку розбийте планку на два\(2\times 2\) стовпчики, кожен з яких вимагає ще однієї перерви (це всього три перерви потрібно). Якщо ми почали з\(1 \times 4\) бару, у нас є вибір для нашої першої перерви. Ми могли б розбити планку навпіл, створивши два\(1\times 2\) бари, або ми могли б зламати один квадрат, залишивши\(1\times 3\) бар. Але так чи інакше, нам все одно потрібні ще дві перерви, даючи в цілому три.

Він починає виглядати як незалежно від того, як ми розбиваємо планку (і незалежно від того, як\(n\) квадрати розташовані в прямокутник), у нас завжди буде однакова кількість необхідних перерв. Це також виглядає так, що число на одиницю менше\(n\text{:}\)

Гіпотеза 2.5.4

Враховуючи\(n\) квадратний прямокутний шоколадний батончик, він завжди робить\(n-1\) перерви, щоб зменшити плитку до одиничних квадратів.

Має сенс довести це індукцією, тому що після того, як зламавши плитку один раз, ви залишаєтеся з меншими шоколадними плитками. Зведення до менших випадків - це те, що таке індукція. Ми можемо індуктивно припустити, що ми вже знаємо, як боротися з цими меншими брусками. Проблема полягає в тому, що якщо ми намагаємося довести індуктивний випадок про\((k+1)\) -квадратний бар, ми не знаємо, що після першого розриву решта бар матиме\(k\) квадрати. Тому нам дійсно потрібно припустити, що наша здогадка вірна для всіх випадків менше, ніж\(k+1\).

Чи справедливо зробити це сильніше припущення? Пам'ятайте, в індукції ми намагаємося довести, що\(P(n)\) це вірно для всіх\(n\). Що робити, якби це було не так? Тоді було б деякі перші,\(n_0\) для яких\(P(n_0)\) було помилковим. Оскільки\(n_0\) це перший зустрічний приклад, ми знаємо, що\(P(n)\) вірно для всіх\(n \lt n_0\). Тепер ми приступимо до того, щоб довести,\(P(n_0)\) що насправді вірно, виходячи з припущення,\(P(n)\) яке вірно для всіх менших\(n\).

Це досить перевага: тепер у нас сильніша індуктивна гіпотеза. Ми можемо припустити, що\(P(1)\text{,}\)\(P(2)\text{,}\)\(P(3)\text{,}\)...\(P(k)\) це правда, просто щоб показати, що\(P(k+1)\) це правда. Раніше ми просто припускали\(P(k)\) для цієї мети.

Трохи простіше, якщо ми змінимо наші змінні для сильної індукції. Ось як виглядатиме формальний доказ:

Сильна індукційна доказ структура

Знову ж таки, почніть з того, що ви хочете довести: «Нехай\(P(n)\) буде твердження...» Потім встановіть два факти:

1. Базовий випадок: Доведіть, що\(P(0)\) це правда.
2. Індуктивний випадок:\(P(k)\) Припустимо, вірно для всіх\(k \lt n\). Доведіть, що\(P(n)\) це правда.

Зробіть висновок, «отже, сильною\(P(n)\) індукцією, вірно для всіх»\(n \gt 0\).

Звичайно, допустимо замінити 0 більшим базовим корпусом, якщо це необхідно. ⁵ Технічно сильна індукція не вимагає від вас доводити окремий базовий випадок. Це тому, що, доводячи індуктивний випадок, ви повинні показати, що\(P(0)\) is true, assuming \(P(k)\) is true for all \(k \lt 0\). But this is not any help so you end up proving \(P(0)\) anyway. To be on the safe side, we will always include the base case separately.

Доведемо нашу здогадку про головоломку шоколадного батончика:

Доказ

\(P(n)\)Дозволяти бути твердженням, «потрібно\(n-1\) перерви, щоб зменшити\(n\) -квадратний шоколадний батончик до одиничних квадратів».

Базовий випадок: Розглянемо\(P(2)\). Квадрати повинні бути розташовані в\(1\times 2\) прямокутник, і нам потрібні\(2-1 = 1\) перерви, щоб зменшити це до одиничних квадратів.

Індуктивний випадок: виправте довільний\(n\ge 2\) і припустимо\(P(k)\), що це вірно для всіх\(k \lt n\). Розглянемо\(n\) квадратну прямокутну плитку шоколаду. Розбийте планку один раз уздовж будь-якого рядка або стовпця. Це призводить до двох плиток шоколаду, скажімо, розмірів\(a\) і\(b\). Тобто ми маємо\(a\) квадратну прямокутну плитку шоколаду,\(b\) квадратну прямокутну плитку шоколаду, і\(a+b = n\).

Ми також знаємо, що\(a \lt n\) і\(b \lt n\text{,}\) так за нашою індуктивною гіпотезою,\(P(a)\) і\(P(b)\) є правдою. Для зменшення\(a\) -sqaure бар до одиночних квадратів робить\(a-1\) перерви; щоб зменшити\(b\) -square бар до одиночних квадратів робить\(b-1\) перерви. Це призводить до того, що наш оригінальний бар буде скорочений до одиничних квадратів. Всі разом взяв початкову перерву, плюс\(a-1\) і\(b-1\) перерви, на загальну кількість\(1+a-1+b-1 = a+b-1 = n-1\) перерв. \(P(n)\)Це правда.

Тому сильною індукцією,\(P(n)\) вірно для всіх\(n \ge 2\).

Ось більш математично релевантний приклад:

Приклад\(\PageIndex{5}\)

Доведіть, що будь-яке натуральне число більше 1 або просте або може бути записано як добуток простих чисел.

Рішення

По-перше, ідея: якщо взяти якесь число\(n\text{,}\) maybe it is prime. If so, we are done. If not, then it is composite, so it is the product of two smaller numbers. Each of these factors is smaller than \(n\) (but at least 2), so we can repeat the argument with these numbers. We have reduced to a smaller case.

Тепер формальний доказ:

Доказ

Нехай\(P(n)\) be the statement, “\(n\) is either prime or can be written as the product of primes.” We will prove \(P(n)\) is true for all \(n \ge 2\).

Базовий випадок:\(P(2)\) is true because \(2\) is indeed prime.

Індуктивний випадок: припустимо\(P(k)\) is true for all \(k \lt n\). We want to show that \(P(n)\) is true. That is, we want to show that \(n\) is either prime or is the product of primes. If \(n\) is prime, we are done. If not, then \(n\) has more than 2 divisors, so we can write \(n = m_1 \cdot m_2\text{,}\) with \(m_1\) and \(m_2\) less than \(n\) (and greater than 1). By the inductive hypothesis, \(m_1\) and \(m_2\) are each either prime or can be written as the product of primes. In either case, we have that \(n\) is written as the product of primes.

Таким чином, сильною індукцією,\(P(n)\) is true for all \(n \ge 2\).

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

Як остаточний контраст між двома формами індукції, розглянемо ще раз проблему штампа. Регулярна індукція працювала, показуючи, як збільшити поштові витрати на один цент (або замінивши три 5-центові марки двома 8-центовими марками, або три 8-центові марки з п'ятьма 5-центовими марками). Ми могли б дати дещо інший доказ, використовуючи сильну індукцію. По-перше, ми могли б показати п'ять базових випадків: можна зробити 28, 29, 30, 31 і 32 центи (ми б насправді сказали, як кожен з них зроблений). Тепер припустимо, що можна зробити\(k\) центи поштових витрат за все до тих\(k \lt n\) пір, поки\(k \ge 28\). Поки\(n > 32\text{,}\) це означає, зокрема, ми можемо зробити\(k = n-5\) центи. Тепер додайте 5-центову марку, щоб отримати\(n\) копійки.