3.4: Математична індукція - вступ

Last updated
Save as PDF

Page ID: 64124

$ \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\geq1$. Ось типовий приклад такої ідентичності:\[1+2+3+\cdots+n = \frac{n(n+1)}{2}.\] Більш загально, ми можемо використовувати математичну індукцію, щоб довести, що$P(n)$ пропозиційна функція вірна для всіх цілих чисел$n\geq1$.

Визначення: Математична індукція

Щоб показати, що пропозиційна функція$P(n)$ істинна для всіх цілих чисел$n\geq1$, виконайте наступні дії:

Основний крок: Переконайтеся, що$P(1)$ це правда.
Індуктивний крок: Показати, що якщо$P(k)$ вірно для деякого цілого числа$k\geq1$,$P(k+1)$ то також вірно.

Базову сходинку ще називають анкерної сходинкою або початковою сходинкою. Ця методика доказування справедлива через наступну теорему.

Теорема$\PageIndex{1}\label{thm:pmi}$: Principle of Mathematical Induction

Якщо$S \subseteq \mathbb{N}$ такий, що

$1\in S$, і
$k\in S \Rightarrow k+1\in S$,

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

Зауваження

Ось ескіз доказу. З (i) ми це знаємо$1\in S$. Потім випливає з (ii) що$2\in S$. Застосовуючи (ii) знову, ми виявляємо, що$3\in S$. Точно так само$4\in S$, потім$5\in S$, і так далі. Оскільки цей аргумент може тривати нескінченно довго, ми вважаємо, що$S = \mathbb{N}$.

З цим аргументом є тонка проблема. Незрозуміло, чому «і так далі» буде працювати. Адже що насправді означає «і так далі» або «продовжувати таким чином»? Чи може це дійсно тривати нескінченно довго? Біда в тому, що у нас немає формального визначення натуральних чисел. Виходить, що ми не можемо повністю довести принцип математичної індукції лише звичайними властивостями для додавання і множення. Отже, ми будемо приймати теорему як аксіому, не даючи жодних формальних доказів.

Хоча ми не можемо надати задовільного доказу принципу математичної індукції, ми можемо використовувати його для обґрунтування обґрунтованості математичної індукції. $S$Дозволяти множина цілих чисел,$n$ для яких пропозиційна функція$P(n)$ істинна. Базовий крок математичної індукції підтверджує це$1\in S$. Індуктивний крок показує, що$k\in S$ має на увазі$k+1\in S$. Тому принцип математичної індукції доводить це$S=\mathbb{N}$. Звідси випливає,$P(n)$ що вірно для всіх цілих чисел$n\geq1$.

Базовий крок і індуктивний крок, разом, довести, що\[P(1) \Rightarrow P(2) \Rightarrow P(3) \Rightarrow \cdots\,.\] Отже,$P(n)$ вірно для всіх цілих чисел$n\geq1$. Порівняйте індукцію з падаючими доміно. Коли випадає перше доміно, воно збиває наступне доміно. Друге доміно по черзі збиває третє доміно. Зрештою, всі доміно будуть збиті з ніг. Але цього не станеться, якщо не будуть дотримані ці умови:

Перше доміно має впасти, щоб почати рух. Якщо вона не впаде, ланцюгової реакції не відбудеться. Це базовий крок.
Відстань між сусідніми доміно має бути встановлено правильно. В іншому випадку певне доміно може впасти вниз, не стукаючись над наступним. Тоді ланцюгова реакція припиниться, і ніколи не буде завершена. Підтримка правої відстані між доміно гарантує, що$P(k)\Rightarrow P(k+1)$ для кожного цілого числа$k\geq1$.

Щоб довести імплікацію\[P(k) \Rightarrow P(k+1)\] в індуктивному кроці, нам потрібно виконати два кроки: припускаючи, що$P(k)$ це правда, то використання його для$P(k+1)$ доведення також вірно. Таким чином, ми можемо вдосконалити індукційний доказ у триступінчасту процедуру:

