6.3: Доказ математичною індукцією II

Навіть там, де немає плутанини між математичною індукцією та «науковою індукцією», студенти часто не оцінюють суть «докази індукцією». Перш ніж проілюструвати це, повторимо основну структуру такого доказу.

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

• сформулювати заявлений результат для кожного значення n окремо: тобто як твердження P (n), яке залежить від n;
• потім голими руками перевірити «початок» — а саме, що найпростіший випадок (зазвичай P (1)) вірний;
• нарешті, знайти спосіб продемонструвати це,

— як тільки ми дізнаємося, що P (k) вірно, для деяких (невідомо)$к\ge 1$,

— ми можемо довести, що наступний результат$\mathbf{Р}(к+1)$потім автоматично істинно

Потім ми можемо зробити висновок, що

«кожне твердження P (n) вірно»,

або що

«P (n) вірно, для всіх$п\ge 1$»

Завдання 229 Доведіть твердження:

«5 ²ⁿ⁺² — 24n — 25 ділиться на 576, для всіх$\mathit{п}⩾1$».

Намагаючись побудувати докази приватно, можна вільно писати все, що допомагає як «чорнова робота». Але передбачувана тяга задачі 229 двояка:

• ввести звичку чітко розрізняти

  (i) твердження P (n) для конкретного n, і

  (ii) твердження, яке потрібно довести, а саме «P (n) вірно, для всіх$п\ge 1$»; і

• звернути увагу на «крок індукції» (тобто третя точка кулі вище), де

  (i) ми припускаємо, що деяке невизначене P (k), як відомо, є істинним, і

  (ii) прагнути довести, що наступне твердження$\mathbf{Р}(к+1)$повинні бути правдою.

Центральним уроком завершення «індукційного кроку» є визнання того, що:

довести, що$\mathbf{Р}(к+1)$правда, потрібно почати, дивлячись на те, що$\mathbf{Р}(к+1)$говорить.

У задачі 229$\mathbf{Р}(к+1)$говорить, що

»$5^{2(к+1)+2}-24(к+1)-25$ділиться на 576».

Отже, слід починати крок індукції з відповідного виразу.

$$\begin{array}{cc}& 5^{2(к+1)+2}-24(к+1)-25,\hfill \end{array}$$

і шукайте якийсь спосіб переставити це в форму, де можна використовувати P (k) (який, як ми вважаємо, вже відомо, є істинним, і тому вільно використовувати).

Це взагалі помилкова стратегія працювати навпаки - «починаючи з P (k), а потім возитися з нею, щоб спробувати отримати$\mathbf{Р}(к+1)$». (Ця стратегія може бути змушена працювати в найпростіших випадках; але вона взагалі не працює, і тому шкідлива звичка потрапити в.) Тож крок індукції завжди повинен починатися з гіпотези$\mathbf{Р}(к+1)$.

Наступна задача пропонує вам довести формулу для суми кутів у будь-якому багатокутнику. Результат добре відомий; але ми впевнені, що читач ніколи не побачив правильного доказу. Отже, намір тут полягає в тому, щоб ви визнати основний характер результату, виявити недоліки в тому, що ви, можливо, досі прийняли як доказ, і спробувати знайти якийсь спосіб отримання загального доказу.

Проблема 230 Доведіть шляхом індукції твердження:

«для кожного$п\ge 3$, кути будь-якого n —кутника в площині мають суму рівну$(п-2)\pi$радіани».

Формулювання, безумовно, передбачає параметр$п\ge 3$; тому вам явно потрібно почати з формулювання твердження P (n). Щоб доказ мав шанс працювати, пошук правильної формулювання передбачає скромний поворот! Так що якщо ви застрягли, можливо, варто перевірити перші пару рядків розчину.

Незалежно від того, як формулюється P (n), ви неодмінно повинні знати, як довести твердження P (3) (по суті формула для суми кутів в трикутнику). Але далеко не очевидно, як довести «індукційний крок»:

«якщо ми знаємо, що P (k) вірно для деяких конкретних$к\ge 1$, потім$\mathbf{Р}(к+1)$також має бути правдою».

При вирішенні індукційного кроку ми, звичайно, не можемо почати з P (k)! Заява$\mathbf{Р}(к+1)$говорить щось про багатокутники з$к+1$сторони: і немає можливості отримати типовий$(к+1)$—gon, возитися з деяким твердженням про багатокутники з k сторін. (Якщо ви починаєте з k—кутника, ви можете, звичайно, намалювати трикутник з одного боку, щоб отримати$(к+1)$—gon; але це дуже особлива конструкція, і немає простого способу дізнатися, чи всі$(к+1)$—gons можна отримати таким чином з деякого k —gon.) Вся суть математичної індукції полягає в тому, що ми завжди повинні починати крок індукції, думаючи про гіпотезу$\mathbf{Р}(к+1)$— тобто в даному випадку, розглядаючи довільний$(к+1)$—gon, а потім знайти певний гарантований спосіб «зменшення» його з метою використання P (k).

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

Проблема 231 Доведіть шляхом індукції твердження:

