3.5: Детальніше про математичну індукцію

Крім тотожностей, ми також можемо використовувати математичну індукцію, щоб довести твердження про додатне ціле число\(n\).

Приклад\(\PageIndex{1}\label{eg:inductmultsix}\)

Доведіть,\(n(n+1)(2n+1)\) що кратне 6 для всіх цілих чисел\(n\geq1\).

Зауваження

Ми вже бачили, як довести цю претензію за допомогою доказу за випадками, що насправді є простішим способом довести,\(n(n+1)(2n+1)\) що ділиться на 6. Тим не менш, ми продемонструємо нижче, як використовувати індукцію для підтвердження претензії.

Обговорення

У індуктивній гіпотезі зрозуміло, що ми припускаємо, що\(k(k+1)(2k+1)\) кратна 6. На індуктивному етапі ми хочемо довести, що\[(k+1)(k+2)[2(k+1)+1] = (k+1)(k+2)(2k+3)\] це також кратне 6. Кратне 6 може бути записано як\(6q\) для деякого цілого числа\(q\). Так як у нас є два кратні 6, нам потрібно\[(k+1)(k+2)(2k+3) = 6Q\] написати\[k(k+1)(2k+1) = 6q\] і розрізняти їх. Використовуючи малі та великі регістри однієї літери, ми вказуємо, що це різні значення. Тим не менш, оскільки вони походять з однієї літери, вони обидва мають якийсь загальний атрибут, в даному випадку, будучи частками, коли відповідні значення діляться на 6.

Тепер, на індуктивному кроці, нам потрібно використовувати рівняння\(k(k+1)(2k+1)=6q\) з індуктивної гіпотези. Це вимагає підключення продукту\((k+1)(k+2)(2k+3)\) до виразу\(k(k+1)(2k+1)\). Оскільки вони поділяють загальний фактор\(k+1\), що залишається зробити, це написати з\((k+2)(2k+3)\) точки зору\(k(2k+1)\).

Нас просять довести,\(n(n+1)(2n+1)\) що кратна 6. Це не ідентичність. Тому не кажіть «припускати/показуйте, що особистість тримається, коли...». Замість цього скажіть «припустити/показати, що претензія вірна, коли...».

Рішення

Приступайте до індукції далі\(n\). Коли\(n=1\), ми маємо\(n(n+1)(2n+1)= 1\cdot2\cdot3=6\), що явно кратне 6. Отже, претензія вірна коли\(n=1\). Припустімо, що твердження вірно, коли\(n=k\) для деякого цілого числа\(k\geq1\); тобто, припустимо, що ми можемо записати\[k(k+1)(2k+1) = 6q\] для деякого цілого числа\(q\). Ми хочемо показати, що твердження все ще вірно, коли\(n=k+1\); тобто, ми хочемо, щоб показати, що\[(k+1)(k+2)[2(k+1)+1] = (k+1)(k+2)(2k+3) = 6Q\] для деякого цілого числа\(Q\). Використовуючи індуктивну гіпотезу, знаходимо\[\begin{aligned} (k+1)(k+2)(2k+3) &=& (k+1)(2k^2+7k+6) \\ &=& (k+1)[(2k^2+k)+(6k+6)] \\ &=& (k+1)[k(2k+1)+6(k+1)] \\ &=& k(k+1)(2k+1) + 6(k+1)^2 \\ &=& 6q + 6(k+1)^2 \\ &=& 6\,[q+(k+1)^2], \end{aligned}\]\(q+(k+1)^2\) де чітко ціле число. На цьому індукція закінчена.

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

Доведіть,\(n^2+3n+2\) що навіть для всіх цілих чисел\(n\geq1\).

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

Приклад\(\PageIndex{2}\label{eg:induct2-02}\)

Доведіть, що\[1+\frac{1}{4}+\cdots+\frac{1}{n^2} \leq 2-\frac{1}{n}\] для всіх натуральних чисел\(n\).

Чернетка. В індуктивній гіпотезі ми припускаємо, що нерівність тримається, коли\(n=k\) для деякого цілого числа\(k\geq1\). Це означає, що ми припускаємо, що\[\sum_{i=1}^k \frac{1}{i^2} \leq 2-\frac{1}{k}.\] в індуктивному кроці ми хочемо показати, що він також тримається, коли\(n=k+1\). Іншими словами, ми хочемо довести, що\[\sum_{i=1}^{k+1} \frac{1}{i^2} \leq 2-\frac{1}{k+1}.\]