Переконайтеся, що$P(1)$ це правда.
Припустімо,$P(k)$ що вірно для деякого цілого числа$k\geq1$.
Покажіть, що$P(k+1)$ це також правда.

Другий крок, припущення, яке$P(k)$ є істинним, іноді називають індуктивною гіпотезою або індукційною гіпотезою. Ось як може виглядати математичний індукційний доказ:

Ідея математичної індукції досить проста. Однак він повинен бути доставлений з точністю.

Обов'язково скажіть «Припустимо, що ідентичність тримає деяке ціле число»$k\geq1$. Не кажіть «Припустимо, що це тримає для всіх цілих чисел»$k\geq1$. Якщо ми вже знаємо, що результат тримається на всіх$k\geq1$, то взагалі нічого доводити не потрібно.
Обов'язково вкажіть вимогу$k\geq1$. Це гарантує, що ланцюгова реакція падаючих доміно починається з першого.
Не кажіть «нехай$n=k$» або «нехай»$n=k+1$. Справа в тому, що ви не призначаєте значення$k$ і$k+1$ до$n$. Швидше за все, ви припускаєте, що твердження істинно$k$, коли$n$ дорівнює, і використовуючи його, щоб показати, що оператор також тримає, коли$n$ дорівнює$k+1$.

Приклад$\PageIndex{1}\label{eg:induct1-01}$

Використовуйте математичну індукцію, щоб показати, що\[1+2+3+\cdots+n = \frac{n(n+1)}{2}\] для всіх цілих чисел$n\geq1$.

Обговорення

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

\[1+2+3+\cdots+k = \frac{k(k+1)}{2}.\]

Ми хочемо довести, що$P(k+1)$ це теж правда. Що$P(k+1)$ насправді означає? У ньому йдеться

\[1+2+3+\cdots+(k+1) = \frac{(k+1)(k+2)}{2}.\]

Порівняйте ліві сторони цих двох рівнянь. Перша - це сума$k$ величин, а друга - сума$k+1$ величин, а зайва кількість - останнє число$k+1$. Сума перших$k$ членів - це саме те, що ми маємо на лівій стороні індуктивної гіпотези. Отже, шляхом написання

\[1+2+3+\cdots+(k+1) = 1+2+\cdots+k+(k+1),\]

ми можемо перегрупувати праву частину як

\[1+2+3+\cdots+(k+1) = [1+2+\cdots+k]+(k+1),\]

так що$1+2+\cdots+k$ може бути замінений$\frac{k(k+1)}{2}$, відповідно до індуктивної гіпотези. За допомогою додаткової алгебраїчної маніпуляції ми намагаємося показати, що сума дорівнює$\frac{(k+1)(k+2)}{2}$.

Приступаємо по індукції далі$n$. Коли$n=1$ ліва сторона ідентичності зменшується до 1, а права сторона стає$\frac{1\cdot2}{2}=1$; отже, ідентичність тримається коли$n=1$. Припустимо, що він тримає, коли$n=k$ для деякого цілого числа$k\geq1$; тобто припустимо, що

\[1+2+3+\cdots+k = \frac{k(k+1)}{2}\]

для деякого цілого числа$k\geq1$. Ми хочемо показати, що він також тримається, коли$n=k+1$. Іншими словами, ми хочемо показати, що

\[1+2+3+\cdots+(k+1) = \frac{(k+1)(k+2)}{2}.\]

Використовуючи індуктивну гіпотезу, знаходимо

\[\begin{aligned} 1+2+3+\cdots+(k+1) &=& 1+2+3+\cdots+k+(k+1) \\ &=& \frac{k(k+1)}{2}+(k+1) \\ &=& (k+1)\left(\frac{k}{2}+1\right) \\ &=& (k+1)\cdot\frac{k+2}{2}. \end{aligned}\]

Тому ідентичність також тримається, коли$n=k+1$. На цьому індукція закінчена.

Ми можемо використовувати позначення підсумовування (також зване сигма-позначенням) для скорочення суми. Наприклад, суму в останньому прикладі можна записати як