»$1+3+5+\cdots +(2\mathit{п}-1)={\mathit{п}}^2$тримає, для всіх$\mathit{п}⩾1$»

Підсумовування в задачі 231 було відомо стародавнім грекам. Містична піфагорійська традиція (яка процвітала протягом століть після Піфагора) досліджувала характер цілих чисел через «просторові фігури», які вони сформували. Наприклад, якщо ми організуємо кожне наступне ціле число як новий рядок точок у площині, то сума»$1+2+3+\cdots +\mathit{п}$» можна побачити, що представляє трикутне число. Аналогічно, якщо розташувати кожне непарне число$2\mathit{к}-1$в сумі»$1+2+3+\cdots +\mathit{п}$» як «k -by- k зворотна L-форма», або gnomon (слово, яке ми все ще використовуємо для позначення L-подібного фрагмента, який відкидає тінь на сонячний годинник), то накопичені L-форми створюють n на n квадрат точок - «1» є крапкою у верхньому лівому куті ручний кут, «3» є зворотною L-формою 3 точок, які роблять цей початковий «1» в квадрат 2 на 2, «5" є зворотною L-формою 5 точок, що робить це 2 на 2 квадрат в 3 на 3 квадрат, і так далі. Звідси і сума»$1+3+5+...+(2\mathit{п}-1)$» можна побачити, щоб представляти квадратне число.

Про такі геометричні ілюстрації можна сказати багато, але від того, що вони ховаються за крапкою (трьома крапками), які ми вставили в сумі між «5» і «».$2\mathit{п}-1$», які потім були узагальнені при розташуванні зворотних L-форм, закінчуючи словами «і так далі»). Доказ математичною індукцією та його застосування в задачі 231 складають формальний спосіб уникнути як звернення до зображень, так і прихованого крапки.

Задача 232 Послідовність

$2,5,13,35,...$

визначається його першими двома термінами${\mathit{у}}_0=2,{\mathit{у}}_1=5$, і за співвідношенням повторення:

${\mathit{у}}_{\mathit{п}+2}=$5уп+1−6уп.

(a) Вгадайте замкнуту формулу для n ^-го терміну u _n.

(б) Доведіть шляхом індукції, що ваша здогадка в (а) є правильною для всіх$$п⩾0.

Задача 233 Послідовність чисел Фібоначчі

$0,1,1,2,3,5,8,13,...$

визначається його першими двома термінами${\mathit{F}}_0=0,{\mathit{F}}_1=1$, і за співвідношенням повторення:

${\mathit{F}}_{\mathit{п}+2}={\mathit{F}}_{\mathit{п}+1}+{\mathit{F}}_{\mathit{п}}$коли$$п⩾0.

Доведіть індукцією, що для всіх$$п⩾0,

${\mathit{F}}_{\mathit{п}}=\frac{{\alpha }^{\mathit{п}}-{\beta }^{\mathit{п}}}{\sqrt{5}},$деα=1+52іβ=1−52

Проблема 234 Доведіть індукцією, що

${}^{}$52п+1·2п+2+3п+2·22п+1

ділиться на 19, для всіх$$п⩾0.

Задача 235 Використовуйте математичну індукцію, щоб довести, що кожна з цих ідентичностей має, для всіх$$п⩾1:

(а)$1+2+3+\cdots +\mathit{п}=\frac{\mathit{п}(\mathit{п}+1)}{2}$

(б)$\frac{1}{1·2}+\frac{1}{2·3}+\frac{1}{3·4}+\cdots +\frac{1}{\mathit{п}(\mathit{п}+1)}=1-\frac{1}{\mathit{п}+1}$

(c)$1+\mathit{q}+{\mathit{q}}^2+{\mathit{q}}^3+\cdots +{\mathit{q}}^{\mathit{п}-1}=\frac{1}{1-\mathit{q}}-\frac{{\mathit{q}}^{\mathit{п}}}{1-\mathit{q}}$

(г)$0·0!+1·1!+2·2!+\cdots +(\mathit{п}-1)·(\mathit{п}-1)!=\mathit{п}!-1$

(е)$($cosθ+ягріхθ)п=cosпθ+ягріхпθ.

Проблема 236 Доведіть шляхом індукції твердження:

»$(1+2+3+\cdots +\mathit{п}{)}^2=1^3+2^3+3^3+\cdots +{\mathit{п}}^3$, для всіх$\mathit{п}⩾1$».

Тепер ми знаємо, що для всіх$$п⩾1:

$1+1+1+\cdots +1($пумови)=п.

І якщо підсумувати ці «виходи» (тобто перші n натуральних чисел), то отримаємо n ^-е трикутне число:

$1+2+3+\cdots +\mathit{п}=\frac{\mathit{п}(\mathit{п}+1)}{2}={\mathit{Т}}_{\mathit{п}}$.

Наступна задача пропонує знайти суму цих «виходів»: тобто знайти суму перших n трикутних чисел.

Проблема 237

(a) Експериментуйте і вгадайте формулу для суми перших n трикутних чисел:

