8.2: Інші докази за допомогою індукції

Last updated
Save as PDF

Page ID: 65275

$ \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}}$

Не всі докази по індукції стосуються сум:

Приклад$8.2.1$.

Припустимо$a, b, n \in \mathbb{Z}$, з$a \equiv b(\bmod n)$. Показати$a^{k} \equiv b^{k}(\bmod n)$, для всіх$k \in \mathbb{N}^{+}$.

Рішення

Вводимо далі$k$. $P(k)$Визначте, щоб бути твердженням\[a^{k} \equiv b^{k}(\bmod n) .\]

Базовий кейс. Оскільки$a^{1} = a$ і$b^{1} = b$, гіпотеза$a \equiv b(\bmod n)$ говорить нам, що\[a^{1} \equiv b^{1}(\bmod n) ,\]
так Р (1) вірно.
Індукційний крок. Припустімо$P(k − 1)$, що це правда. Це означає, що\[a^{k-1} \equiv b^{k-1}(\bmod n) .\]

За припущенням, ми також маємо\[a \equiv b(\bmod n) .\]

Вправа$5.1.19(3)$ говорить нам, що добуток конгруентних величин є конгруентним, тому ми можемо помножити вищезазначені конгруенції, щоб зробити висновок, що\[\left(a^{k-1}\right)(a) \equiv\left(b^{k-1}\right)(b)(\bmod n) .\]

Іншими словами,\[a^{k} \equiv b^{k}(\bmod n) ,\]

так$P(k)$ і правда.

Тому, за принципом математичної індукції,$P(k)$ вірно для кожного$k \in \mathbb{N}^{+}$.

Вправа$8.2.2$.

Доведіть кожне з наступних тверджень шляхом індукції.

$5^{k} \equiv 5(\bmod 4)$, для кожного$k \in \mathbb{N}^{+}$.
$n^{3} \equiv n(\bmod 3)$для кожного$n \in \mathbb{N}^{+}$.

Принцип математичної індукції є важливим інструментом для доведення речей про послідовності чисел, в яких кожен член визначається з попередніх членів. (Такі послідовності, як кажуть, визначаються «рекурсивно» або «індуктивно».) Числа Фібоначчі - один із відомих прикладів цього. У цьому випадку кожен член - це сума двох попередніх термінів:

Визначення$8.2.3$.

Числа Фібоначчі$F_{1}, F_{2}, F_{3}, \ldots$ визначаються:

$F_{1} = 1$,
$F_{2} = 1$, і
$F_{n} = F_{n−1} + F_{n−2}$для$n \geq 3$.

(Наприклад,$F_{3}=F_{3-1}+F_{3-2}=F_{2}+F_{1}=1+1=2$.) Загалом кожне число Фібоначчі (після$F_{2}$) є сумою двох попередніх чисел Фібоначчі, тому перші кілька чисел Фібоначчі:\ [\ begin {масив} {c||c|c|c|c|c|c|c}
n & 1 & 2 & 3 & 5 & 6 & 7 &\ cdots\\
\ hline F_ {n} & 1 & 1 & 2 & 3 & 5 & 8 & 13 &\ cdots
\ кінець {масив}\]

Приклад$8.2.4$.

Доведіть$\sum_{k=1}^{n} F_{k}=F_{n+2}-1$ для всіх$n \in \mathbb{N}^{+}$.

Рішення

$P(n)$Визначте, щоб бути твердженням\[\sum_{k=1}^{n} F_{k}=F_{n+2}-1 .\]