\[\sum_{i=1}^n i.\]

Буква$i$ - індекс підсумовування. Поставивши$i=1$ під$\sum$ і$n$ вище, ми оголошуємо, що сума починається з$i=1$, і коливається через$i=2$$i=3$, і так далі, поки$i=n$. Кількість, яка слідує,$\sum$ описує закономірність термінів, які ми додаємо в підсумовуванні. Відповідно,

\[\sum_{i=1}^{10} i^2 = 1^2+2^2+3^2+\cdots+10^2.\]

У загальному випадку$\{a_1,a_2,a_3,\ldots\,\}$ позначається сума перших$n$ членів в послідовності$\sum_{i=1}^n a_i$. Зауважте, що

\[\sum_{i=1}^{k+1} a_i = \left(\sum_{i=1}^k a_i\right) + a_{k+1},\]

який забезпечує зв'язок між індукційним доказом$P(k+1)$ та$P(k)$ в ньому.

Приклад$\PageIndex{2}\label{eg:induct1-02}$

Використовуйте математичну індукцію, щоб показати, що для всіх цілих$n\geq1$ чисел\[\sum_{i=1}^n i^2 = 1^2+2^2+3^2+\cdots+n^2 = \frac{n(n+1)(2n+1)}{6}.\]

Відповідь: Приступаємо по індукції далі$n$. Коли$n=1$, ліва сторона зводиться до$1^2=1$, а права сторона стає$\frac{1\cdot2\cdot3}{6}=1$; отже, ідентичність тримається коли$n=1$. Припустимо, що він тримає, коли$n=k$ для деякого цілого числа$k\geq1$; тобто припустимо, що\[\sum_{i=1}^k i^2 = \frac{k(k+1)(2k+1)}{6}\] для деякого цілого числа$k\geq1$. Ми хочемо показати, що він все ще тримається, коли$n=k+1$. Іншими словами, ми хочемо показати, що\[\sum_{i=1}^{k+1} i^2 = \frac{(k+1)(k+2)[2(k+1)+1]}{6} = \frac{(k+1)(k+2)(2k+3)}{6}.\] З індуктивної гіпотези ми знаходимо\[\begin{aligned} \sum_{i=1}^{k+1} i^2 &=& \left(\sum_{i=1}^k i^2\right) + (k+1)^2 \\ &=& \frac{k(k+1)(2k+1)}{6}+(k+1)^2 \\ [3pt] &=& \textstyle\frac{1}{6}\,(k+1)[k(2k+1)+6(k+1)] \\ [3pt] &=& \textstyle\frac{1}{6}\,(k+1)(2k^2+7k+6) \\ [3pt] &=& \textstyle\frac{1}{6}\,(k+1)(k+2)(2k+3). \end{aligned}\] Тому ідентичність також тримається коли$n=k+1$. На цьому індукція закінчена.

Приклад$\PageIndex{3}\label{eg:induct1-03}$

Використовуйте математичну індукцію, щоб показати, що\[3+\sum_{i=1}^n (3+5i) = \frac{(n+1)(5n+6)}{2}\] для всіх цілих чисел$n\geq1$.

Відповідь: Приступайте до індукції далі$n$. Коли$n=1$, ліва сторона зводиться до$3+(3+5)=11$, а права сторона стає$\frac{2\cdot11}{2} =11$; отже, ідентичність тримається коли$n=1$. Припустимо, що він тримає, коли$n=k$ для деякого цілого числа$k\geq1$; тобто припустимо, що\[3+\sum_{i=1}^k (3+5i) = \frac{(k+1)(5k+6)}{2}\] для деякого цілого числа$k\geq1$. Ми хочемо показати, що він все ще тримається, коли$n=k+1$. Іншими словами, ми хочемо показати, що\[3+\sum_{i=1}^{k+1} (3+5i) = \frac{[(k+1)+1]\,[5(k+1)+6]}{2} = \frac{(k+2)(5k+11)}{2}.\] З індуктивної гіпотези ми знаходимо\[\begin{aligned} 3+\sum_{i=1}^{k+1} (3+5i) &=& \left(3+\sum_{i=1}^k (3+5i)\right) + [3+5(k+1)] \\ &=& \frac{(k+1)(5k+6)}{2} + 5k+8 \\ [3pt] &=& \textstyle\frac{1}{2}\,[(k+1)(5k+6)+2(5k+8)] \\ [3pt] &=& \textstyle\frac{1}{2}\,(5k^2+21k+22) \\ [3pt] &=& \textstyle\frac{1}{2}\,(k+2)(5k+11). \end{aligned}\] Це завершує індукцію.