Для того, щоб використовувати індуктивну гіпотезу, ми повинні знайти зв'язок між цими двома нерівностями. Очевидно, що ми маємо\[\sum_{i=1}^{k+1} \frac{1}{i^2} = \left(\sum_{i=1}^k \frac{1}{i^2}\right) + \frac{1}{(k+1)^2}.\] Отже, з індуктивної гіпотези випливає, що\[\sum_{i=1}^{k+1} \frac{1}{i^2} = \left(\sum_{i=1}^k \frac{1}{i^2}\right) + \frac{1}{(k+1)^2} \leq 2-\frac{1}{k} + \frac{1}{(k+1)^2}.\] Доказ був би повним, якби ми могли показати, що\[2-\frac{1}{k} + \frac{1}{(k+1)^2} \leq 2-\frac{1}{k+1}.\] Немає гарантії, що ця ідея спрацює, але це повинно бути першим, що ми спробуємо.

Після перестановки нерівність стає\[\frac{1}{k+1}+\frac{1}{(k+1)^2} \leq \frac{1}{k},\] рівнозначною\(\frac{k+2}{(k+1)^2} \leq \frac{1}{k}\). Перехресне множення дає\[k(k+2) \leq (k+1)^2.\] Оскільки\[k(k+2)=k^2+2k, \qquad\mbox{and}\qquad (k+1)^2=k^2+2k+1,\] зрозуміло, що те, що ми хочемо довести, дійсно вірно.

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

Доказ 1

Приступайте до індукції далі\(n\). Коли\(n=1\), ліва сторона стає 1, як і права сторона; таким чином, нерівність тримається. Припустимо, що він тримає, коли\(n=k\) для\(k\geq1\) деякого цілого числа:\[\sum_{i=1}^k \frac{1}{i^2} \leq 2-\frac{1}{k}.\] Ми хочемо показати, що він також тримає, коли\(n=k+1\):\[\sum_{i=1}^{k+1} \frac{1}{i^2} \leq 2-\frac{1}{k+1}.\]

Щоб закінчити доказ, нам потрібно вивести нерівність. Зверніть увагу, що\[k(k+2) = k^2+2k < k^2+2k+1 = (k+1)^2.\] Отже, розділивши обидві сторони на\(k(k+1)^2\), ми отримуємо\[\frac{k+2}{(k+1)^2} < \frac{1}{k}.\] Це призводить до\[\frac{1}{k+1} + \frac{1}{(k+1)^2} = \frac{(k+1)+1}{(k+1)^2} = \frac{k+2}{(k+1)^2} < \frac{1}{k},\] якого еквівалентно\[-\frac{1}{k} + \frac{1}{(k+1)^2} < -\frac{1}{k+1}. \label{eq:induct2-ineq}\]

Тепер повернемося до нашої первісної проблеми. З індуктивної гіпотези і ([eq:induct2-ineq]) випливає, що\[\begin{aligned} \sum_{i=1}^{k+1} \frac{1}{i^2} &=& \left(\sum_{i=1}^k \frac{1}{i^2}\right) +\frac{1}{(k+1)^2} \\ &\leq& 2-\frac{1}{k} + \frac{1}{(k+1)^2} \\ & < & 2-\frac{1}{k+1}. \end{aligned}\] тому нерівність все ще тримається\(n=k+1\), коли, що завершує індукцію.

Зауваження

Ключовим кроком у доказі є встановлення ([eq:induct2-ineq]), що може бути зроблено за допомогою протиріччя.

Доказ 2

Приступайте до індукції далі\(n\). Коли\(n=1\), ліва сторона стає 1, як і права сторона; таким чином, нерівність тримається. Припустимо, що він тримає, коли\(n=k\) для\(k\geq1\) деякого цілого числа:\[\sum_{i=1}^k \frac{1}{i^2} \leq 2-\frac{1}{k}.\] Ми хочемо показати, що він також тримає, коли\(n=k+1\):\[\sum_{i=1}^{k+1} \frac{1}{i^2} \leq 2-\frac{1}{k+1}.\]

