3.6: Математична індукція - сильна форма

Можливо, ви чули про цифри Фібоначчі. Вони часто зустрічаються в математиці та науках про життя. Вони навіть були застосовані для вивчення фондового ринку! Числа Фібоначчі утворюють послідовність, кожен член якої, крім перших двох, є сумою попередніх двох чисел. Математично, якщо позначити\(n\) й число Фібоначчі\(F_n\), то\[F_n = F_{n-1} + F_{n-2}. \label{eqn:FiboRecur}\] Це називається рецидивним відношенням для\(F_n\).

Деякі студенти мають проблеми з використанням\ ref {eqn:FiboreCur}: ми не додаємо\(n-1\)\(n-2\) і. Індекси вказують лише на місця розташування послідовності Фібоначчі. Отже,\(F_1\) означає перше число\(F_2\) Фібоначчі, друге число Фібоначчі тощо. Порівняйте це з скиданням десяти чисел у десять коробок, і кожна коробка позначена цифрами від 1 до 10. \(a_i\)Скористаємося для позначення значення в\(i\) полі. Коли ми говоримо\(a_7\), ми не маємо на увазі число 7. Замість цього ми маємо на увазі число, що зберігається в Box 7. Виражене словами відношення повторення\ ref {eqn:FiboreCur} говорить нам про\(n\) те, що число Фібоначчі - це сума\((n-1)\) го і\((n-2)\) го чисел Фібоначчі. Це легко запам'ятати: складаємо останні два числа Фібоначчі, щоб отримати наступне число Фібоначчі.

Відношення повторення має на увазі, що нам потрібно почати з двох початкових значень. Ми часто починаємо з\(F_0=0\) (зображення у\(F_0\) вигляді нульового числа Фібоначчі, числа, що зберігається в коробці 0) і\(F_1=1\). Ми об'єднаємо рекуррентне відношення for\(F_n\) і його початкові значення разом в одному визначенні:

\ [F_0=0,\ квадрад F_1=1,\ qquad
F_n = F_ {n-1} + F_ {n-2},\ квадратний\ mbox {для} n\ geq2\ nonumber\]

Ми повинні вказати, що рекуррентне відношення є дійсним лише тоді\(n\geq2\), коли, тому що це найменше значення,\(n\) для якого ми можемо використовувати відношення повторення. Що станеться, якщо ви хочете знайти\(F_1\) за допомогою цієї формули? Ви отримаєте\(F_1=F_0+F_{-1}\), але\(F_{-1}\) не визначено!

Сума нульового та першого чисел Фібоначчі дає нам друге число Фібоначчі:\[F_2 = F_1 + F_0 = 1 + 0 = 1. \nonumber\] Продовжуючи таким чином, ми знаходимо\[ \begin{array}{lclclcl} F_3 &=& F_2+F_1 &=& 1+1 &=& 2, \\ F_4 &=& F_3+F_2 &=& 2+1 &=& 3, \\ F_5 &=& F_4+F_3 &=& 3+2 &=& 5, \\ F_6 &=& F_5+F_4 &=& 5+3 &=& 8, \\ \hfil\vdots&& \hfil\vdots && \hfil\vdots && \vdots \end{array} \nonumber\] Слідуючи цій схемі, які значення\(F_7\) і\(F_8\)?

Числа Фібоначчі користуються багатьма цікавими властивостями, і є численні результати щодо чисел Фібоначчі. Як стартер розглянемо властивість\[F_n < 2^n, \qquad n\geq1. \nonumber\] Як би ми це довели індукцією?

Оскільки ми хочемо довести, що нерівність тримається для всіх\(n\geq1\), ми повинні перевірити випадок\(n=1\) в базовому кроці. Коли\(n=1\), у нас\(F_1=1\) якого, звичайно, менше\(2^1=2\). В індуктивній гіпотезі ми припускаємо, що нерівність тримається, коли\(n=k\) для деякого цілого числа\(k\geq1\); тобто ми припускаємо\[F_k < 2^k \nonumber\] для деякого цілого числа\(k\geq1\). Далі ми хочемо довести, що нерівність все ще тримається, коли\(n=k+1\). Тому нам потрібно довести, що\[F_{k+1} < 2^{k+1}. \nonumber\]

Щоб скористатися індуктивною гіпотезою, нам потрібно застосувати рецидивне відношення чисел Фібоначчі. Це говорить нам, що\(F_{k+1}\) це сума попередніх двох чисел Фібоначчі; тобто єдине,\[F_{k+1} = F_k + F_{k-1}. \nonumber\] що ми знаємо з індуктивної гіпотези, це\(F_k < 2^k\). Отже, як вона стоїть, вона нам багато про що не розповідає\(F_{k+1}\).