практичні вправи$\PageIndex{1}\label{he:induct1-01}$

Настав час написати власний індукційний доказ. Доведіть, що\[1\cdot2 + 2\cdot3 + 3\cdot4 + \cdots + n(n+1) = \frac{n(n+1)(n+2)}{3}\] для всіх цілих чисел$n\geq1$.

Зауваження

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

Відповідь

для деякого цілого числа$k\geq1$. Ми хочемо показати, що він також тримається, коли$n=k+1$; тобто ми хочемо показати, що

З індуктивної гіпотези випливає, що на\[\begin{aligned} \hskip2in &=& \hskip2in + \hskip1in \\ [6pt] \hskip2in &=& \hskip1in + \hskip1in \\ [6pt] \hskip2in &=& \hskip1in . \end{aligned}\] цьому індукція завершується.

вправа$\PageIndex{2}\label{he:induct1-02}$

Використовуйте індукцію, щоб довести, що для всіх натуральних$n$ чисел\[1\cdot2\cdot3 + 2\cdot3\cdot4 + \cdots + n(n+1)(n+2) = \frac{n(n+1)(n+2)(n+3)}{4}.\]

вправа$\PageIndex{3}\label{he:sumfourn}$

Використовуйте індукцію, щоб довести, що для всіх натуральних$n$ чисел\[1+4+4^2+\cdots+4^n = \frac{1}{3}\,(4^{n+1}-1).\]

Всі три кроки індукційного доказу повинні бути виконані; інакше доказ може бути неправильним.

Приклад$\PageIndex{4}\label{eg:induct1-04}$

Ніколи не намагайтеся довести$P(k)\Rightarrow P(k+1)$ прикладами поодинці. Розглянемо\[P(n): \qquad n^2+n+11 \mbox{ is prime}.\] На індуктивному кроці ми хочемо довести, що\[P(k) \Rightarrow P(k+1) \qquad\mbox{ for \emph{any} } k\geq1.\] Наступна таблиця підтверджує, що це вірно для$1\leq k\leq 8$:\[\begin{array}{|*{10}{c|}} \hline n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline n^2+n+11 & 13 & 17 & 23 & 31 & 41 & 53 & 67 & 83 & 101 \\ \hline \end{array}\] Тим не менш, коли$n=10$,$n^2+n+11=121$ є складовим. Отже$P(9) \nRightarrow P(10)$. Індуктивний крок руйнується при$k=9$.

Приклад$\PageIndex{5}\label{eg:induct1-05}$

Базовий крок не менш важливий. Розглянемо доведення\[P(n): \qquad 3n+2 = 3q \mbox{ for some integer $q$}\] для всіх$n\in\mathbb{N}$. Припустімо$P(k)$, що вірно для деякого цілого числа$k\geq1$; тобто припустимо,$3k+2=3q$ для деякого цілого числа$q$. Тоді\[3(k+1)+2 = 3k+3+2 = 3+3q = 3(1+q).\] Тому,$3(k+1)+2$ може бути написано в тій же формі. Це доводить,$P(k+1)$ що також вірно. Чи слід, що$P(n)$ вірно для всіх цілих чисел$n\geq1$? Ми знаємо, що$3n+2$ не можна записати як кратне 3. У чому проблема?