Щоб закінчити доказ, нам знадобиться наступне нерівність. Ми стверджуємо, що\[-\frac{1}{k} + \frac{1}{(k+1)^2} < -\frac{1}{k+1}. \label{eq:induct2-ineqalt}\] Припустимо, навпаки, що\[-\frac{1}{k} + \frac{1}{(k+1)^2} \geq -\frac{1}{k+1}.\] Очистити знаменники шляхом множення\(k(k+1)^2\) на обидві сторони нерівності. Ми знаходимо\[-(k+1)^2 + k \geq -k(k+1),\] або еквівалентно,\[-k^2-k-1 \geq -k^2-k,\] що те саме, що сказати\(-1\geq0\). Це протиріччя доводить, що ([eq:induct2-ineqalt]) має бути істинним.

Тепер повернемося до нашої первісної проблеми. З індуктивної гіпотези випливає і ([eq:induct2-ineqalt]), що\[\begin{aligned} \sum_{i=1}^{k+1} \frac{1}{i^2} &=& \left(\sum_{i=1}^k \frac{1}{i^2}\right) +\frac{1}{(k+1)^2} \\ &\leq& 2-\frac{1}{k} + \frac{1}{(k+1)^2} \\ & < & 2-\frac{1}{k+1}. \end{aligned}\] Тому нерівність все ще тримається коли\(n=k+1\), що завершує індукцію.

практичні вправи\(\PageIndex{2}\label{he:induct2-02}\)

Показати, що\(n < 2^n\) для всіх цілих чисел\(n\geq1\).

Ми не повинні починати з\(n=1\) базового кроку. Ми можемо почати з будь-якого цілого числа\(n_0\).

Узагальнення. Щоб показати,\(P(n)\) що вірно для всіх цілих чисел\(n \geq n_0\), виконайте наступні дії:

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

Основна відмінність полягає в базовому кроці: нам потрібно переконатися, що\(P(n_0)\) це правда. Крім того, в індуктивній гіпотезі нам потрібно підкреслити це\(k\geq n_0\).

Приклад\(\PageIndex{3}\label{eg:induct2-03}\)

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

Рішення

Приступайте до індукції далі\(n\). Коли\(n=0\), ліва сторона зводиться до\(\sum_{i=0}^0 4^i = 4^0 = 1\), а права стає\(\frac{1}{3} (4^1-1) = \frac{1}{3}\cdot3 = 1\). Отже, формула тримає коли\(n=0\). Припустимо, що він тримає, коли\(n=k\) для деякого цілого числа\(k\geq0\); тобто,\[\sum_{i=0}^k 4^i = \frac{1}{3} (4^{k+1}-1).\] припустимо, Ми хочемо показати, що він також тримає, коли\(n=k+1\); тобто,\[\sum_{i=0}^{k+1} 4^i = \frac{1}{3} (4^{k+2}-1).\] Використовуючи індуктивну гіпотезу, ми знаходимо,\[\begin{aligned} \sum_{i=0}^{k+1} 4^i &=& \left(\sum_{i=0}^k 4^i\right) + 4^{k+1} \\ &=& \textstyle\frac{1}{3}\,(4^{k+1}-1) + 4^{k+1} \\ [3pt] &=& \textstyle\frac{1}{3}\,(4^{k+1}-1+3\cdot4^{k+1}) \\ [3pt] &=& \textstyle\frac{1}{3}\,(4\cdot4^{k+1}-1) \\ [3pt] &=& \textstyle\frac{1}{3}\,(4^{k+2}-1), \end{aligned}\] що є те, що ми хочемо довести, тим самим завершуючи індукцію.

практичні вправи\(\PageIndex{3}\label{he:induct2-03}\)

Доведіть, що для будь-якого цілого числа\(n\geq0\),\[1+\frac{2}{3}+\frac{4}{9}+\cdots+\left(\frac{2}{3}\right)^n = 3\,\left[1-\left(\frac{2}{3}\right)^{n+1}\right].\]

Приклад\(\PageIndex{4}\label{eg:induct2-04}\)