Засіб полягає в тому, щоб припустити в індуктивній гіпотезі, що нерівність також тримається, коли\(n=k-1\); тобто ми також припускаємо, що\[F_{k-1} < 2^{k-1}. \nonumber\] Тому, на відміну від усіх проблем, які ми бачили до цього часу, індуктивний крок у цій проблемі спирається на останні два\(n\) -значення замість одного. Що стосується доміно, уявіть, що вони настільки важкі, що нам потрібна комбінована вага двох доміно, щоб збити наступне. Потім\[F_{k+1} = F_k + F_{k-1} < 2^k + 2^{k-1} = 2^{k-1}(2+1) < 2^{k-1} \cdot 2^2 = 2^{k+1}, \nonumber\], який завершить індукцію. Ця модифікована індукція відома як сильна форма математичної індукції. На відміну від цього, ми називаємо звичайну математичну індукцію слабкою формою індукції.

Доказ все ще має незначний глюк! Щоб мати можливість використовувати індуктивну гіпотезу в рецидивних відносині\[F_{k+1} = F_k + F_{k-1}, \nonumber\] обидва\(k\) індекси і\(k-1\) повинні бути не менше 1, тому що твердження стверджує, що\(F_n < 2^n\) для всіх\(n\geq1\). Це означає, що нам потрібно\(k\geq2\). Отже, на базовому кроці ми повинні припустити, що нерівність тримається принаймні для перших двох значень\(n\).

З точки зору ефекту доміно починається ланцюгова реакція падаючих доміно\(k=2\). Треба переконатися, що перші два доміно впадуть, так що їх сукупна вага зб'є третє доміно. Тоді комбінований вага другого і третього доміно буде збивати над четвертим доміно. Ланцюгова реакція буде тривати нескінченно довго.

Символічно звичайна математична індукція спирається на підтекст\(P(k) \Rightarrow P(k+1)\). Іноді,\(P(k)\) одного недостатньо, щоб довести\(P(k+1)\). У випадку доведення\(F_n < 2^n\), ми насправді використовуємо\[[P(k-1) \wedge P(k)] \Rightarrow P(k+1). \nonumber\] Ми повинні припустити в індуктивній гіпотезі, що результат вірний, коли\(n=k-1\) і\(n=k\).

Більш загально, у сильній формі математичної індукції ми можемо використовувати стільки попередніх випадків, скільки хочемо довести\(P(k+1)\).

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

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

Ідея індуктивного кроку полягає в тому, щоб показати, що\[[\,P(n_0)\wedge P(n_0+1)\wedge\cdots\wedge P(k-1)\wedge P(k)\,] \Rightarrow P(k+1). \nonumber\] Нам, можливо, не потрібно використовувати все\(P(n_0),P(n_0+1),\ldots,P(k-1),P(k)\). Насправді нам можуть знадобитися лише останні кілька з них, наприклад,\(P(k-3),P(k-2),P(k-1)\) і\(P(k)\). Кількість попередніх випадків, необхідних для встановлення,\(P(k+1)\) повідомляє нам, скільки початкових випадків ми повинні перевірити на базовому кроці. Ми не знаємо, скільки нам потрібно до індуктивного кроку. З цієї причини розумно почати з протягу.

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

Покажіть, що\(F_n<2^n\) для всіх\(n\geq1\).

Зауваження

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

Відповідь

Приступайте до індукції далі\(n\). Коли\(n=1\) і\(n=2\), ми знаходимо\[\displaylines{ F_1 = 1 < 2 = 2^1, \cr F_2 = 1 < 4 = 2^2. \cr} \nonumber\] Тому нерівність тримається коли\(n=1, 2\). Припустимо, що він тримає для\(n=1,2,\ldots,k\), де\(k\geq2\). Зокрема, у нас є\[F_k < 2^k, \qquad\mbox{and}\qquad F_{k-1} < 2^{k-1}, \nonumber\] де\(k\geq2\). Тоді\[F_{k+1} = F_k + F_{k-1} < 2^k + 2^{k-1} = 2^{k-1} (2+1) < 2^{k-1}\cdot 2^2 = 2^{k+1}. \nonumber\] Отже, нерівність все ще тримається\(n=k+1\), коли, що завершує індукцію.