Базовий кейс. Бо$n = 1$, у нас$P(1)$ є\[\sum_{k=1}^{n} F_{k}=\sum_{k=1}^{1} F_{k}=F_{1}=1=2-1=F_{3}-1=F_{1+2}-1=F_{n+2}-1 ,\]
так вірно.
Індукційний крок. Припустімо$P(n − 1)$, що це правда (і$n \geq 2$). Потім\ [\ почати {вирівнювання}
\ sum_ {k=1} ^ {n} F_ {k} &=\ ліворуч (\ sum_ {k=1} ^ {n-1} F_ {k}\ праворуч) +F_ {n}\ &=\ ліворуч (F_ {(n-1) +2} -1\ вправо) +F_ {n}\\
&=\ ліворуч (F_ {n-1) +2} -1\ вправо) +F_ {n}\\
&=\ ліворуч (F_ {n-1) +1} -1\ праворуч) +F_ {n}\\
&=\ ліворуч (F_ {n+1} +F_ {n}\ праворуч) -1\\
&= F_ {n+2} -1
\ кінець {вирівняний}\]

(Друга лінія: Індукційна гіпотеза, Остання лінія: визначення числа Фібоначчі).

Тому, за принципом математичної індукції,$P(n)$ вірно для кожного$n$. Це засіб$\sum_{k=1}^{n} F_{k}=F_{n+2}-1$ для всіх$n \in \mathbb{N}^{+}$.

Вправа$8.2.5$.

Доведіть кожне твердження індукцією.

$\sum_{k=1}^{n} F_{k}^{2}=F_{n} F_{n+1}$.
$F_{3k}$рівний, для всіх$k \in \mathbb{N}^{+}$.
$F_{4k}$ділиться на 3, для всіх$k \in \mathbb{N}^{+}$.

Індукція також може застосовуватися до інших послідовностей, які визначаються рекурсивно:

Приклад$8.2.6$.

Визначте послідовність$\left\{a_{n}\right\}$ за допомогою:

$a_{1} = 1$, і
$a_{n} = 2a_{n−1} + 1$для$n \geq 2$.

Показати$a_{n} = 2^{n} − 1$ для всіх$n \in \mathbb{N}^{+}$.

Рішення

$P(n)$Визначте, щоб бути твердженням\[a_{n}=2^{n}-1 .\]

Базовий кейс. Бо$n = 1$, ми маємо\[a_{n}=a_{1}=1 \quad \text { and } \quad 2^{n}-1=2^{1}-1=2-1=1 .\]
Оскільки вони рівні, ми знаємо, що$P(1)$ це правда.
Індукційний крок. Припустімо$P(k − 1)$, що це правда (і$k \geq 2$). Це означає, що\[a_{k-1}=2^{k-1}-1 .\]
потім\ [\ почати {вирівняний}
a_ {k} &=2 a_ {k-1} +1\\
&=2\ ліворуч (2^ {k-1} -1\ праворуч) +1\\
&=\ ліворуч (2^ {k} -2\ праворуч) +1\\
&=2^ {k} -1,
\ кінець {вирівняний}\]
\ Перша лінія: визначення$a_{k}$, Друга лінія: Індукційна гіпотеза)
$P(k)$ так вірно.

Тому, за принципом математичної індукції,$P(n)$ вірно для кожного$n$. Це засіб$a_{n} = 2^{n} − 1$ для всіх$n \in \mathbb{N}^{+}$.

Історичне зауваження$8.2.7$.

Італійський математик Фібоначчі відкрив числа Фібоначчі в 1202 році, як відповідь на проблему про зростання популяції кроликів. А саме, припустимо, що:

Ви починаєте з 1 пари новонароджених кроликів (самця і самки).
Кожна самка щомісяця народжує іншу пару кроликів (самця і самку), починаючи з двох місяців. (А кролики ніколи не вмирають.)

Це означає, що пари кроликів, які у вас є на n-му місяці, складаються з пар, які ви вже мали минулого місяця, плюс одна нова пара для кожної пари, яка була у вас два місяці тому. Тому якщо$F_{n}$ число пар в n-му місяці, то$F_{n}=F_{n-1}+F_{n-2}$. Детальніше про цифри Фібоначчі можна прочитати у Вікіпедії.

Вправа$8.2.8$.