Використовуйте математичну індукцію, щоб показати, що\[n^n \geq 2^n\] для всіх цілих чисел\(n\geq2\).

Рішення

Приступайте до індукції далі\(n\). Коли\(n=2\), нерівність стає\(2^2\geq 2^2\), що очевидно вірно. Припустимо, що він тримає, коли\(n=k\) для\(k\geq2\) деякого цілого числа:\[k^k \geq 2^k.\] Ми хочемо показати, що він все ще тримається, коли\(n=k+1\):\[(k+1)^{k+1} \geq 2^{k+1}.\] Оскільки\(k\geq2\), це випливає з індуктивної гіпотези, що\[(k+1)^{k+1} \geq k^{k+1} = k\cdot k^k \geq 2\cdot 2^k = 2^{k+1}.\] Отже, нерівність все ще тримається, коли\(n=k+1\). На цьому індукція закінчена.

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

• Ми можемо використовувати індукцію, щоб довести загальний твердження, що включає ціле число\(n\).
• Заява може бути ідентичністю, нерівністю або претензією про властивість вираження за участю\(n\).
• Індукційний доказ не потрібно починати з\(n=1\).
• Якщо ми хочемо довести, що твердження вірно для всіх цілих чисел\(n\geq n_0\), ми повинні перевірити твердження для\(n=n_0\) в базовому кроці.
• Крім того, потрібно припустити, що\(k\geq n_0\) в індуктивній гіпотезі.

Вправа\(\PageIndex{1}\label{ex:induct2-01}\)

Використовуйте індукцію, щоб довести, що\(n(n+1)(n+2)\) кратна 3 для всіх цілих чисел\(n\geq1\).

Вправа\(\PageIndex{2}\label{ex:induct2-02}\)

Використовуйте індукцію, щоб показати, що\(n^3+5n\) кратна 6 для будь-якого невід'ємного цілого числа\(n\).

Вправа\(\PageIndex{3}\label{ex:induct2-03}\)

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

Вправа\(\PageIndex{4}\label{ex:induct2-04}\)

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

Вправа\(\PageIndex{5}\label{ex:induct2-05}\)

Використовуйте індукцію, щоб довести, що\[a+ar+ar^2+\cdots+ar^n = \frac{a(r^{n+1}-1)}{r-1}\] для всіх невід'ємних цілих чисел\(n\), де\(a\) і\(r\) є дійсними числами с\(r\neq1\).

Вправа\(\PageIndex{6}\label{ex:induct2-06}\)

Використовуйте індукцію, щоб довести, що для будь-якого цілого числа\(n\geq2\),\[6 \sum_{i=2}^n i(i+2) = 2n^3+9n^2+7n-18.\]

Вправа\(\PageIndex{7}\label{ex:induct2-07}\)

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

Вправа\(\PageIndex{8}\label{ex:induct2-08}\)

Використовуйте індукцію, щоб показати, що\(n!>2^n\) для всіх цілих чисел\(n\geq4\).

Вправа\(\PageIndex{9}\label{ex:induct2-09}\)

Використовуйте індукцію, щоб довести, що\(n^2>4n+1\) для всіх цілих чисел\(n\geq5\).

Вправа\(\PageIndex{10}\label{ex:induct2-10}\)

Доведіть, що\(2n+1 < 2^n\) для всіх цілих чисел\(n\geq3\).

Вправа\(\PageIndex{1}\label{ex:induct2-01}\)

Визначте\[S_n = \frac{1}{2!} + \frac{2}{3!} + \frac{3}{4!} + \cdots + \frac{n}{(n+1)!}.\]

1. Оцініть\(S_n\) для\(n=1,2,3,4,5\).
2. Запропонуйте просту формулу для\(S_n\).
3. Використовуйте індукцію, щоб довести свою гіпотезу для всіх цілих чисел\(n\geq1\).

Вправа\(\PageIndex{12}\label{ex:induct2-12}\)

Визначте\(T_n = \sum_{i=0}^n \frac{1}{(2i+1)(2i+3)}\).

1. Оцініть\(T_n\) для\(n=0,1,2,3,4\).
2. Запропонуйте просту формулу для\(T_n\).
3. Використовуйте індукцію, щоб довести свою гіпотезу для всіх цілих чисел\(n\geq0\).