Відношення повторення може бути використано для визначення послідовності. Наприклад, якщо послідовність\(\{a_n\}_{n=1}^\infty\) визначається рекурсивно за\[a_n = 3 a_{n-1} - 2 \qquad \mbox{for } n\geq2, \nonumber\] допомогою with\(a_1=4\), то\[\displaylines{ a_2 = 3a_1 - 2 = 3\cdot4-2 = 10, \cr a_3 = 3a_2 - 2 = 3\cdot10-2 = 28. \cr} \nonumber\] Ідентичність за участю таких послідовностей часто може бути доведена за допомогою індукції.

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

Послідовність\(\{b_n\}_{n=1}^\infty\) визначається як\[b_1 = 5, \quad b_2 = 13, \qquad b_n = 5b_{n-1} - 6b_{n-2} \quad\mbox{for } n\geq3. \nonumber\] Довести, що\(b_n = 2^n+3^n\) для всіх\(n\geq1\).

Відповідь

Приступайте до індукції далі\(n\). Коли\(n=1\), запропонована формула для\(b_n\) говорить\(b_1=2+3=5\), яка узгоджується з початковим значенням\(b_1=5\). Коли\(n=2\), запропонована формула претендує\(b_2=4+9=13\), що знову ж таки узгоджується з визначенням\(b_2=13\). Припустімо, що формула дійсна\(n=1,2,\ldots,k\) для деякого цілого числа\(k\geq2\). Зокрема, припустимо\[b_k = 2^k+3^k, \qquad\mbox{and}\qquad b_{k-1} = 2^{k-1}+3^{k-1}. \nonumber\] Ми хочемо показати, що формула все ще працює, коли\(n=k+1\). Іншими словами, ми хочемо показати, що\[b_{k+1} = 2^{k+1}+3^{k+1}.\nonumber\] Використовуючи рецидивне відношення та індуктивну гіпотезу, ми знаходимо,\[\begin{array}{r c l} b_{k+1} &=& 5b_k - 6b_{k-1} \\ &=& 5(2^k+3^k)-6(2^{k-1}+3^{k-1}) \\ &=& 5\cdot2^k+5\cdot3^k-6\cdot2^{k-1}-6\cdot3^{k-1} \\ &=& 5\cdot2^k+5\cdot3^k-2\cdot3\cdot2^{k-1}-2\cdot3\cdot3^{k-1} \\ &=& 5\cdot2^k+5\cdot3^k-3\cdot2^k-2\cdot3^k \\ &=& 2\cdot2^k+3\cdot3^k \\ &=& 2^{k+1}+3^{k+1} \end{array} \nonumber\] що саме ми хочемо встановити. На цьому індукція закінчена, а значить, і твердження, що\(b_n = 2^n+3^n\).

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

Послідовність\(\{c_n\}_{n=1}^\infty\) визначається як\[c_1 = 7, \quad b_2 = 29, \qquad c_n = 5b_{n-1} - 6b_{n-2} \quad\mbox{for } n\geq3. \nonumber\] Доведіть, що\(c_n = 5\cdot3^n-4\cdot2^n\) для всіх цілих чисел\(n\geq1\).

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

Показати, що всі цілі числа\(n\geq24\) можуть бути виражені як\(4x+9y\) для деяких цілих чисел\(x,y\geq0\).

Визначення

Виразом\(4x+9y\) називається лінійна комбінація 4 і 9,\(x\) і\(y\) називається коефіцієнтами лінійної комбінації.

Зауваження

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

Зауваження

Дух математичної індукції (як слабких, так і сильних форм) використовує те, що ми знаємо про проблему меншого розміру. У слабкому вигляді використовуємо результат від,\(n=k\) щоб встановити результат для\(n=k+1\). У сильній формі ми використовуємо деякі результати,\(n=k,k-1,k-2,\ldots\,\) щоб встановити результат для\(n=k+1\).

Обговорення

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

Уявіть, що ви хочете відправити лист, який вимагає\((k+1)\) -центових поштових витрат, і ви можете використовувати тільки 4-центові і 9-центові марки. Ви могли б спочатку поставити 4-центовий штамп. Тоді вам ще потрібно придумати залишилися поштові витрати\((k+1)-4=k-3\) центів. Якщо ви могли б використовувати 4-центові та 9-центові марки, щоб скласти залишок\((k-3)\) -центових поштових витрат, проблема вирішена. Тому в індуктивній гіпотезі потрібно припустити, що це можна робити при\(n=k-3\).

Щоб весь аргумент працював,\(k-3\) повинен бути в межах діапазону\(n\) -значень, які ми розглядаємо. Так що нам потрібно\(k-3\geq24\); тобто ми хочемо\(k\geq27\). Отже, ми повинні перевірити претензію на\(n=24,25,26,27\) базовому кроці.

