B.2: Індукція на

Last updated
Save as PDF

Page ID: 52731

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

Template:MathJaxZach

У найпростішому вигляді індукція - це техніка, яка використовується для доведення результатів для всіх натуральних чисел. Він використовує той факт, що, починаючи з\(0\) і багаторазово додаючи,\(1\) ми врешті-решт досягаємо кожного натурального числа. Таким чином, щоб довести, що щось вірно для кожного числа, ми можемо (1) встановити, що це вірно для\(0\) і (2) показати, що всякий раз, коли це вірно для числа\(n\), це також вірно для наступного числа\(n+1\). Якщо ми скорочуємо «число\(n\) має властивість\(P\)»\(P(n)\) (і «число\(k\) має властивість\(P\)» і т.д.), то доказ шляхом індукції, що\(P(n)\) для всіх\(P(k)\) \(n \in \Nat\)складається з:

доказ\(P(0)\), і
доказ того, для будь-якого\(k\), якщо\(P(k)\) тоді\(P(k+1)\).

Щоб зробити це кришталево чистим, припустимо, що у нас є обидва (1) і (2). Тоді (1) говорить нам, що\(P(0)\) це правда. Якщо ми також маємо (2), ми знаємо, зокрема, що якщо\(P(0)\) тоді\(P(0+1)\), тобто\(P(1)\). Це випливає із загального твердження «для будь-якого\(k\), якщо\(P(k)\) тоді\(P(k+1)\)» шляхом надягання\(0\) для\(k\). Таким чином, по модусу ponens, у нас є, що\(P(1)\). З (2) знову, тепер беручи\(1\) за\(n\), ми маємо: якщо\(P(1)\) тоді\(P(2)\). Оскільки ми щойно встановили\(P(1)\), за допомогою modus ponens, ми маємо\(P(2)\). І так далі. Для будь-якого числа\(n\), зробивши цей\(n\) раз, ми врешті-решт приходимо до\(P(n)\). Так (1) і (2) разом встановлюють\(P(n)\) для будь-якого\(n \in \Nat\).

Давайте розглянемо приклад. Припустимо, ми хочемо дізнатися, скільки різних сум ми можемо кинути за допомогою\(n\) кубиків. Хоча це може здатися дурним, давайте почнемо з\(0\) кубиків. Якщо у вас немає кубиків, є лише одна можлива сума, яку ви можете «кинути»: жодних точок взагалі, що становить\(0\). Так що кількість різних можливих кидків є\(1\). Якщо у вас є тільки один вмирає\(n=1\), тобто існує шість можливих значень,\(1\) через\(6\). За допомогою двох кубиків ми можемо кинути будь-яку суму\(2\) через\(12\), це\(11\) можливості. За допомогою трьох кубиків ми можемо кинути будь-яке число від\(3\) до\(18\), тобто\(16\) різні можливості. \(1\),\(6\)\(11\),\(16\): виглядає як закономірність: може бути, відповідь є\(5n+1\)? Звичайно,\(5n+1\) це максимально можливий, тому що є лише\(5n+1\) цифри між\(n\), найменшим значенням, яке ви можете кинути\(n\) кубиками (всі\(1\)) і\(6n\), найвищий, який ви можете кинути ( всіх\(6\)).

Теорема\(\PageIndex{1}\)

За допомогою\(n\) кубиків можна кинути всі\(5n+1\) можливі значення між\(n\) і\(6n\).

Доказ. Нехай\(P(n)\) буде претензія: «Можна кинути будь-яке число між\(n\) і\(6n\) за допомогою\(n\) кубиків». Щоб використовувати індукцію, ми доводимо:

Індукційна основа\(P(1)\), тобто за допомогою всього однієї плашки, можна кидати будь-яке число між\(1\) і\(6\).
Крок індукції, для всіх\(k\), якщо\(P(k)\) тоді\(P(k+1)\).

(1) Доведено оглядом\(6\) -односторонньої матриці. Він має всі 6 сторін, і кожне число між\(1\) і\(6\) з'являється на одній зі сторін. Таким чином, можна кинути будь-яке число між\(1\) і\(6\) за допомогою однієї матриці.