${\mathit{Т}}_1+{\mathit{Т}}_2+{\mathit{Т}}_3+\cdots +{\mathit{Т}}_{\mathit{п}}=1+3+6+\cdots +\frac{\mathit{п}(\mathit{п}+1)}{2}.$

(б) Доведіть шляхом індукції, що ваша вгадана формула є правильною для всіх$$п⩾1.

A: Тепер ми знаємо закриті формули для

»$1+2+3+\cdots +\mathit{п}$»

і для

»$1·2+2·3+3·4+\cdots +(\mathit{п}-1)\mathit{п}$».

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

$1^2+2^2+3^2+\cdots +{\mathit{п}}^2$

для перших n кубиків:

$1^3+2^3+3^3+\cdots +{\mathit{п}}^3$

і так далі.

Проблема 238

(a) Зауважте, що$\mathrm{}$

$1·2+2·3+3·4+\cdots +\mathit{п}(\mathit{п}+1)=1·(1+1)+2·(2+1)+3·(3+1)+\cdots +\mathit{п}·(\mathit{п}+1)$.

Скористайтеся цим і результатом завдання 237, щоб вивести формулу для суми:${\mathrm{}}^{}$

$1^2+2^2+3^2+\cdots +{\mathit{п}}^2$.

(b) Вгадайте і доведіть формулу для суми

$1·2·3+2·3·4+3·4·5+\cdots +(\mathit{п}-2)(\mathit{п}-1)\mathit{п}$.

Скористайтеся цим, щоб вивести замкнуту формулу для суми:

$1^3+2^3+3^3+\cdots +{\mathit{п}}^3$.

Може знадобитися трохи зусиль, щоб переварити твердження в наступній задачі. Він розширює ідею «методу невизначеного коефіцієнта», який обговорюється в Примітці 2 до розв'язання задачі 237 (а).

Проблема 239

(а) Враховуючи$\mathit{п}+1$різні дійсні числа

${\mathit{a}}_0,{\mathit{a}}_1,{\mathit{a}}_2\mathrm{,\; ...\; ,}{\mathit{a}}_{\mathit{п}}$

знайти всі можливі поліноми ступеня n, які задовольняють

$$fa0=fa1=fa2=⋯=faп−1=0,faп=б

для деякого вказаного числа b.

(b) Для кожного$$п⩾1, довести наступне твердження:

З урахуванням двох маркованих наборів$\mathit{п}+1$дійсні числа

${\mathit{a}}_0,{\mathit{a}}_1,{\mathit{a}}_2\mathrm{,...},{\mathit{a}}_{\mathit{п}}$,

і

${\mathit{б}}_0,{\mathit{б}}_1,{\mathit{б}}_2,...,{\mathit{б}}_{\mathit{п}}$,

де a _i всі різні (але b не повинні бути), існує многочлен f _{n ступеня n}, такий, що

$$fпa0=б0,fпa1=б1,fпa2=б2,...,fпaп=бп.

Ми закінчуємо цей підрозділ змішаним пакетом з трьох досить різних проблем індукції. У першій задачі крок індукції передбачає просту конструкцію такого роду, яку ми зустрінемо пізніше.

Проблема 240 Країна має всього 3 центові і 4 центові монети.

(а) Експеримент, щоб вирішити, яка, здається, найбільша сума, N центів, яку неможливо сплатити безпосередньо (без отримання змін).

(б) Доведіть шляхом індукції, що «n центів можна заплатити безпосередньо за кожен$\mathit{п}>\mathit{П}$».

Проблема 241

(а) Вирішити рівняння$\mathit{z}+\frac{1}{\mathit{z}}=1$. Розрахувати${\mathit{z}}^2$, і перевірте, що${\mathit{z}}^2+\frac{}{}$1z2також є цілим числом.

(б) Розв'яжіть рівняння$\mathit{z}+\frac{1}{\mathit{z}}=2$. Розрахувати${\mathit{z}}^2+\frac{}{}$1z2, і перевірте, що${\mathit{z}}^2+\frac{}{}$1z2також є цілим числом.

(c) Вирішити рівняння$\mathit{z}+\frac{1}{\mathit{z}}=3$. Розрахувати${\mathit{z}}^2+\frac{}{}$1z2, і перевірте, що${\mathit{z}}^2+\frac{}{}$1z2також є цілим числом.

(d) Розв'яжіть рівняння$\mathit{z}+\frac{1}{\mathit{z}}=\mathit{к}$, де k - ціле число. Обчисліть z ², і перевірте, що${\mathit{z}}^2+\frac{}{}$1z2також є цілим числом.

(e) Доведіть, що якщо число z має властивість, яка$z+\frac{1}{z}$є цілим числом, потім${\mathit{z}}^{\mathit{п}}+\frac{}{}$1zптакож є цілим числом для кожного$$п⩾1.

Завдання 242 Нехай p буде будь-яке просте число. Використовуйте індукцію, щоб довести:

»${\mathit{п}}^{\mathit{р}}-\mathit{п}$ділиться на p для всіх$\mathit{п}⩾1$».