Рішення

Приступайте до індукції далі\(n\). Ми знаходимо\[\begin{aligned} 24 &=& 4\cdot6 + 9\cdot0, \\ 25 &=& 4\cdot4 + 9\cdot1, \\ 26 &=& 4\cdot2 + 9\cdot2, \\ 27 &=& 4\cdot0 + 9\cdot3. \end{aligned} \nonumber\] Отже, претензія вірна коли\(n=24,25,26,27\). Припустімо, що це правда, коли\(n=24,25,\ldots,k\) для деякого цілого числа\(k\geq27\). Зокрема, оскільки\(k-3\geq24\), це припущення гарантує, що\[k-3 = 4x+9y \nonumber\] для деяких невід'ємних цілих чисел\(x\) і\(y\). З цього випливає, що\[\begin{array}{r c l} k+1 &=& 4+(k-3) \\ &=& 4+4x+9y \\ &=& 4(1+x)+9y, \end{array} \nonumber\] де\(1+x\) і\(y\) є невід'ємними цілими числами. Це показує, що твердження все ще вірно\(n=k+1\), коли, тим самим завершуючи індукцію.

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

Показати, що всі цілі числа\(n\geq2\) можуть бути виражені як\(2x+3y\) для деяких невід'ємних цілих чисел\(x\) і\(y\).

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

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

Вправи 3.6

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

Використовуйте математичну індукцію, щоб підтвердити ідентичність\[F_1^2+F_2^2+F_3^2+\cdots+F_n^2 = F_n F_{n+1} \nonumber\] для будь-якого цілого числа\(n\geq1\).

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

Використовуйте індукцію, щоб підтвердити таку ідентичність для всіх цілих чисел\(n\geq1\):\[F_1+F_3+F_5+\cdots+F_{2n-1} = F_{2n}. \nonumber\]

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

Використовуйте індукцію, щоб довести, що\[\frac{F_1}{F_2F_3} + \frac{F_2}{F_3F_4} + \frac{F_3}{F_4F_5} + \cdots + \frac{F_{n-2}}{F_{n-1}F_n} = 1 - \frac{1}{F_n} \nonumber\] для всіх цілих чисел\(n\geq3\).

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

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

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

Футбольна команда може забити гол поля за 3 очки або ¹ тачдаун (з конверсією) за 7 очок. Доведіть, що для будь-якого цілого числа\(n\geq12\), це можливо для футбольної команди, щоб набрати\(n\) очки з поля голів і touchdowns.

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

Острівна країна випускає лише монети 1, 5 центів та 9 центів. Через дефіцит міді все 1-центові монети були відкликані. Доведіть, що, використовуючи тільки 5 центів і 9-центових монет, можна заплатити\(n\) -цент покупки для будь-якого\(n\geq32\).

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

Послідовність\(\{b_n\}_{n=1}^\infty\) визначається рекурсивно за\[b_n = 3 b_{n-1} - 2 \qquad \mbox{for } n\geq2, \nonumber\] допомогою\(b_1=4\). Використовуйте індукцію, щоб довести це\(b_n=3^n+1\) для всіх\(n\geq1\).

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

Послідовність\(\{c_n\}_{n=1}^\infty\) визначається рекурсивно як\[c_1=3, \quad c_2=-9, \qquad c_n = 7c_{n-1} - 10c_{n-2}, \quad\mbox{for } n\geq3. \nonumber\] Використовувати індукцію, щоб показати, що\(c_n = 4\cdot2^n-5^n\) для всіх цілих чисел\(n\geq1\).

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

Послідовність\(\{d_n\}_{n=1}^\infty\) визначається рекурсивно як\[d_1=2, \quad d_2=56, \qquad d_n = d_{n-1} + 6d_{n-2}, \quad\mbox{for } n\geq3. \nonumber\] Використовувати індукцію, щоб показати, що\(d_n = 5(-2)^n+4\cdot3^n\) для всіх цілих чисел\(n\geq1\).

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

Послідовність\(\{a_n\}_{n=1}^\infty\) визначається рекурсивно як\[a_1=2, \quad a_2=4, \qquad a_n = 2a_{n-1} + 3a_{n-2}, \quad\mbox{for } n\geq3. \nonumber\] Використовувати індукцію, щоб показати, що\(a_n > \left(\frac{5}{2}\right)^n\) для будь-якого цілого числа\(n\geq4\).

---

1. Хоча команда може набрати 2 бали за безпеку або 8 балів за приземлення з двоочним перетворенням, ми б не розглядали ці можливості в цій спрощеній версії справжньої футбольної гри. ↩