Щоб довести (2), ми припускаємо попередник умовного, тобто\(P(k)\). Це припущення називається індуктивної гіпотезою. Ми використовуємо його, щоб довести\(P(k+1)\). Важка частина полягає в тому, щоб знайти спосіб мислення про можливі значення кидка\(k+1\) кістки з точки зору можливих значень кидків\(k\) кістки плюс кидки додаткового\(k+1\) -st die - це те, що ми повинні зробити, хоча, якщо ми хочемо використовувати індуктивну гіпотеза.

Індуктивна гіпотеза говорить, що ми можемо отримати будь-яке число між\(k\) і\(6k\) за допомогою\(k\) кубиків. Якщо ми кидаємо a\(1\) з нашим\((k+1)\) -st die, це додає\(1\) до загальної суми. Таким чином, ми можемо кинути будь-яке значення між\(k+1\) і,\(6k+1\) кидаючи\(5\) кістки, а потім прокатки\(1\) з\((k+1)\) -st die. Що залишилося? Значення\(6k+2\) через\(6k+6\). Ми можемо отримати їх, прокатки\(k\)\(6\) s, а потім число між\(2\) і\(6\) з нашим\((k+1)\) -st померти. Разом це означає, що за допомогою\(k+1\) кубиків ми можемо кинути будь-яке з чисел між\(k+1\) і\(6(k+1)\), тобто, ми довели,\(P(k+1)\) використовуючи припущення\(P(k)\), індуктивну гіпотезу. ◻

Дуже часто ми використовуємо індукцію, коли хочемо довести щось про ряд об'єктів (чисел, множин тощо), який сам визначається «індуктивно», тобто шляхом визначення\((n+1)\) -го об'єкта в терміні\(n\) -го. Наприклад, ми можемо визначити суму\(s_n\) натуральних чисел аж до\(n\)\[\begin{aligned} s_0 & = 0\\ s_{n+1} & = s_n + (n+1)\end{aligned}\] цього визначення дає:\[\begin{aligned} s_0 & = 0,\\ s_1 & = s_0 + 1 && = 1,\\ s_2 & = s_1 + 2 && = 1 + 2 = 3\\ s_3 & = s_2 + 3 && = 1 + 2 + 3 = 6, \text{ etc.}\end{aligned}\] Тепер ми можемо довести, шляхом індукції, що\(s_n = n(n+1)/2\).

Пропозиція\(\PageIndex{1}\)

\(s_n = n(n+1)/2\).

Доказ. Ми повинні довести (1) що\(s_0 = 0\cdot(0 + 1)/2\) і (2) якщо\(s_k = k(k+1)/2\) тоді\(s_{k+1} = (k+1)(k+2)/2\). (1) очевидно. Щоб довести (2), ми припустимо індуктивну гіпотезу:\(s_k = k(k+1)/2\). Використовуючи його, ми повинні це показати\(s_{k+1} = (k+1)(k+2)/2\).

Що таке\(s_{k+1}\)? За визначенням,\(s_{k+1} = s_k + (k+1)\). За індуктивною гіпотезою,\(s_k = k(k+1)/2\). Ми можемо підставити це в попереднє рівняння, а потім просто потрібно трохи арифметики дробів:\[\begin{aligned} s_{k+1} & = \frac{k(k+1)}{2} + (k+1) = {}\\ & = \frac{k(k+1)}{2} + \frac{2(k+1)}{2} = {}\\ & = \frac{k(k+1) + 2(k+1)}{2} = {}\\ & = \frac{(k+2)(k+1)}{2}. \end{aligned}\] ◻

Важливим уроком тут є те, що якщо ви доказуєте щось про якусь індуктивно визначену послідовність\(a_n\), індукція є очевидним способом. І навіть якщо це не так (як у випадку з можливостями кидків кісток), ви можете використовувати індукцію, якщо ви можете якось пов'язати справу для справи для\(k\).\(k+1\)