Визначте послідовність$\left\{b_{n}\right\}$ за допомогою:
- $b_{1} = 4$, і
- $b_{n} = 3b_{n−1} − 2 for \(n \geq 2$.
  Показати$b_{n} = 3^{n} + 1$ для всіх$n \in \mathbb{N}^{+}$.
Визначте послідовність$\left\{c_{n}\right\}$ за допомогою:
- $c_{1} = 25$, і
- $c_{n} = 4c_{n−1} + 5^{n}$для$n \geq 2$.
  Показати$c_{n} = 5^{n+1}$ для всіх$n \in \mathbb{N}^{+}$.
Визначте послідовність$\left\{d_{n}\right\}$ за допомогою:
- $d_{1} = 3$, і
- $d_{n} = 2d_{n−1} − n + 2$для$n \geq 2$.
  Показати$d_{n} = 2^{n} + n$ для всіх$n \in \mathbb{N}^{+}$.
Визначте послідовність$\left\{e_{n}\right\}$ за допомогою:
- $e_{1} = 2$, і
- $e_{n} = 2e_{n−1} − n + 1$для$n \geq 2$.
  Показати$e_{n} = n + 1$ для всіх$n \in \mathbb{N}^{+}$.

Індукція не тільки для того, щоб довести, що речі рівні. Наприклад, він також може бути використаний для доведення нерівностей:

Приклад$8.2.9$.

Доведіть$2^{n} \geq n$ для всіх$n \in \mathbb{N}^{+}$.

Подряпини. \ [\ begin {вирівняний}
2^ {n} &\ stackrel {?} {>} n\\
2\ крапка 2^ {n-1} &\ стекер {?} {>n}\\
2 (n-1) &\ geq n\\
n &\ geq 2
\ кінець {вирівняний}\]

(Третя лінія: Індукційна гіпотеза, остання лінія:$\sqrt{ }$)

Рішення

$P(n)$Визначте, щоб бути твердженням\[2^{n}>n\]

Базовий кейс. Бо$n = 1$, у нас$P(1)$ є\[2^{n}=2^{1}=2>1=n,\]
так вірно.
Індукційний крок. Припустімо$P(n − 1)$, що це правда (і$n \geq 2$). Це означає, що\[2^{n-1}>n-1 .\]
потім\ [\ почати {вирівняний}
2^ {n} &=2\ cdot 2^ {n-1}\\
&>2 (n-1)\\
&= n+ (n-2)\\
&\ geq n+0\\
&=n,
\ end {вирівняний}\]
(Друга лінія: Індукційна гіпотеза, четверта лінія:$n \geq 2$,
так$n - 2 \geq 0$)$P(n)$ так вірно.

Тому, за принципом математичної індукції,$P(n)$ вірно для кожного натурального числа$n$.

Вправа$8.2.10$.

Доведіть$3^{n} \geq 3n$ для всіх$n \in \mathbb{N}^{+}$. [Підказка: Зверніть увагу, що$3^{n} − 3^{n−1} > 3n − 3(n − 1)$ якщо$n \geq 2$.]
Доведіть$(1 + x)^{n} \geq 1 + nx$ для всіх$x \in \mathbb{R}^{+}$ і всіх$n \in \mathbb{N}^{+}$.

Ось стандартний рада:

Пропозиція$8.2.11$.

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

Вправа$8.2.12$.

(Припускає знайомство з многочленами). Доведіть шляхом індукції на$n$ те,$x^{n} − y^{n}$ що многочлен ділиться на$x − y$, для всіх$n \in N\mathbb{+}$. [Підказка: Що таке$(x − y)x^{n} + y(x^{n} − y^{n})$?]

Вправа$8.2.13$.

(передбачає знайомство з комутативними групами). Припустимо,$(G, +)$ це комутативна група. Для$g \in G$ і$n \in \mathbb{N}^{+}$, ми визначаємо$ng$ рекурсивно, шляхом:\[1 g=g \quad \text { and } \quad(n+1) g=n g+g .\]

Доведіть шляхом індукції на$n$ це$(m + n)g = mg + ng$ для всіх$m, n \in \mathbb{N}^{+}$.

Вправа$8.2.14$

Поясніть, що не так, з наступним відомим «доказом» того, що всі коні мають однаковий колір.

СПРОБА ДОКАЗУ ШЛЯХОМ ІНДУКЦІЇ.

$P(n)$Визначте, щоб бути твердженням

«У кожному наборі n коней всі коні мають однаковий колір».

Базовий кейс. Для$n = 1$, нехай$H$ буде будь-який набір$n$ коней. Так як$n = 1$, є тільки один кінь в$H$, тому очевидно, що всі коні в$H$ мають однаковий колір.
Індукційний крок. Припустимо, для кожного набору$n − 1$ коней, що всі коні мають однаковий колір (і$n \geq 2$). Нехай$H$ буде будь-який набір$n$ коней.

$clipboard_e3e38521075e0cfee7374f1dbacf574b7.png$

Видаліть одного коня$h_{1}$ з$H$, щоб сформувати набір$H_{1}$$n − 1$ коней. За індукційною гіпотезою ми знаємо, що

($8.2.15$) всі коні$H_{1}$ мають однаковий колір.

Тепер видаліть іншого коня$h_{2}$ з,$H$ щоб сформувати інший набір$H_{2}$$n−1$ коней. Застосовуючи гіпотезу індукції знову, ми знаємо, що

($8.2.16$) всі коні в H2 мають однаковий колір.

Тепер вибирайте$h$ бути якимось іншим конем ($h_{1}$ні$h_{2}$). Оскільки$h \neq h_{1}$, ми знаємо$h \in H_{1}$, отже, з ($8.2.15$), ми знаємо, що всі коні$H_{1}$ мають той же колір, що і$h$. Так само, оскільки$h \neq h_{2}$, ми знаємо$h \in H_{2}$, так, з ($8.2.16$), ми знаємо, що всі коні$H_{2}$ також мають той же колір, що і$h$. Це означає, що всі коні$H_{1} \cup H_{2}$ мають однаковий колір (а саме, колір коня$h$). Оскільки зрозуміло, що$H = H_{1} \cup H_{2}$ (тому що$H_{1}$ містить кожного коня$h_{1}$, крім того, що знаходиться в$H_{2}$), ми робимо висновок, що всі коні$H$ мають однаковий колір.

За принципом математичної індукції ми робимо висновок, що в кожному (кінцевому) наборі коней всі коні мають однаковий колір.

$clipboard_e118be0c47c3d8779df58caad12281124.png$

ПОПЕРЕДЖЕННЯ. Математична індукція - це метод, який широко використовується математиками та комп'ютерними вченими. Однак інші вчені (а також філософи) використовують слово «індукція» для позначення зовсім іншого методу міркування: наукова індукція (або «індуктивне міркування») - це процес виведення загального правила з конкретних прикладів. (Це протилежність дедуктивній причині3g, де конкретні висновки виводяться із загальних правил.) Наприклад, вчений може виміряти довжину і ширину дуже багатьох прямокутників і порівняти з площами прямокутників. Він або вона виявить, що область завжди виходила, щоб бути твором довжини з шириною. Тоді вчений зробив би висновок (шляхом індуктивних міркувань), що площа кожного прямокутника є добутком його довжини та ширини. Однак це не є математичним доказом формули для площі прямокутника

Приклад\(8.2.1\).

Вправа\(8.2.2\).

Визначення\(8.2.3\).

Приклад\(8.2.4\).

Вправа\(8.2.5\).

Приклад\(8.2.6\).

Історичне зауваження\(8.2.7\).

Вправа\(8.2.8\).

Приклад\(8.2.9\).

Вправа\(8.2.10\).

Пропозиція\(8.2.11\).

Вправа\(8.2.12\).

Вправа\(8.2.13\).

Вправа\(8.2.14\)

СПРОБА ДОКАЗУ ШЛЯХОМ ІНДУКЦІЇ.