Рішення: Проблема полягає$P(k)$ в тому, що ми повинні бути істинними принаймні для одного значення,$k$ щоб почати послідовність наслідків\[P(1) \Rightarrow P(2), \qquad P(2) \Rightarrow P(3), \qquad P(3) \Rightarrow P(4), \qquad\ldots\] Індукція не вдається, тому що ми не встановили базовий крок. По суті,$P(1)$ є помилковим. Оскільки перше доміно не падає, ми не можемо навіть запустити ланцюгову реакцію.

Зауваження

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

Резюме та огляд

Математична індукція може бути використана, щоб довести, що твердження про$n$ істинно для всіх цілих чисел$n\geq1$.
Ми повинні виконати три кроки.
На базовому кроці перевірте заяву для$n=1$.
У індуктивній гіпотезі припустимо, що твердження тримає коли$n=k$ для деякого цілого числа$k\geq1$.
На індуктивному етапі використовуйте інформацію, зібрану з індуктивної гіпотези, щоб довести, що твердження також має місце, коли$n=k+1$.
Обов'язково виконайте всі три етапи.
Зверніть увагу на формулювання. На початку уважно стежте за шаблоном. Коли ви відчуваєте себе комфортно з усім процесом, ви можете почати вирішувати самостійно.

Вправа$\PageIndex{1}\label{ex:induct1-01}$

Використовуйте індукцію, щоб довести, що\[1^3+2^3+3^3+\cdots+n^3 = \frac{n^2(n+1)^2}{4}\] для всіх цілих чисел$n\geq1$.

Вправа$\PageIndex{2}\label{ex:induct1-02}$

Використовуйте індукцію, щоб довести, що наступна ідентичність має для всіх цілих чисел$n\geq1$:\[1+3+5+\cdots+(2n-1) = n^2.\]

Вправа$\PageIndex{3}\label{ex:induct1-03}$

Використовуйте індукцію, щоб показати, що\[1+\frac{1}{3}+\frac{1}{3^2}+\cdots+\frac{1}{3^n} = \frac{3}{2}\left(1-\frac{1}{3^{n+1}}\right)\] для всіх натуральних чисел$n$.

Вправа$\PageIndex{4}\label{ex:induct1-04}$

Використовуйте індукцію, щоб встановити наступний ідентифікатор для будь-якого цілого числа$n\geq1$:\[1-3+9-\cdots+(-3)^n = \frac{1-(-3)^{n+1}}{4}.\]

Вправа$\PageIndex{5}\label{ex:induct1-05}$

Використовуйте індукцію, щоб показати, що для будь-якого цілого числа$n\geq1$:\[\sum_{i=1}^n i\cdot i! = (n+1)!-1.\]

Вправа$\PageIndex{6}\label{ex:induct1-06}$

Використовуйте індукцію для підтвердження такої ідентичності для цілих чисел$n\geq1$:\[\sum_{i=1}^n \frac{1}{(2i-1)(2i+1)} = \frac{n}{2n+1}.\]

Вправа$\PageIndex{7}\label{ex:induct1-07}$

Оцініть$\dd\sum_{i=1}^n \frac{1}{i(i+1)}$ за кілька значень$n$. Як ви вважаєте, яким повинен бути результат? Використовуйте індукцію, щоб довести свою здогадку.

Вправа$\PageIndex{8}\label{ex:induct1-08}$

Використовуйте індукцію, щоб довести, що\[\sum_{i=1}^n (2i-1)^3 = n^2(2n^2-1)\] всякий раз, коли$n$ є додатним числом.

Вправа$\PageIndex{9}\label{ex:induct1-09}$

Використовуйте індукцію, щоб показати, що для будь-якого цілого числа$n\geq1$:\[1^2-2^2+3^2-\cdots+(-1)^{n-1}n^2 = (-1)^{n-1}\,\frac{n(n+1)}{2}.\]

Вправа$\PageIndex{10}\label{ex:induct1-10}$

Використовуйте математичну індукцію, щоб показати, що\[\sum_{i=1}^n \frac{i+4}{i(i+1)(i+2)} = \frac{n(3n+7)}{2(n+1)(n+2)}\] для всіх цілих чисел$n\geq1$.