6.10: Коментарі та рішення

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

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

228.

(а) Так.

(б) Так.

$$2\times 3\times 5\times 7\times 11+1=2311,і$ \sqrt{2311}=48.07...$,\; тому\; нам\; потрібно\; лише\; перевірити\; прості\; множники\; до$ 47$.$$

(c) Ні.

$$2\times 3\times 5\times 7\times 11\times 13+1=30031,$$

і$\sqrt{30031}=173.29...$тому нам, можливо, доведеться перевірити всі$40$можливі прості множники до$173$. Однак нам залишається лише почати з$17$[Чому?] , І перевірка за допомогою калькулятора дуже швидка. Фактично$30031$фактури досить гарно, як$59\times 509$.

229. Примітка: Постановка в задачі включає квантор «для всіх$п\ge 1$».

Що потрібно довести, так це складне твердження

»$Р(п)$вірно для всіх$п\ge 1$».

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

Важливо бути зрозумілим, коли ви маєте справу зі складним твердженням, і коли ви маєте на увазі якесь конкретне твердження$Р(1)$, або$Р(п)$, або$Р(к)$.

Нехай$Р(п)$бути твердженням:

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

•$Р(1)$це твердження:

»$5^4-24\times 1-25$ділиться на$576$».

Тобто:

»$625-49=576$ділиться на$576$»,

що, очевидно, вірно.

• Тепер припустимо, що ми знаємо$Р(к)$вірно для деяких$к\ge 1$. Ми повинні показати, що$Р(к+1)$тоді також вірно.

Щоб довести, що$Р(к+1)$правда, ми повинні розглянути твердження$Р(к+1)$. Це не має сенсу, починаючи з$Р(к)$. Однак, оскільки ми знаємо, що$Р(к)$) правда, ми вільні використовувати його на будь-якому етапі, якщо він виявиться корисним.

Щоб довести, що$Р(к+1)$правда, ми повинні показати, що

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

Отже, ми повинні почати з$5^{2(к+1)+2}-24(к+1)-25$і спробувати «спростити» його (знаючи, що «спростити» в даному випадку означає «переписати його таким чином, що передбачає${}^{}$52к+2−24к−25»).

$\begin{array}{c}{5}^{2(к+1)+2}-24(к+1)-25\hfill \\ \hfill & =\left[5^{2к+4}\right]-24к-24-25\hfill \\ \hfill & =[5^2(5^{2к+2}-24к-25)+5^2\cdot \left(24к\right)+5^2\cdot 25]\hfill \\ \hfill & -24к-(24+25)\hfill \\ \hfill & =5^2(5^{2к+2}-24к-25)+[(5^2-1)\times \left(24к\right)]\hfill \\ \hfill & +[5^2\times 25-24-25]\hfill \\ \hfill & =5^2(5^{2к+2}-24к-25)+24^2к+[5^2\times 25-24-25]\hfill \\ \hfill & =5^2(5^{2к+2}-24к-25)+24^2к+[5^4-24-25].\hfill \end{array}$

Перший термін на RHS є кратним$({}^{}$52к+2−24к−25), так ділиться на$576$(Оскільки ми знаємо, що P (k) вірно); другий член на RHS кратний 24 ² = 576; а третій член на RHS - це вираз, що виникає в P (1), який ми бачили дорівнює 576.

$\therefore$весь RHS ділиться на$576$

$\therefore$LHS ділиться на$576$, так$Р(к+1)$це правда.

Звідси

• $Р(1)$вірно; і
• щоразу$Р(к)$вірно для деяких$к\ge 1$, ми довели, що$Р(к+1)$має бути правдою.

$\therefore$ $Р(п)$вірно для всіх$п\ge 1$.

230. Нехай$Р(п)$бути твердженням:

«кути будь-якого p -кутника, для будь-якого значення p з$3\le р\le п$, мати суму точно$(р-2)\pi$радіани».

1. $Р(3)$це твердження:

   «кути будь-якого трикутника мають суму$\pi$радіани».

   Це відомий факт: заданий трикутник ΔABC, проведіть лінію$$ХAУчерез A паралельно$БC$, з X на тій же стороні$AC$як B і Y на одній стороні$AБ$як С. Тоді$\angle ХAБ=\angle CБA$і$\angle УAC=\angle БCA$(чергуються кути), так

   $$\angle Б+\angle A+\angle C=\angle ХAБ+\angle A+\angle УAC=\angle ХAУ=\pi .$$
2. Тепер ми припускаємо, що$Р(к)$як відомо, вірно для деяких$к\ge 3$. Ми повинні показати, що$Р(к+1)$то обов'язково вірно.

Щоб довести, що$Р(к+1)$правда, ми повинні розглянути твердження$Р(к+1)$: тобто,

«кути p -кутника, для будь-якого значення p з$3\le р\le к+1$, мати суму точно$(р-2)\pi$радіани»

Це можна переформулювати, розділивши його на дві частини:

«кути будь-якого p -кутника для$3\le р\le к$мати суму точно$(р-2)\pi$радіани;»

і

«кути будь-якого (k + 1) -кутника мають суму точно$((к+1)-2)\pi$радіани».

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

Нехай$A_0{A}_1{A}_2\cdots A_{к}$бути будь-яким (k + 1) -кутник.

[Примітка: Звичайний хід у цей момент полягає в тому, щоб сказати «намалювати акорд»$$AкA1вирізати багатокутник в трикутник$$AкA1A0(з кутовою сумою$\pi$(по$Р(3)$), і k -кутник$A_1{A}_2\cdots A_{к}$(з кутовою сумою$(к-2)\pi$(по$Р(к)$), звідки ми можемо додати, щоб побачити, що$A_0{A}_1{A}_2\cdots A_{к}$має суму кута$((к+1)-2)\pi$. Однак це працює лише

• якщо трикутник$$AкA1A0«стирчить», а не в, і

Так що те, що зазвичай подається як «доказ», взагалі не працює.

Якщо ми хочемо довести загальний результат — для багатокутників усіх форм — ми маємо обійти це необґрунтоване припущення. Експеримент може переконати вас, що «завжди є якась вершина, яка стирчить і яку можна сміливо «відрізати»; але зовсім не зрозуміло, як довести цей факт (ми не знаємо простого доказу). Тому ми повинні знайти інший шлях.]

Розглянемо вершину$A_1$, і двох його сусідів$A_0$і$A_2$.

Уявіть собі кожну половину лінії, яка починається з$A_1$, і який вирушає у внутрішню частину багатокутника. Оскільки багатокутник скінченний, кожна така половина лінії визначає відрізок лінії$\underset{¯}{A_1Х}$, де X - наступна точка багатокутника, на яку потрапляє половина лінії (тобто X є однією з вершин$A_{м}$, або точка на одній зі сторін$\underset{}{}$AмAм+1¯).

Розглянемо локус всіх таких точок Х, як розгойдування половини лінії від$\underset{¯}{A_1{A}_0}$(вироблено) до$\underset{¯}{A_1{A}_2}$(Вироблено). Є дві можливості: або

(a) всі ці точки X належать одній стороні багатокутника; або

(б) вони цього не роблять.

(a) У першому випадку жодна з вершин або сторін багатокутника$A_0{A}_1{A}_2\cdots A_{к}$вторгнутися у внутрішню частину трикутника$$A0A1A2, так акорд$\underset{¯}{A_0{A}_2}$відокремлює (k + 1) -кутник$A_0{A}_1{A}_2\cdots A_{к}$в трикутник$$A0A1A2і k -кутник$A_0{A}_2{A}_3\cdots A_{к}$. Сума кута$A_0{A}_1{A}_2\cdots A_{к}$дорівнює сумі (i) суми кута трикутника$$A0A1A2і (ii) сума кута$A_0{A}_2{A}_3\cdots A_{к}$— які дорівнюють$\pi$і$(к-2)\pi$відповідно (по$Р(к)$). Отже, сума кута (k + 1) -кутника$A_0{A}_2{A}_3\cdots A_{к}$дорівнює$((к+1)-2)\pi$як потрібно.

(б) У другому випадку, як половина лінії$$A1Хобертається від$$A1A0до$$A1A2, точка X повинна в якийсь момент перемикатися з лежачого на одній стороні багатокутника на лежачи на іншій стороні; в той самий момент, коли X перемикає сторони,$Х=A_{м}$повинна бути вершиною багатокутника.

Через те, як була обрана точка X, акорд$\underset{¯}{A_1Х}=\underset{¯}{A_1{A}_{м}}$не відповідає жодній іншій точці (k + 1) -кутника$A_0{A}_1{A}_2\cdots A_{к}$, і так розбиває (k + 1) -кутник на m -кутник$A_1{A}_2{A}_3\cdots A_{м}$(з кутовою сумою$(м-2)\pi$від$Р(к)$) і а (k - м + 3) -кутник$$AмAм+1Aм+2⋯AкA0A1(з кутовою сумою$(к-м+1)\pi$від$Р(к)$). Отже, (k + 1) -кутник$A_0{A}_1{A}_2\cdots A_{к}$має суму кута$((к+1)-2)\pi$як потрібно.

Звідси$Р(к+1)$це правда.

$\therefore$ $Р(п)$вірно для всіх$п\ge 3$.

231. Нехай$Р(п)$бути заявою$$1$$$$+3+5+\cdots +(2п-1)={п}^2$$

• ЛГС$Р(1)=1$; RHS або$Р(1)=1^2$. Оскільки ці два рівні,$Р(1)$це правда.
• Припустимо, що$Р(к)$вірно для деяких конкретних (невизначений)$к\ge 1$; тобто ми знаємо, що для цього конкретного k,

  $$1+3+5+\cdots +(2к-1)={к}^2$$.

  Бажаємо довести, що$Р(к+1)$тоді має бути правдою.

  Зараз$Р(к+1)$це рівняння, тому ми починаємо з LHS$Р(к+1)$і спробуйте спростити його відповідним чином, щоб отримати RHS$Р(к+1)$:

  $\begin{array}{ccc}\text{ЛГС}\mathbf{Р}(к+1)\hfill & =\hfill & 1+3+5+...+\left(2\right(к+1)-1)\hfill \\ \hfill & =\hfill & (1+3+5+...+(2к-1\left)\right)+(2к+1).\hfill \end{array}$

  Якщо ми зараз використовуємо$Р(к)$, який ми припускаємо бути істинним, то перша дужка дорівнює k ², тому ця сума дорівнює:

  $\begin{array}{ccc}\hfill & =\hfill & {к}^2+(2к+1)\hfill \\ \hfill & =\hfill & {(к+1)}^2\hfill \\ \hfill & =\hfill & \text{RHS}\mathbf{Р}(к+1).\hfill \end{array}$

  Звідси$Р(к+1)$тримає.

Поєднання цих двох точок кулі показує, що»$Р(п)$тримає, для всіх$п\ge 1$».

232.

(а) Єдиний спосіб навчитися - це спроба і невдача; потім спроба знову і невдача трохи краще! Тому не здавайтеся занадто швидко. Природно намагатися співвідносити кожен термін з тим, що раніше. Потім ви можете помітити, що кожен термін трохи менше, ніж в 3 рази попередній термін.

(b) Примітка: Відношення повторення для${у}_{п}$передбачає два попередніх терміну. Отже, коли ми припускаємо, що$Р(к)$відомо, щоб бути правдою і спробувати довести$Р(к+1)$, відношення рецидивів для${у}_{к+1}$буде залучати${у}_{к}$і${у}_{к-1}$, так$Р(п)$потрібно сформулювати, щоб ми могли використовувати замкнуті вирази для обох цих термінів. З тієї ж причини індукційний доказ повинен починатися з показу того, що обидва$Р(0)$і$Р(1)$вірні.

Нехай$Р(п)$бути твердженням:

»${у}_{м}=2^{м}+3^{м}$для всіх м,$0\le м\le п$».

• ЛГС$Р(0)={у}_0=2$; RHS або$Р(0)=2^0+3^0=1+1$. Оскільки ці два рівні,$Р(0)$це правда.

  $Р(1)$поєднує$Р(0)$, і рівність${у}_1=5$і$2^1+3^1$; оскільки ці два рівні,$Р(1)$це правда.

• Припустимо, що$Р(к)$вірно для деяких конкретних (невизначений)$к\ge 1$; тобто ми знаємо, що для цього конкретного k,

  »${у}_{м}=2^{м}+3^{м}$для всіх м,$0\le м\le к$.»

  Бажаємо довести, що$Р(к+1)$тоді має бути правдою.

  Зараз$Р(к+1)$вимагає від нас довести, що

  »${у}_{м}=2^{м}+3^{м}$для всіх м,$0\le м\le к+1$.»

  Більшу частину цього гарантують$Р(к)$, який ми вважаємо правдою. Нам залишається перевірити, чи дотримується рівність${у}_{к+1}$. Ми знаємо, що

  $${у}_{к+1}=5{у}_{к}-6{у}_{к-1}.$$

  І ми можемо використовувати$Р(к)$), які ми передбачаємо бути правдою, зробити висновок, що:

  $\begin{array}{ccc}{у}_{к+1}\hfill & =\hfill & 5(2^{к}+3^{к})-6(2^{к-1}+3^{к-1})\hfill \\ \hfill & =\hfill & (10-6)2^{к-1}+(15-6)3^{к-1}\hfill \\ \hfill & =\hfill & 2^{к+1}+3^{к+1}.\hfill \end{array}$

  Звідси$Р(к+1)$тримає.

Поєднання цих двох точок кулі показує, що»$Р(п)$тримає, для всіх$п\ge 0$».

233. Нехай$Р(п)$бути твердженням:

»$F_{м}=\frac{{\alpha }^{м}-{\beta }^{м}}{\sqrt{5}}$для всіх м,$0\le м\le п$»,

де$\alpha =\frac{1+\sqrt{5}}{2}$і$\beta =\frac{1-\sqrt{5}}{2}$.

• ЛГС$Р(0)=F_0=0$; RHS або$Р(0)=\frac{1-1}{\sqrt{5}}=0$. Оскільки ці два рівні,$Р(0)$це правда.

  ЛГС$Р(1)=F_1=1$; RHS або$Р(1)=\frac{\alpha -\beta }{\sqrt{5}}=1$. Оскільки ці два рівні,$Р(1)$це правда.

• Припустимо, що$Р(к)$вірно для деяких конкретних (невизначений)$к\ge 1$; тобто ми знаємо, що для цього конкретного k,

  »$F_{м}=\frac{{\alpha }^{м}-{\beta }^{м}}{\sqrt{5}}$для всіх м,$0\le м\le к$.»

  Бажаємо довести, що$Р(к+1)$тоді має бути правдою.

  Зараз$Р(к+1)$вимагає від нас довести, що

  »$F_{м}=\frac{{\alpha }^{м}-{\beta }^{м}}{\sqrt{5}}$для всіх м,$0\le м\le к+1$.»

  Більшу частину цього гарантують$Р(к)$, який ми вважаємо правдою. Залишилося перевірити це на$F_{к+1}$. Ми знаємо, що

  $$F_{к+1}=F_{к}+F_{к-1}.$$

  І ми можемо використовувати$Р(к)$, який ми вважаємо вірним, щоб зробити висновок, що:

  $\begin{array}{ccc}{F}_{к+1}\hfill & =\hfill & \genfrac{}{}{0.1ex}{}{{\alpha }^{к}-{\beta }^{к}}{\sqrt{5}}+\genfrac{}{}{0.1ex}{}{{\alpha }^{к-1}-{\beta }^{к-1}}{\sqrt{5}}\hfill \\ \hfill & =\hfill & \genfrac{}{}{0.1ex}{}{{\alpha }^{к}+{\alpha }^{к-1}}{\sqrt{5}}-\genfrac{}{}{0.1ex}{}{{\beta }^{к}+{\beta }^{к-1}}{\sqrt{5}}\hfill \\ \hfill & =\hfill & \genfrac{}{}{0.1ex}{}{{\alpha }^{к+1}-{\beta }^{к+1}}{\sqrt{5}}\hfill \end{array}$

  (з$\alpha$і$\beta$є корінням рівняння${х}^2-х-1=0$) Звідси$Р(к+1)$тримає.

Поєднання цих двох точок кулі показує, що»$Р(п)$тримає, для всіх$п\ge 1$».

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

$$(р,q)=р(1,0)+q(0,1)).$$

Як тільки ми це дізнаємося, залишається:

• знайти два спеціальні рішення (наприклад вектори (1, 0) та (0, 1) у площині), які ми робимо тут, шукаючи послідовності форми»$1,х,{х}^2,{х}^3,...$» які задовольняють повторення, що означає, що$1+х={х}^2$, так$х=\alpha$, або$х=\beta$;
• потім вибрати лінійну комбінацію$F_{м}=$рαм+qβмз цих двох силових рішень дати правильні перші два терміни:$0=F_0=р+q$,$1=F_1=р\alpha +q\beta$, так$р=\frac{1}{\sqrt{5}}$,$q=-\frac{1}{\sqrt{5}}$.

234. Нехай$Р(п)$бути твердженням:

»$5^{2п+1}·2^{п+2}+3^{п+2}·2^{2п+1}$ділиться на$19$».

• $Р(0)$це твердження:»$5\times 4+9\times 2$ділиться на 19», що вірно.
• Тепер припустимо, що ми знаємо, що$Р(к)$вірно для деяких$к\ge 0$. Ми повинні показати, що$Р(к+1)$тоді також вірно.
• Щоб довести, що$Р(к+1)$правда, ми повинні показати, що

  »$5^{2к+3}·2^{к+3}+3^{к+3}·2^{2к+3}$ділиться на$19$».

  $\begin{array}{ccc}{5}^{2к+3}\cdot 2^{к+3}+3^{к+3}\cdot 2^{2к+3}\hfill & =\hfill & 5^2\cdot 2(5^{2к+1}\cdot 2^{к+2}+3^{к+2}\cdot 2^{2к+1})\hfill \\ \hfill & \hfill & -5^2\cdot 2\cdot 3^{к+2}\cdot 2^{2к+1}+3^{к+3}\cdot 2^{2к+3}\hfill \\ \hfill & =\hfill & 5^2\cdot 2\cdot (5^{2к+1}\cdot 2^{к+2}+3^{к+2}\cdot 2^{2к+1})\hfill \\ \hfill & \hfill & -(5^2-3\cdot 2)3^{к+2}\cdot 2^{2к+2}.\hfill \end{array}$

  Дужка в першому семестрі на RHS ділиться на 19 (на$Р(к)$), а дужка у другому члені дорівнює 19. Отже, обидва терміни на RHS діляться на 19, тому RHS ділиться на 19. Тому LHS також ділиться на 19, так$Р(к+1)$це правда.

$\cdot$ $Р(п)$вірно для всіх$п\ge 0$.

235.

Примітка: Докази ідентичності, такі як у Задачі 235., які наведені у багатьох вступних текстах, ігнорують уроки попередніх двох проблем. Зокрема,

• вони часто не в змозі розрізнити

— єдина заява$Р(п)$для конкретного n, і

— «кількісний» результат, який підлягає доведенню («для всіх$п\ge 1$»),

і

• вони йдуть у «неправильному» напрямку (наприклад, починаючи з особистості$Р(п)$і «додавання однакового до обох сторін»).

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

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

(а) Нехай$Р(п)$бути твердженням:

»$1+2+3+\cdots +п=\frac{п(п+1)}{2}$».

• ЛГС$Р(1)=1$; RHS або$Р(1)=\frac{1·(1+1)}{2}=1$. Оскільки ці два рівні,$Р(1)$це правда.
• Припустимо, що$Р(к)$вірно для деяких конкретних (невизначений)$к\ge 1$; тобто ми знаємо, що для цього конкретного k,

  »$1+2+3+\cdots +к=\frac{к(к+1)}{2}$».

  Бажаємо довести, що$Р(к+1)$тоді має бути правдою.

  Зараз$Р(к+1)$це рівняння, тому ми починаємо з LHS$Р(к+1)$і спробуйте спростити його відповідним чином, щоб отримати RHS$Р(к+1)$):

  $\begin{array}{ccc}\text{ЛГС}\mathbf{Р}(к+1)\hfill & =\hfill & 1+2+3+\cdots +к+(к+1)\hfill \\ \hfill & =\hfill & (1+2+3+\cdots +к)+(к+1).\hfill \end{array}$

  Якщо ми зараз використовуємо$Р(к)$, які ми припускаємо бути правдою, тоді перша дужка дорівнює$\frac{к(к+1)}{2}$, Таким чином, повна сума дорівнює:

  $\begin{array}{ccc}\hfill & =\hfill & \genfrac{}{}{0.1ex}{}{к(к+1)}{2}+(к+1)\hfill \\ \hfill & =\hfill & \genfrac{}{}{0.1ex}{}{(к+1)(к+2)}{2}\hfill \\ \hfill & =\hfill & \text{RHS}\mathbf{Р}(к+1).\hfill \end{array}$

  Звідси$Р(к+1)$тримає.

  Якщо ми об'єднаємо ці дві точки кулі, то ми довели, що»$Р(п)$тримає для всіх$п\ge 1$».

(б) Нехай$Р(п)$бути твердженням:

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

• ЛГС$Р(1)=\frac{1}{1·2}=\frac{1}{2}$; RHS або$Р(1)=1-\frac{1}{2}=\frac{1}{2}$. Оскільки ці два рівні,$Р(1)$це правда.
• Припустимо, що$Р(к)$вірно для деяких конкретних (невизначений)$к\ge 1$; тобто ми знаємо, що для цього конкретного k,

  »$\frac{1}{1·2}+\frac{1}{2·3}+\frac{1}{3·4}+\cdots +\frac{1}{к·(к+1)}=1-\frac{1}{к+1}$».

  Бажаємо довести, що$Р(к+1)$тоді має бути правдою.

  Зараз$Р(к+1)$це рівняння, тому ми починаємо з LHS$Р(к+1)$і спробуйте спростити його відповідним чином, щоб отримати RHS$Р(к+1)$:

  $\begin{array}{ccc}\text{ЛГС}\mathbf{Р}(к+1)\hfill & =\hfill & \genfrac{}{}{0.1ex}{}{1}{1\cdot 2}+\genfrac{}{}{0.1ex}{}{1}{2\cdot 3}+\genfrac{}{}{0.1ex}{}{1}{3\cdot 4}+\cdots +\genfrac{}{}{0.1ex}{}{1}{(к+1)(к+2)}\hfill \\ \hfill & =\hfill & [\genfrac{}{}{0.1ex}{}{1}{1\cdot 2}+\genfrac{}{}{0.1ex}{}{1}{2\cdot 3}+\genfrac{}{}{0.1ex}{}{1}{3\cdot 4}+\genfrac{}{}{0.1ex}{}{1}{к(к+1)}]\hfill \\ \hfill & \hfill & +\genfrac{}{}{0.1ex}{}{1}{(к+1)(к+2)}.\hfill \end{array}$

  Якщо ми зараз використовуємо$Р(к)$, який ми вважаємо істинним, тоді перша дужка дорівнює$1-\frac{1}{к+1}$, Таким чином, повна сума дорівнює:

  $\begin{array}{ccc}\hfill & =\hfill & [1-\genfrac{}{}{0.1ex}{}{1}{к+1}]+\genfrac{}{}{0.1ex}{}{1}{(к+1)(к+2)}\hfill \\ \hfill & =\hfill & 1-[\genfrac{}{}{0.1ex}{}{1}{к+1}-\genfrac{}{}{0.1ex}{}{1}{(к+1)(к+2)}]\hfill \\ \hfill & =\hfill & 1-\genfrac{}{}{0.1ex}{}{1}{к+2}\hfill \\ \hfill & =\hfill & \text{RHS}\mathbf{Р}(к+1).\hfill \end{array}$

  Звідси$Р(к+1)$тримає.

  Якщо ми об'єднаємо ці дві точки кулі, ми довели, що»$Р(п)$тримає для всіх$п\ge 1$».

(c) Примітка: Якщо$q=1$, То LHS дорівнює n, але RHS не має сенсу. Отже, ми припускаємо$q\ne 1$.

Нехай$Р(п)$бути твердженням:

»$1+q+q^2+q^3+\cdots +q^{п-1}=\frac{1}{1-q}-\frac{q^{п}}{1-q}$».

• ЛГС$Р(1)=1$; RHS або$Р(1)=\frac{1}{1-q}-\frac{q}{1-q}=1$. Оскільки ці два рівні,$Р(1)$це правда.
• Припустимо, що$Р(к)$вірно для деяких конкретних (невизначений)$к\ge 1$; тобто ми знаємо, що для цього конкретного k,

  »$1+q+q^2+q^3+\cdots +q^{к-1}=\frac{1}{1-q}-\frac{q^{к}}{1-q}$».

  Бажаємо довести, що$Р(к+1)$тоді має бути правдою.

Зараз$Р(к+1)$це рівняння, тому ми починаємо з LHS$Р(к+1)$і спробуйте спростити його відповідним чином, щоб отримати RHS$Р(к+1)$:

$\begin{array}{ccc}\text{ЛГС}\mathbf{Р}(к+1)\hfill & =\hfill & 1+q+q^2+q^3+\cdots +q^{к}\hfill \\ \hfill & =\hfill & (1+q+q^2+q^3+\cdots +q^{к-1})+q^{к}.\hfill \end{array}$

Якщо ми зараз використовуємо$Р(к)$, який ми вважаємо істинним, тоді перша дужка дорівнює

$$\frac{1}{1-q}-\frac{q^{к}}{1-q}$$

тому повна сума дорівнює:

$\begin{array}{ccc}\hfill & =\hfill & \genfrac{}{}{0.1ex}{}{1}{1-q}-[\genfrac{}{}{0.1ex}{}{q^{к}}{1-q}-q^{к}]\hfill \\ \hfill & =\hfill & \genfrac{}{}{0.1ex}{}{1}{1-q}-\genfrac{}{}{0.1ex}{}{q^{к+1}}{1-q}\hfill \\ \hfill & =\hfill & \text{RHS}\mathbf{Р}(к+1).\hfill \end{array}$

Звідси$Р(к+1)$тримає.

Якщо ми об'єднаємо ці дві точки кулі, ми довели, що»$Р(п)$тримає для всіх$п\ge 1$».

(d) Примітка: Заява, що підлягає доведенню, починається з терміну, що включає «0!». визначення

$$п!=1\times 2\times 3\times \cdots \times п$$

не відразу говорить нам, як інтерпретувати»$0!$». Правильне тлумачення випливає з того, що кілька різних думок все вказують в одному напрямку.

(i) Коли$п>0$, щоб потім отримати від$п!$до$(п+1)!$множимо на (n + 1). Якщо ми продовжимо це до$п=0$, потім «отримати від$0!$до$1!$, ми повинні помножити на 1» - що говорить про те, що$0!=1$.

(ii) Коли$п>0$,$п!$підраховує кількість перестановок n символів або кількість різних лінійних порядків n об'єктів (тобто скільки різних способів їх можна розташувати в рядку). Якщо ми продовжимо це до$п=0$, Ми бачимо, що існує лише один спосіб розташувати 0 об'єктів (а саме, сидіти щільно і нічого не робити).

(iii) Визначення$п!$як продукт говорить про те, що$0!$передбачає «продукт без термінів» взагалі. Тепер, коли ми «не додаємо жодних термінів разом», має сенс інтерпретувати результат як «= 0» (можливо, тому, що якби ця «сума без термінів» була додана до якоїсь іншої суми, це не мало б різниці). У тому ж дусі продукт без термінів слід приймати як «= 1» (оскільки якби цей порожній продукт був включений в кінці якогось іншого продукту, це не мало б різниці для результату).

Нехай$Р(п)$бути твердженням:

»$0·0!+1·1!+2·2!+\cdots +(п-1)·(п-1)!=п!-1$».

• LHS або$Р(1)=0·0!=0$; RHS або$Р(1)=1!-1=0$. Оскільки ці два рівні,$Р(1)$це правда.

• Припустимо, що$Р(к)$вірно для деяких конкретних (невизначений)$к\ge 1$; тобто ми знаємо, що для цього конкретного k,

»$0·0!+1·1!+2·2!+\cdots +(к-1)·(к-1)!=к!-1$».

Бажаємо довести, що$Р(к+1)$тоді має бути правдою.

Зараз$Р(к+1)$це рівняння, тому ми починаємо з LHS$Р(к+1)$і спробуйте спростити його відповідним чином, щоб отримати RHS$Р(к+1)$):

$\begin{array}{ccc}\text{ЛГС}\mathbf{Р}(к+1)\hfill & =\hfill & 0\cdot 0!+1\cdot 1!+2\cdot 2!+\cdots +к\cdot к!\hfill \\ \hfill & =\hfill & [0\cdot 0!+1\cdot 1!+2\cdot 2!+\cdots +(к-1)\cdot (к-1)!]+к.к!.\hfill \end{array}$

Якщо ми зараз використовуємо$Р(к)$, який ми вважаємо істинним, тоді перша дужка дорівнює$к!-1$, Таким чином, повна сума дорівнює:$\begin{array}{ccc}\hfill & =\hfill & (к!-1)+к\cdot к!\hfill \\ \hfill & =\hfill & (к+1)\cdot к!-1\hfill \\ \hfill & =\hfill & (к+1)!-1=\text{RHS}\mathbf{Р}(к+1).\hfill \end{array}$Звідси$Р(к+1)$тримає.

Якщо ми об'єднаємо ці дві точки кулі, ми довели, що»$Р(п)$тримає для всіх$п\ge 1$».

(е) Нехай$Р(п)$бути твердженням:

»${(}^{}$cosθ+ягріхθ)п=cosпθ+ягріхпθ»

• LHS або$Р(1)={(}^{}$cosθ+ягріхθ)1; RHS або$Р(1)=$cosθ+ягріхθ. Оскільки ці два рівні,$Р(1)$це правда.

• Припустимо, що$Р(к)$вірно для деяких конкретних (невизначений)$к\ge 1$; тобто ми знаємо, що для цього конкретного k,

»${(}^{}$cosθ+ягріхθ) к =cosкθ+ягріхкθ».

Бажаємо довести, що$Р(к+1)$тоді має бути правдою.

Зараз$Р(к+1)$це рівняння, тому ми починаємо з LHS$Р(к+1)$і спробуйте спростити його відповідним чином, щоб отримати RHS$Р(к+1)$:$\begin{array}{ccc}\text{ЛГС}\mathbf{Р}(к+1)\hfill & =\hfill & {(\cos \theta +я\mathrm{гріх}\theta )}^{к+1}\hfill \\ \hfill & =\hfill & {(\cos \theta +я\mathrm{гріх}\theta )}^{к}(\cos \theta +я\mathrm{гріх}\theta ).\hfill \end{array}$Якщо ми зараз використовуємо$Р(к)$, який ми вважаємо істинним, тоді перша дужка дорівнює$($cosкθ+ягріхкθ), Таким чином, повний вираз дорівнює:

$\begin{array}{cc}=\hfill & (\cos к\theta +я\mathrm{гріх}к\theta )(\cos \theta +я\mathrm{гріх}\theta )\hfill \\ =\hfill & [\cos к\theta \cdot \cos \theta -\mathrm{гріх}к\theta \cdot \mathrm{гріх}\theta ]+я[\cos к\theta \cdot \mathrm{гріх}\theta +\mathrm{гріх}к\theta \cdot \cos \theta ]\hfill \\ =\hfill & \cos (к+1)\theta +я\mathrm{гріх}(к+1)\theta =\text{RHS}\mathbf{Р}(к+1).\hfill \end{array}$Звідси$Р(к+1)$тримає.

Якщо ми об'єднаємо ці дві точки кулі, ми довели, що»$Р(п)$тримає для всіх$п\ge 1$».

236. Нехай$Р(п)$бути твердженням:

»${(1+2+3+\cdots +п)}^2=1^3+2^3+3^3+\cdots +{п}^3$».

• LHS або$Р(1)=1^2$; RHS або$Р(1)=1^3$. Оскільки ці два рівні,$Р(1)$це правда.

• Припустимо, що$Р(к)$вірно для деяких конкретних (невизначений)$к\ge 1$; тобто ми знаємо, що для цього конкретного k,

»${(1+2+3+\cdots +к)}^2=1^3+2^3+3^3+\cdots +{к}^3$».

Бажаємо довести, що$Р(к+1)$тоді має бути правдою.

Зараз$Р(к+1)$це рівняння, тому ми починаємо з однієї сторони$Р(к+1)$і спробуйте спростити його відповідним чином, щоб отримати іншу сторону$Р(к+1)$. У цьому випадку RHS$Р(к+1)$є найбільш перспективною відправною точкою (тому що ми знаємо формулу${}^{}$кготрикутне число, і так видно, як його спростити):$\begin{array}{ccc}\text{RHS}\mathbf{Р}(к+1)\hfill & =\hfill & 1^3+2^3+3^3+\cdots +{к}^3+{(к+1)}^3\hfill \\ \hfill & =\hfill & [1^3+2^3+3^3+\cdots +{к}^3]+{(к+1)}^3.\hfill \end{array}$

Якщо ми зараз використовуємо$Р(к)$, який ми вважаємо істинним, тоді перша дужка дорівнює

$${(1+2+3+\cdots +к)}^2,$$

Таким чином, повний RHS:$\begin{array}{cc}=\hfill & {(1+2+3+\cdots +к)}^2+{(к+1)}^3\hfill \\ =\hfill & {\left[\genfrac{}{}{0.1ex}{}{к(к+1)}{2}\right]}^2+{(к+1)}^3\hfill \\ =\hfill & \genfrac{}{}{0.1ex}{}{1}{4}{(к+1)}^2[{к}^2+4к+4]\hfill \\ =\hfill & {\left[\genfrac{}{}{0.1ex}{}{(к+1)(к+2)}{2}\right]}^2\hfill \\ =\hfill & {(1+2+3+\cdots +(к+1\left)\right)}^2\hfill \\ =\hfill & \text{ЛГС}\mathbf{Р}(к+1).\hfill \end{array}$Звідси$Р(к+1)$тримає.

Якщо ми об'єднаємо ці дві точки кулі, ми довели, що»$Р(п)$тримає для всіх$п\ge 1$».

Примітка: Дещо інший спосіб організації доказу іноді може бути корисним. Позначимо дві сторони рівняння в твердженні$Р(п)$від$f(п)$і$г(п)$відповідно. Тоді

•$f(1)=1^2=1^3=г(1)$; і

• проста алгебра дозволяє перевірити, що для кожного$к\ge 1$,

$$f(к+1)-f(к)={(к+1)}^3=г(к+1)-г(к).$$

Потім випливає (шляхом індукції), що$f(п)=г(п)$для всіх$п\ge 1$.

237.

(а)${Т}_1=1$,${Т}_1+{Т}_2=1+3=4$,${Т}_1+{Т}_2+{Т}_3=1+3+6=10$. Вони можуть бути не дуже сугестивними. Але

$${Т}_1+{Т}_2+{Т}_3+{Т}_4=20=5\times 4,$$ $${Т}_1+{Т}_2+{Т}_3+{Т}_4+{Т}_5=35=5\times 7,$$

і

$${Т}_1+{Т}_2+{Т}_3+{Т}_4+{Т}_5+{Т}_6=56=7\times 8$$

може врешті-решт змусити здогадатися, що

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

Примітка 1: Це, безумовно, буде легше здогадатися, якщо ви пам'ятаєте, що ви знайшли в задачі 17.

Примітка 2: Є ще один спосіб допомогти в такому ворожінні. Припустимо, ви помітили, що

— додавання значень для$к=1$до$к=п$полінома ступеня 0 (наприклад$р(х)=1$) дає відповідь, яка є «многочленом ступеня 1»,

$$1+1+\cdots +1=п,$$

і

— додавання значень для$к=1$до$к=п$полінома 1 ступеня (наприклад$р(х)=х$) дає відповідь, що є «многочленом 2 ступеня»,

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

Тоді ви можете здогадатися, що сума

$${Т}_1+{Т}_2+{Т}_3+\cdots +{Т}_{п}$$

дасть відповідь, що є поліномом ступеня 3 в n. Припустимо, що

$${Т}_1+{Т}_2+{Т}_3+\cdots +{Т}_{п}=$$Aп3+Бп2+Cп+D.

Потім ми можемо використовувати малі значення n, щоб встановити рівняння, які повинні бути задоволені A, B, C, D і вирішити їх, щоб знайти A, B, C, D:

— коли$п=0$, отримуємо$D=0$;

— коли$п=1$, отримуємо$A+Б+C=1$;

— коли$п=2$, отримуємо$8A+4Б+2C=4$;

— коли$п=3$, отримуємо$$27A+9Б+3C=10.

Цей метод передбачає, що ми знаємо, що відповідь є поліномом і що ми знаємо його ступінь: він називається «методом невизначений коефіцієнтів».

Існують різні способи вдосконалення основного методу (наприклад, написання полінома$$Aп3+Бп2+Cп+Dу формі

$$Рп(п-1)(п-2)+Qп(п-1)+Рп+S,$$

який адаптує його до значень$п=0,1,2,3$що один має намір замінити).

(б) Нехай$Р(п)$бути твердженням:

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

• LHS або$Р(1)={Т}_1=1$; RHS або$Р(1)=\frac{1\times 2\times 3}{6}=1$. Оскільки ці два рівні,$Р(1)$це правда.

• Припустимо, що$Р(к)$вірно для деяких конкретних (невизначений)$к\ge 1$; тобто ми знаємо, що для цього конкретного k,

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

Бажаємо довести, що$Р(к+1)$тоді має бути правдою.

Зараз$Р(к+1)$це рівняння, тому ми починаємо з LHS$Р(к+1)$і спробуйте спростити його відповідним чином, щоб отримати RHS$Р(к+1)$:$\begin{array}{ccc}\text{ЛГС}\mathbf{Р}(к+1)\hfill & =\hfill & {Т}_1+{Т}_2+{Т}_3+\cdots +{Т}_{к}+{Т}_{к+1}\hfill \\ \hfill & =\hfill & [{Т}_1+{Т}_2+{Т}_3+\cdots +{Т}_{к}]+{Т}_{к+1}.\hfill \end{array}$Якщо ми зараз використовуємо$Р(к)$, який ми вважаємо істинним, тоді перша дужка дорівнює

$$\frac{к(к+1)(к+2)}{6}.$$

тому повна сума дорівнює:$\begin{array}{cc}=\hfill & \genfrac{}{}{0.1ex}{}{к(к+1)(к+2)}{6}+\genfrac{}{}{0.1ex}{}{(к+1)(к+2)}{2}\hfill \\ =\hfill & \genfrac{}{}{0.1ex}{}{(к+1)(к+2)(к+3)}{6}\hfill \\ =\hfill & \text{RHS}\mathbf{Р}(к+1).\hfill \end{array}$

Звідси$Р(к+1)$тримає.

Якщо ми об'єднаємо ці дві точки кулі, ми довели, що»$Р(п)$тримає для всіх$п\ge 1$».

Примітка: Трикутні числа${Т}_1,{Т}_2,{Т}_3,...,{Т}_{к},...{Т}_{п}$також дорівнюють біноміальним коефіцієнтам$к+$1cчoosе2. А сума цих біноміальних коефіцієнтів - ще один біноміальний коефіцієнт.$п+$2cчoosе3, Таким чином, результат в задачі 237. може бути записаний як:

$$\left(\begin{array}{c}2\\ 2\end{array}\right)+\left(\begin{array}{c}3\\ 2\end{array}\right)+\left(\begin{array}{c}4\\ 2\end{array}\right)+\cdots +\left(\begin{array}{c}п+1\\ 2\end{array}\right)=\left(\begin{array}{c}п+2\\ 3\end{array}\right).$$

Ви можете інтерпретувати задачу 237. мовою біноміальних коефіцієнтів і довести це багаторазовим використанням базового відношення трикутника Паскаля (Паскаль (1623—1662)):

$$\left(\begin{array}{c}к\\ р\end{array}\right)+\left(\begin{array}{c}к\\ р+1\end{array}\right)=\left(\begin{array}{c}к+1\\ р+1\end{array}\right).$$

Почніть з рерайтингу

$$\left(\begin{array}{c}п+2\\ 3\end{array}\right)=\left(\begin{array}{c}п+1\\ 2\end{array}\right)+\left(\begin{array}{c}п+1\\ 3\end{array}\right).$$

238.

(a) Ми знаємо з проблеми 237. (б) що

$$1\cdot 2+2\cdot 3+3\cdot 4+\cdots +п(п+1)=\frac{п(п+1)(п+2)}{3}.$$

Також

$\begin{array}{ccc}1\cdot 2+2\cdot 3+3\cdot 4+\cdots +п(п+1)\hfill & =\hfill & 1\cdot (1+1)+2\cdot (2+1)+3\cdot (3+1)\hfill \\ \hfill & \hfill & +\cdots +п\cdot (п+1)\hfill \\ \hfill & =\hfill & (1^2+1)+(2^2+2)+(3^2+3)\hfill \\ \hfill & \hfill & +\cdots +({п}^2+п)\hfill \\ \hfill & =\hfill & (1^2+2^2+3^2+\cdots +{п}^2)\hfill \\ \hfill & \hfill & +(1+2+3+\cdots +п).\hfill \end{array}$

Тому

$\begin{array}{ccc}{1}^2+2^2+3^2+\cdots +{п}^2\hfill & =\hfill & \genfrac{}{}{0.1ex}{}{п(п+1)(п+2)}{3}-\genfrac{}{}{0.1ex}{}{п(п+1)}{2}\hfill \\ \hfill & =\hfill & \genfrac{}{}{0.1ex}{}{п(п+1)(2п+1)}{6}.\hfill \end{array}$

(б) Вгадайте:

$$1\cdot 2\cdot 3+2\cdot 3\cdot 4+3\cdot 4\cdot 5+\cdots +п(п+1)(п+2)=\frac{п(п+1)(п+2)(п+3)}{4}.$$

Доказ за допомогою індукції є цілком рутинним, і залишається для читача.

$\begin{array}{ccc}1\cdot 2\cdot 3+2\cdot 3\cdot 4+\cdots +п(п+1)(п+2)\hfill & =\hfill & 1\cdot (1+1)(1+2)+2\cdot (2+1)(2+2)\hfill \\ \hfill & \hfill & +\cdots +п\cdot (п+1)(п+2)\hfill \\ \hfill & =\hfill & (1^3+3\cdot 1^2+2\cdot 1)\hfill \\ \hfill & \hfill & +(2^3+3\cdot 2^2+2\cdot 2)\hfill \\ \hfill & \hfill & +\cdots +({п}^3+3{п}^2+2п)\hfill \\ \hfill & =\hfill & (1^3+2^3+\cdots +{п}^3)\hfill \\ \hfill & \hfill & +3(1^2+2^2+\cdots +{п}^2)\hfill \\ \hfill & \hfill & +2(1+2+\cdots +п).\hfill \end{array}$

Тому

$\begin{array}{ccc}{1}^3+2^3+3^3+\cdots +{п}^3\hfill & =\hfill & \genfrac{}{}{0.1ex}{}{п(п+1)(п+2)(п+3)}{4}\hfill \\ \hfill & \hfill & -3\left[\genfrac{}{}{0.1ex}{}{п(п+1)(2п+1)}{6}\right]\hfill \\ \hfill & \hfill & -п(п+1)\hfill \\ \hfill & =\hfill & {\left[\genfrac{}{}{0.1ex}{}{п(п+1)}{2}\right]}^2.\hfill \end{array}$

239.

(а) Нехай$f(х)$бути будь-яким таким многочленом. Якщо$f(a_{к})=0$, то ми знаємо (за теоремою про залишок), що$f(х)$має$(х-a_{к})$як фактор. Так як$a_{к}$всі різні, і$f(a_{к})=0$для кожного k,$0\le к\le п-1$, у нас є

$$f(х)=(х-a_0)(х-a_1)(х-a_2)\cdots (х-a_{п-1})\cdot г(х)$$

для деякого многочлена$г(х)$. А оскільки нам кажуть, що$f(х)$має ступінь n,$г(х)$має ступінь 0, тому є константою. Звідси кожен такий многочлен ступеня n має вигляд:

$$C\cdot (х-a_0)(х-a_1)(х-a_2)\cdots (х-a_{п-1}).$$

Так як$f(a_{п})=б$, ми можемо замінити, щоб знайти C:

$$C=\frac{б}{(a_{п}-a_0)(a_{п}-a_1)(a_{п}-a_2)\cdots (a_{п}-a_{п-1})}.$$

(б) Нехай$Р(п)$бути твердженням:

«З урахуванням будь-яких двох маркованих наборів$п+1$дійсні числа$a_0,a_1,a_2,...,a_{п}$, і${б}_0,{б}_1,{б}_2,...,{б}_{п}$, де$a_{я}$всі різні (але${б}_{я}$не потрібно), існує многочлен$f_{п}$ступеня n, такі, що$f_{п}(a_0)={б}_0$,$f_{п}(a_1)={б}_1$,$f_{п}(a_2)={б}_2$,...,$f_{п}(a_{п})={б}_{п}$.»

• Коли$п=0$, ми можемо вибрати$f_0(х)={б}_0$бути постійним многочленом. Звідси$Р(0)$це правда.

• Припустимо, що$Р(к)$вірно для деяких конкретних (невизначений)$к\ge 0$; тобто ми знаємо, що для цього конкретного k:

«З урахуванням будь-яких двох маркованих наборів$к+1$дійсні числа$a_0,a_1,a_2,...,a_{к}$, і${б}_0,{б}_1,{б}_2,...,{б}_{к}$, де$a_{я}$всі різні (але${б}_{я}$не потрібно), існує многочлен$f_{к}$ступеня k, такі, що$f_{к}(a_0)={б}_0$,$f_{к}(a_1)={б}_1$,$f_{к}(a_2)={б}_2,...,f_{к}(a_{к})={б}_{к}$.»

Бажаємо довести, що$Р(к+1)$тоді має бути правдою.

Зараз$Р(к+1)$це твердження:

«З урахуванням будь-яких двох маркованих наборів$(к+1)+1$дійсні числа$a_0,a_1,...,a_{к+1}$, і${б}_0,{б}_1,{б}_2,...,{б}_{к+1}$, де$a_{я}$всі різні (але${б}_{я}$не потрібно), існує многочлен$f_{к+1}$ступеня$к+1$, такий, що$f_{к+1}(a_0)={б}_0$,$f_{к+1}(a_1)={б}_1$,$f_{к+1}(a_2)={б}_2$,...,$f_{к+1}(a_{к+1})={б}_{к+1}$.»

Отже, щоб довести, що$Р(к+1)$тримає, ми повинні почати з розгляду

будь-які два позначені набори$(к+1)+1$дійсні числа$$a_0,a_1,a_2,...,a_{к+1},\text{і}{б}_0,{б}_1,{б}_2,...,{б}_{к+1},$$де$a_{я}$всі різні (але${б}_{я}$не потрібно).

Потім ми повинні якось побудувати поліноміальну функцію$f_{к+1}$ступеня$к+1$з необхідним майном.

Тому що ми припускаємо, що$Р(к)$як відомо, правда, ми можемо зосередитися на першому$к+1$числа в кожному з двох списків —$a_0,a_1,a_2,...,a_{к}$, і${б}_0,{б}_1,{б}_2,...,{б}_{к}$— і тоді ми можемо бути впевнені, що існує многочлен$f_{к}$ступеня k такий, що

$$f_{к}(a_0)={б}_0,f_{к}(a_1)={б}_1,f_{к}(a_2)={б}_2,...,f_{к}(a_{к})={б}_{к}.$$

Наступний крок трохи непрямий: використовуємо многочлен$f_{к+1}$який ми все ще намагаємося побудувати, і зосередитися на многочлені

$$f(х)=f_{к+1}(х)-f_{к}(х)$$

задовольняючи

$$f(a_0)=f(a_1)=...=f(a_{к})=0,f(a_{к+1})={б}_{к+1}-f_{к}(a_{к+1})=б(\text{сказати}).$$

Частина (а) гарантує існування такого многочлена$f(х)$ступеня$к+1$і розповідає нам, що саме ця поліноміальна функція$f(х)$дорівнює. Звідси ми можемо побудувати потрібний многочлен$f_{к+1}(х)$) встановивши його рівним$f(х)+f_{к}(х)$, що доводить, що$Р(к+1)$це правда.

Якщо ми об'єднаємо ці дві точки кулі, ми довели, що»$Р(п)$тримає для всіх$п\ge 1$».

240.

(a) 5 центів не можна зробити;$6=3+3$;$7=3+4$;$8=4+4$;$9=3+3+3$; і т.д.

Вгадайте: Кожну суму> N = 5 можна оплатити безпосередньо (без отримання змін).

(б) Нехай$Р(п)$бути твердженням:

«n центів можна оплатити безпосередньо (без зміни) за допомогою 3-х центових і 4-центових монет».

—$Р(6)$це твердження: «6 центів можна заплатити безпосередньо». І$6=3+3$, так$Р(6)$це правда.

— Тепер припустимо, що ми знаємо$Р(к)$вірно для деяких$к\ge 6$. Ми повинні показати, що$Р(к+1)$тоді має бути правдою.

Довести$Р(к+1)$розглядаємо заяву$Р(к+1)$:

»$к+1$центи можуть бути сплачені безпосередньо».

Ми знаємо, що$Р(к)$це правда, тому ми знаємо, що «k центів можна заплатити безпосередньо».

— Якщо прямий метод оплати k центів передбачає принаймні одну монету 3 центів, то ми можемо замінити одну монету 3 цента монета 4 центів, щоб виробити спосіб оплати$к+1$центів.

Отже, нам потрібно лише турбуватися про ситуацію, в якій єдиний спосіб заплатити k центів безпосередньо не передбачає жодних монет 3 центів взагалі - тобто оплата k центів використовує лише монети 4 центів. Але тоді повинно бути не менше двох монет 4 центів (так як$к\ge 6$), і ми можемо замінити дві монети 4 центів трьома монетами 3 центів, щоб виробляти спосіб оплати$к+1$центів безпосередньо.

Звідси

•$Р(6)$вірно; і

• коли завгодно$Р(к)$вірно для деяких$к\ge 6$, ми знаємо, що$Р(к+1)$також вірно.

$\therefore$ $Р(п)$вірно для всіх$п\ge 6$.

241.

(а)$z^2-z+1=0$, так$z=\frac{1\pm \sqrt{-3}}{2}$(Це два примітивних шостого кореня єдності).

$\therefore$ $z^2=\frac{-1\pm \sqrt{-3}}{2}$(два примітивних куба зуби єдності), і

$$z^2+$$1z2=−1.

(б)$z^2-2z+1=0$, так$z=1$(Повторний корінь).$\therefore$ $z^2=1$і$z^2+\frac{}{}$1z2=2.

(c) (г)$z^2-3z+1=0$, так$z=\frac{3\pm \sqrt{5}}{2}$.

Як тільки почнеться обчислення z ² і$\frac{}{}$1z2, стає зрозуміло, що пора п-а-у-с-е і думати.

$${\left(z+\frac{1}{z}\right)}^2=(z^2+$$1z2)+2,

так всякий раз$z+\frac{1}{z}=к$є цілим числом,

$$z^2+{\left(\frac{1}{z}\right)}^2={к}^2-2$$

також є цілим числом.

(е) Нехай$Р(п)$бути твердженням:

«якщо z має властивість, яка$z+\frac{1}{z}$є цілим числом, потім$z^{м}+\frac{}{}$1zмтакож є цілим числом для всіх m,$0\le м\le п$».

•$Р(0)$і$Р(1)$явно обидва вірні; і$Р(2)$було доведено в частині (d) вище.

• Припустимо, що$Р(к)$вірно для деяких конкретних (невизначений)$к\ge 2$; тобто ми знаємо, що для цього конкретного k:

«якщо z має властивість, яка$z+\frac{1}{z}$є цілим числом, потім$z^{м}+\frac{}{}$1zмтакож є цілим числом для всіх m,$0\le м\le к$».

Бажаємо довести, що$Р(к+1)$тоді має бути правдою.

Якщо$z+\frac{1}{z}$є цілим числом, потім, по$Р(к)$,

»$z^{м}+\frac{}{}$1zмтакож є цілим числом для всіх m,$0\le м\le к$».

Отже, щоб довести, що$Р(к+1)$тримає, нам потрібно лише показати, що

»$z^{к+1}+\frac{}{}$1zк+1є цілим числом».

За біноміальною теоремою:$\begin{array}{ccc}{(z+\genfrac{}{}{0.1ex}{}{1}{z})}^{к+1}\hfill & =\hfill & (z^{к+1}+\genfrac{}{}{0.1ex}{}{1}{z^{к+1}})+\left(\genfrac{}{}{0ex}{}{к+1}{1}\right)(z^{к-1}+\genfrac{}{}{0.1ex}{}{1}{z^{к-1}})\hfill \\ \hfill & \hfill & +\left(\genfrac{}{}{0ex}{}{к+1}{2}\right)(z^{к-3}+\genfrac{}{}{0.1ex}{}{1}{z^{к-3}})+\cdots \hfill \end{array}$

LHS є цілим числом (так як$z+\frac{1}{z}$є цілим числом), і (по$Р(к)$) кожен член на RHS є цілим числом, за винятком, можливо, першого. Отже, перший член - це різниця двох цілих чисел, тому також має бути цілим числом.

Звідси$Р(к+1)$це правда.

Якщо ми об'єднаємо ці дві точки кулі, ми довели, що»$Р(п)$тримає для всіх$п\ge 1$». КВЕД

Примітка: Якщо$к+1=2м$є рівним, розширення${\left(z+\frac{1}{z}\right)}^{к+1}$має непарну кількість термінів, тому RHS вищезгаданого повторно згрупованого розширення закінчується терміном$(\begin{array}{}\end{array}$2мм)·zм·(1z)м, який також є цілим числом.

242.

Примітка: У розв'язку задачі 241. ми включили умову на z як частину твердження$Р(п)$.

У задачі 242. доведений результат має аналогічну фонову гіпотезу — «Нехай p буде простим числом». Це може зробити індукцію зрозумілішою, якщо, як і в постановці Проблеми, ця гіпотеза викладена перед початком індукційного доказу.

Нехай p будь-яке просте число. Ми пускаємо$Р(п)$бути твердженням:

»${п}^{р}-п$ділиться на p».

•$Р(1)$вірно (так як$1^{р}-1=0=0\times р$, Який ділиться на p).

• Припустимо, що$Р(к)$вірно для деяких конкретних (невизначений)$к\ge 1$; тобто ми знаємо, що для цього конкретного k:

»${к}^{р}-к$ділиться на p».

Бажаємо довести$Р(к+1)$— тобто,

»${(к+1)}^{р}-(к+1)$ділиться на p»

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

$$\begin{array}{lll}{(к+1)}^{р}-(к+1)\hfill & =\hfill & \left[{к}^{р}+\left(\begin{array}{c}р\\ р-1\end{array}\right){к}^{р-1}+\left(\begin{array}{c}р\\ р-2\end{array}\right){к}^{р-2}+\cdots +\left(\begin{array}{c}р\\ 1\end{array}\right)к+1\right]\hfill \\ \hfill & \hfill & -(к+1)\hfill \\ \hfill & =\hfill & ({к}^{р}-к)+\left[\left(\begin{array}{c}р\\ р-1\end{array}\right){к}^{р-1}+\left(\begin{array}{c}р\\ р-2\end{array}\right){к}^{р-2}+\cdots +\left(\begin{array}{c}р\\ 1\end{array}\right)к\right].\hfill \end{array}$$

За$Р(к)$, Перша дужка на RHS ділиться на p; і в кожному з інших членів кожен з біноміальних коефіцієнтів$\left(\begin{array}{c}р\\ р\end{array}\right)$,$0<р<р$,

• є цілим числом, і

• має множник «p» в чисельнику і немає такого коефіцієнта в знаменнику.

Отже, кожен член у другій дужці кратний p. Так RHS (а отже, і LHS) ділиться на р.

Звідси$Р(к+1)$це правда.

Якщо ми об'єднаємо ці дві точки кулі, ми довели, що»$Р(п)$тримає для всіх$п\ge 1$». КВЕД

243.

$$0.037037037...\text{(на віки віків)}=\frac{37}{1000}+\frac{37}{1000000}+\frac{37}{1000000000}+\cdots \text{(на віки віків)}.$$

Це геометричний ряд з першим терміном$a=\frac{37}{1000}$і загальне співвідношення$р=\frac{1}{1000}$, і так має суму

$$\frac{a}{1-р}=\frac{37}{999}=\frac{1}{27}.$$

244.

(a) Кожна людина отримує в цілому:

$$\frac{1}{4}+{\left(\frac{1}{4}\right)}^2+{\left(\frac{1}{4}\right)}^3+{\left(\frac{1}{4}\right)}^4+\cdots \text{(на віки віків)}=\frac{1}{3}$$

(тут$a=\frac{1}{4}=р$).

(б) У вас є

$$1-\frac{1}{2}+\frac{1}{4}-\frac{1}{8}+\cdots \text{(на віки віків)}=\frac{2}{3}$$

(тут$a=1$,$р=-\frac{1}{2}$); У мене є

$$\frac{1}{2}-\frac{1}{4}+\frac{1}{8}-\cdots \text{(на віки віків)}=\frac{1}{3}$$

(тут$a=\frac{1}{2}$,$р=-\frac{1}{2}$).

245. Потяги знаходяться на відстані 120 км один від одного, а муха рухається зі швидкістю 50 км/год до поїзда B, який спочатку знаходиться на відстані 120 км і рухається зі швидкістю 30 км/год.

Відносна швидкість польоту і поїзда В становить 80 км/год, тому вона займає$\genfrac{}{}{0.1ex}{}{3}{2}$годин до їх зустрічі. За цей час поїзд А і поїзд B пройшли 45 км, тому вони тепер знаходяться на відстані 30 км один від одного. Потім муха повертає праворуч і летить назад до поїзда А.

Відносна швидкість польоту і поїзда А тоді також становить 80 км/год, так що це займає всього$\genfrac{}{}{0.1ex}{}{3}{8}$годин (або 22,5 хвилини) для польоту, щоб повернутися до поїзда А. Поїзд А та Поїзд B подорожували$\genfrac{}{}{0.1ex}{}{45}{4}$км в цей час, тому вони зараз$\genfrac{}{}{0.1ex}{}{30}{4}$км один від одного. Потім муха обертається і летить прямо назад до поїзда B.

Потяг B є$\genfrac{}{}{0.1ex}{}{30}{4}$км, а відносна швидкість польоту і поїзда B знову 80 км/год, тому подорож займає$\genfrac{}{}{0.1ex}{}{3}{32}$годин (або 5,625 хвилин).

Продовжуючи таким чином, ми бачимо, що муха бере

$$\frac{3}{2}+\frac{3}{8}+\frac{3}{32}+\frac{3}{128}+\cdots \text{(на віки віків)}=2\text{годин}.$$Отже, муха подорожує 100 км, перш ніж бути роздавлений.

Примітка: Два поїзди наближаються один до одного зі швидкістю 60 км/год, тому вони розбиваються рівно за 2 години — за цей час муха проїжджає 100 км.

246.

(а) (i)$3^2>2^2$; тому

$$\frac{1}{3^2}<\frac{1}{2^2},$$

тому

$$\frac{1}{2^2}+\frac{1}{3^2}<\frac{2}{2^2}=\frac{1}{2}.$$

(ii)$7^2>6^2>5^2>4^2$; тому

$$\frac{1}{7^2}<\frac{1}{6^2}<\frac{1}{5^2}<\frac{1}{4^2},$$

тому

$$\frac{1}{4^2}+\frac{1}{5^2}+\frac{1}{6^2}+\frac{1}{7^2}<\frac{4}{4^2}=\frac{1}{4}.$$

(b) Аргумент у частині (a) дає верхню межу для кожного виразу в дужках у сумі

$$\left(\frac{1}{1^2}\right)+\left(\frac{1}{2^2}+\frac{1}{3^2}\right)+\left(\frac{1}{4^2}+\frac{1}{5^2}+\frac{1}{6^2}+\frac{1}{7^2}\right)+\left(\frac{1}{8^2}+\cdots +\frac{1}{{15}^2}\right)+\cdots$$

Замінюючи кожну дужку на її верхню межу, ми бачимо, що сума дорівнює

$\begin{array}{ccc}\hfill & <\hfill & \genfrac{}{}{0.1ex}{}{1}{1^2}+\genfrac{}{}{0.1ex}{}{2}{2^2}+\genfrac{}{}{0.1ex}{}{4}{4^2}+\genfrac{}{}{0.1ex}{}{8}{8^2}+\cdots \hfill \\ \hfill & =\hfill & 1+\genfrac{}{}{0.1ex}{}{1}{2}+\genfrac{}{}{0.1ex}{}{1}{4}+\genfrac{}{}{0.1ex}{}{1}{8}+\cdots \text{(на віки віків)}\hfill \\ \hfill & =\hfill & 2.\hfill \end{array}$

(c) Кінцеві часткові суми

$$S_{п}=\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+\cdots +\frac{}{}$$1п2

• стабільно зростати, оскільки ми приймаємо все більше і більше термінів, і

• кожна часткова сума$S_{п}$менше, ніж$2$. Зрозуміло, що ці часткові суми утворюють послідовність.

$$1=S_1<S_2<S_3<...<S_{п}<S_{п+1}<...<2.$$

Звідси випливає, що існує якесь (невідоме) число$S\le 2$до яких часткові суми сходяться як$п\to \infty$, і ми приймаємо це (невідоме) точне значення S як точне значення нескінченної суми

$$\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+\cdots +\frac{}{}$$1п2+⋯(на віки віків)

Побачити, наприклад, що$S>\frac{17}{12}$, зауважте, що

$\begin{array}{ccc}S\hfill & >\hfill & S_4\hfill \\ \hfill & =\hfill & \genfrac{}{}{0.1ex}{}{1}{1^2}+\genfrac{}{}{0.1ex}{}{1}{2^2}+\genfrac{}{}{0.1ex}{}{1}{3^2}+\genfrac{}{}{0.1ex}{}{1}{4^2}\hfill \\ \hfill & =\hfill & 1+\genfrac{}{}{0.1ex}{}{1}{4}+\genfrac{}{}{0.1ex}{}{1}{9}+\genfrac{}{}{0.1ex}{}{1}{16}\hfill \\ \hfill & >\hfill & \genfrac{}{}{0.1ex}{}{17}{12}.\hfill \end{array}$

Примітка 1: Твердження, що

«зростаюча послідовність часткових сум$S_{п}$, все менше 2, повинні сходитися до деякого числа$S\le 2$»

є фундаментальною властивістю дійсних чисел — називається повнотою.

Примітка 2: Так само, як можна отримати кращі і кращі нижчі межі для S - як»$\frac{17}{12}<S$», так що можна поліпшити верхню межу»$S<2$». Наприклад, якщо в частині (b) ми уникаємо заміни третього терміну$\genfrac{}{}{0.1ex}{}{1}{9}$від$\genfrac{}{}{0.1ex}{}{1}{4}$, ми отримуємо кращу верхню межу»$S<\frac{67}{36}$», який$\genfrac{}{}{0.1ex}{}{5}{36}$менше 2.

247.

(а) Нехай$Р(п)$бути твердженням:

»$\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+\cdots +\frac{1}{{п}^2}\le 2-\frac{1}{п}$».

• Тоді LHS або$Р(1)=\frac{1}{1^2}=1$, і RHS$Р(1)=2-1=1$. Звідси$Р(1)$це правда.

• Припустимо, ми знаємо, що$Р(к)$вірно для деяких$к\ge 1$. Ми хочемо довести, що$Р(к+1)$тримає.

$\begin{array}{ccc}\text{ЛГС}\mathbf{Р}(к+1)\hfill & =\hfill & \genfrac{}{}{0.1ex}{}{1}{1^2}+\genfrac{}{}{0.1ex}{}{1}{2^2}+\genfrac{}{}{0.1ex}{}{1}{3^2}+\cdots +\genfrac{}{}{0.1ex}{}{1}{{к}^2}+\genfrac{}{}{0.1ex}{}{1}{{(к+1)}^2}\hfill \\ \hfill & =\hfill & [\genfrac{}{}{0.1ex}{}{1}{1^2}+\genfrac{}{}{0.1ex}{}{1}{2^2}+\genfrac{}{}{0.1ex}{}{1}{3^2}+\cdots +\genfrac{}{}{0.1ex}{}{1}{{к}^2}]+\genfrac{}{}{0.1ex}{}{1}{{(к+1)}^2}\hfill \\ \hfill & \le \hfill & [2-\genfrac{}{}{0.1ex}{}{1}{к}]+\genfrac{}{}{0.1ex}{}{1}{{(к+1)}^2}\hfill \\ \hfill & =\hfill & 2-[\genfrac{}{}{0.1ex}{}{1}{к}-\genfrac{}{}{0.1ex}{}{1}{{(к+1)}^2}]\hfill \\ \hfill & <\hfill & 2-\genfrac{}{}{0.1ex}{}{1}{к+1}.\hfill \end{array}$

Звідси$Р(к+1)$тримає.

$\therefore$ $Р(1)$тримає; і коли завгодно$Р(к)$як відомо, правда,$Р(к+1)$також вірно.

$\therefore$ $Р(п)$правда, для всіх$п\ge 1$. КВЕД

(б) Нехай$Р(п)$бути твердженням:

»$\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+\cdots +\frac{}{}$1п2<1.68−1п».

• Потім

$$\text{ЛГС}Р(4)=\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+\frac{1}{4^2}=1.423611111\cdots ,$$

та RHS$Р(4)=1.43$. Звідси$Р(4)$це правда.

• Припустимо, ми знаємо, що$Р(к)$вірно для деяких$к\ge 4$. Ми хочемо довести, що$Р(к+1)$тримає.

$\begin{array}{ccc}\text{ЛГС}\mathbf{Р}(к+1)\hfill & =\hfill & \genfrac{}{}{0.1ex}{}{1}{1^2}+\genfrac{}{}{0.1ex}{}{1}{2^2}+\genfrac{}{}{0.1ex}{}{1}{3^2}+\cdots +\genfrac{}{}{0.1ex}{}{1}{{к}^2}+\genfrac{}{}{0.1ex}{}{1}{{(к+1)}^2}\hfill \\ \hfill & =\hfill & (\genfrac{}{}{0.1ex}{}{1}{1^2}+\genfrac{}{}{0.1ex}{}{1}{2^2}+\genfrac{}{}{0.1ex}{}{1}{3^2}+\cdots +\genfrac{}{}{0.1ex}{}{1}{{к}^2})+\genfrac{}{}{0.1ex}{}{1}{{(к+1)}^2}\hfill \\ \hfill & <\hfill & [1.68-\genfrac{}{}{0.1ex}{}{1}{к}]+\genfrac{}{}{0.1ex}{}{1}{{(к+1)}^2}\hfill \\ \hfill & =\hfill & 1.68-[\genfrac{}{}{0.1ex}{}{1}{к}-\genfrac{}{}{0.1ex}{}{1}{{(к+1)}^2}]\hfill \\ \hfill & <\hfill & 1.68-\genfrac{}{}{0.1ex}{}{1}{к+1}.\hfill \end{array}$

Звідси$Р(к+1)$тримає.

$\therefore$ $Р(1)$тримає; і коли завгодно$Р(к)$як відомо, правда,$Р(к+1)$також вірно.

$\therefore$ $Р(п)$правда, для всіх$п\ge 1$.

248.

(а) (i)$п!=п\times (п-1)\times (п-2)\times \cdots \times 3\times 2\times 1\ge 2\times 2\times 2\times \cdots \times 2\times 1=2^{п-1}$щоразу$п\ge 1$.

$\therefore$ $\frac{1}{п!}\le {\left(\frac{1}{2}\right)}^{п-1}$для всіх$п\ge 1$.

$\therefore$ $\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{п!}\le 1+\left[1+\frac{1}{2}+{\left(\frac{1}{2}\right)}^2+\cdots +{\left(\frac{1}{2}\right)}^{п-1}\right]<3$для всіх$п\ge 0$.

(ii) Коли ми продовжуємо додавати все більше і більше термінів, кожна кінцева сума

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{п!}$$

більше попередньої суми. Оскільки кожна кінцева сума

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{п!}<3,$$

суми збільшуються, але ніколи не досягають 3, тому вони накопичуються ближче і ближче до значення «е»$\le 3$. Причому це значення «е», безумовно, більше суми перших двох членів$\frac{1}{0!}+\frac{1}{1!}=2$, так$2<е\le 3$.

(б) (i) Нехай$Р(п)$бути твердженням:

»$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{п!}\le 3-\frac{1}{п\cdot п!}$».

•$\text{ЛГС}Р(1)=2=\text{RHS}Р(1)$. Звідси$Р(1)$це правда.

• Припустимо, ми знаємо, що$Р(к)$вірно для деяких$к\ge 1$. Ми хочемо довести, що$Р(к+1)$тримає.

$\begin{array}{ccc}\text{ЛГС}\mathbf{Р}(к+1)\hfill & =\hfill & \genfrac{}{}{0.1ex}{}{1}{0!}+\genfrac{}{}{0.1ex}{}{1}{1!}+\genfrac{}{}{0.1ex}{}{1}{2!}+\cdots +\genfrac{}{}{0.1ex}{}{1}{(к+1)!}\hfill \\ \hfill & =\hfill & [\genfrac{}{}{0.1ex}{}{1}{0!}+\genfrac{}{}{0.1ex}{}{1}{1!}+\genfrac{}{}{0.1ex}{}{1}{2!}+\cdots +\genfrac{}{}{0.1ex}{}{1}{к!}]+\genfrac{}{}{0.1ex}{}{1}{(к+1)!}\hfill \\ \hfill & \le \hfill & 3-\genfrac{}{}{0.1ex}{}{1}{к\cdot к!}+\genfrac{}{}{0.1ex}{}{1}{(к+1)!}\hfill \\ \hfill & =\hfill & 3-\genfrac{}{}{0.1ex}{}{1}{к(к+1)!}\hfill \\ \hfill & <\hfill & 3-\genfrac{}{}{0.1ex}{}{1}{(к+1)\cdot (к+1)!}\hfill \end{array}$

Звідси$Р(к+1)$тримає.

$\cdot$ $Р(1)$тримає; і коли завгодно$Р(к)$як відомо, правда,$Р(к+1)$також вірно.

$\cdot$ $Р(п)$правда, для всіх$п\ge 1$.

(ii) [Міркування тут використовує константу «3», ігноруючи уточнення»$3-\frac{1}{п.п!}$», і так звучить точно так само, як частина (a) (ii).] Коли ми додаємо більше термінів, кожна кінцева сума

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{п!}$$

більше попередньої суми. Оскільки кожна кінцева сума

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{п!}<3,$$

часткові суми збільшуються, але ніколи не досягають 3; тому вони накопичуються ближче і ближче до значення «е»$\le 3$. Причому це значення «е», безумовно, більше суми перших трьох членів$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}=2.5$, так$2.5<е\le 3$.

(c) Примітка: Уважно вивчіть роль, яку відіграє число «3» у наведеному вище індукційному доказі в (b) (ii). Він потрібен саме для того, щоб підтвердити заяву.$Р(1)$: так як$\frac{1}{0!}+\frac{1}{1!}=3-\frac{1}{1\times 1!}$». Але число «3» не грає активної ролі на другому етапі індукції, і може бути замінено будь-яким іншим числом, яке ми вибрали.

Точне значення «е» нескінченного ряду насправді не впливає на те, що відбувається, коли$п=1$. Припустимо, ми запитаємо: «Яке число$C_2$слід замінити «3», якщо ми хочемо лише довести, що

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{п!}\le C_2-\frac{1}{п\cdot п!},\text{для всіх}п\ge 2?$$

Єдина частина індукційного доказу, де$C_2$тоді має значення, коли ми намагаємося перевірити, що$Р(2)$тримає; тому ми повинні вибрати найменший можливий$C_2$задовольнити

$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}\le C_2-\frac{1}{2.2!}:$

тобто,$C_2=2.75$.

(i) Нехай$Р(п)$бути твердженням:

»$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{п!}\le 2.75-\frac{1}{п\cdot п!}$».

• LHS або$Р(2)=2.5$; RHS або$Р(2)=2.75-\frac{1}{4}$. Звідси$Р(2)$це правда.

• Припустимо, ми знаємо, що$Р(к)$вірно для деяких$к\le 2$. Ми хочемо довести, що$Р(к+1)$тримає.

$\begin{array}{ccc}\text{ЛГС}\mathbf{Р}(к+1)\hfill & =\hfill & \genfrac{}{}{0.1ex}{}{1}{0!}+\genfrac{}{}{0.1ex}{}{1}{1!}+\genfrac{}{}{0.1ex}{}{1}{2!}+\cdots +\genfrac{}{}{0.1ex}{}{1}{(к+1)!}\hfill \\ \hfill & =\hfill & [\genfrac{}{}{0.1ex}{}{1}{0!}+\genfrac{}{}{0.1ex}{}{1}{1!}+\genfrac{}{}{0.1ex}{}{1}{2!}+\cdots +\genfrac{}{}{0.1ex}{}{1}{к!}]+\genfrac{}{}{0.1ex}{}{1}{(к+1)!}\hfill \\ \hfill & \le \hfill & 2.75-\genfrac{}{}{0.1ex}{}{1}{к\cdot к!}+\genfrac{}{}{0.1ex}{}{1}{(к+1)!}\hfill \\ \hfill & =\hfill & 2.75-\genfrac{}{}{0.1ex}{}{1}{к(к+1)!}\hfill \\ \hfill & <\hfill & 2.75-\genfrac{}{}{0.1ex}{}{1}{(к+1)(к+1)!}\hfill \end{array}$

Звідси$Р(к+1)$тримає.

$\therefore$ $Р(2)$тримає; і коли завгодно$Р(к)$як відомо, правда,$Р(к+1)$також вірно.

$\therefore$ $Р(п)$правда, для всіх$п\ge 2$. КВЕД

(ii) Коли ми додаємо більше термінів, кожна кінцева сума

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{п!}$$

більше попередньої суми.

Оскільки кожна кінцева сума

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{п!}<2.75,$$

кінцеві суми збільшуються, але ніколи не досягають 2,75, тому вони накопичуються ближче і ближче до значення «е»$\le 2.75$. Причому ця величина «е», безумовно, більше суми перших чотирьох членів

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!}>2.66,$$

тому$2.66<е\le 2.75$.

(d) (i) Нехай$Р(п)$бути твердженням:

»$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{п!}\le 2.7222\cdots (\text{на віки віків)}-\frac{1}{п.п!}$».

•$\text{ЛГС}Р(3)=\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!}=2.66\cdots \text{(на віки віків)}$;$\text{RHS}Р(3)=2.7222\cdots \text{(на віки віків)}-\frac{1}{18}=2.66\cdots \text{(на віки віків)}$. Звідси$Р(3)$це правда.

• Припустимо, ми знаємо, що$Р(к)$вірно для деяких$к\ge 3$. Ми хочемо довести, що$Р(к+1)$тримає.

$\begin{array}{ccc}\text{ЛГС}\mathbf{Р}(к+1)\hfill & =\hfill & \genfrac{}{}{0.1ex}{}{1}{0!}+\genfrac{}{}{0.1ex}{}{1}{1!}+\genfrac{}{}{0.1ex}{}{1}{2!}+\cdots +\genfrac{}{}{0.1ex}{}{1}{(к+1)!}\hfill \\ \hfill & =\hfill & [\genfrac{}{}{0.1ex}{}{1}{0!}+\genfrac{}{}{0.1ex}{}{1}{1!}+\genfrac{}{}{0.1ex}{}{1}{2!}+\cdots +\genfrac{}{}{0.1ex}{}{1}{к!}]+\genfrac{}{}{0.1ex}{}{1}{(к+1)!}\hfill \\ \hfill & \le \hfill & 2.7222\cdots \left(\text{назавжди}\right)-\genfrac{}{}{0.1ex}{}{1}{к\cdot к!}+\genfrac{}{}{0.1ex}{}{1}{(к+1)!}\hfill \\ \hfill & =\hfill & 2.7222\cdots \left(\text{назавжди}\right)-\genfrac{}{}{0.1ex}{}{1}{к(к+1)!}\hfill \\ \hfill & <\hfill & 2.7222\cdots \left(\text{назавжди}\right)-\genfrac{}{}{0.1ex}{}{1}{(к+1)(к+1)!}\hfill \end{array}$

Звідси$Р(к+1)$тримає.

$\cdot$ $Р(3)$тримає; і коли завгодно$Р(к)$як відомо, правда,$Р(к+1)$також вірно.

$\therefore$ $Р(п)$правда, для всіх$п\ge 3$.

(ii) Коли ми додаємо більше термінів, кожна кінцева сума

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{п!}$$

більше попередньої суми.

Оскільки кожна кінцева сума

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{п!}<2.7222\cdots \text{(на віки віків)},$$

кінцеві суми збільшуються, але ніколи не досягають$2.7222\cdots$(назавжди), тому вони накопичуються ближче і ближче до значення «е»$\le 2.7222\cdots$(назавжди). Причому ця величина «е», безумовно, більше суми перших п'яти членів

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!}+\frac{1}{4!}>2.708,$$

тому$2.708<е\le 2.7222\cdots \text{(на віки віків)}$.

Примітка: Цей процес доопрацювання може тривати до нескінченності. Але нам залишається лише піти ще один крок, щоб визначити значення «е» з дивовижною точністю.

Наступний крок використовує той самий доказ, щоб показати, що

»$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{п!}\le 2.7185-\frac{1}{п\cdot п!}$, для всіх$п\ge 4$»,

і зробити висновок, що нескінченна сума

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{п!}+\cdots (\text{назавжди})$$

має певне значення «e», яке лежить десь між$2.716$і$2.71875$.

Потім ми могли б повторити той самий доказ, щоб показати, що

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{п!}\le 2.718333\cdots (\text{назавжди})-\frac{1}{п\cdot п!},\text{для всіх}п\ge 5,$$

і використовувати нижню межу$2.7177...$з перших семи термінів зробити висновок, що нескінченна сума

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{п!}+\cdots \text{(на віки віків)}$$

має певне значення «e», яке лежить десь між$2.7177$і$2.718333\cdots$(назавжди). І так далі.

249. Нехай$Р(п)$бути твердженням:

»$\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots +\frac{1}{\sqrt{п}}\ge \sqrt{п}$».

• LHS$Р(1)=1=$RHS$Р(1)$. Звідси$Р(1)$це правда.

• Припустимо, ми знаємо, що$Р(к)$вірно для деяких$к\ge 1$. Ми хочемо довести, що$Р(к+1)$тримає.

$\begin{array}{ccc}\text{ЛГС}\mathbf{Р}(к+1)\hfill & =\hfill & \genfrac{}{}{0.1ex}{}{1}{\sqrt{1}}+\genfrac{}{}{0.1ex}{}{1}{\sqrt{2}}+\genfrac{}{}{0.1ex}{}{1}{\sqrt{3}}+\cdots +\genfrac{}{}{0.1ex}{}{1}{\sqrt{к+1}}\hfill \\ \hfill & =\hfill & (\genfrac{}{}{0.1ex}{}{1}{\sqrt{1}}+\genfrac{}{}{0.1ex}{}{1}{\sqrt{2}}+\genfrac{}{}{0.1ex}{}{1}{\sqrt{3}}+\cdots +\genfrac{}{}{0.1ex}{}{1}{\sqrt{к}})+\genfrac{}{}{0.1ex}{}{1}{\sqrt{(к+1)}}\hfill \\ \hfill & \ge \hfill & \sqrt{к}+\genfrac{}{}{0.1ex}{}{1}{\sqrt{к+1}}\hfill \\ \hfill & \ge \hfill & \sqrt{к+1}(\text{так як}\genfrac{}{}{0.1ex}{}{1}{\sqrt{к+1}}\ge \genfrac{}{}{0.1ex}{}{1}{\sqrt{к+1}+\sqrt{к}}).\hfill \end{array}$

Звідси$Р(к+1)$тримає.

$\therefore$ $Р(1)$тримає; і коли завгодно$Р(к)$як відомо, правда,$Р(к+1)$також вірно.

$\therefore$ $Р(п)$правда, для всіх$п\ge 1$. КВЕД

250. Нехай a, b бути дійсними числами такі, що$a\ne б$, і$a+б>0$.

Один з a, b тоді більший, і ми можемо припустити, що це a - так що$a>б$. Якщо$a>б>0$, потім$a^{п}>{б}^{п}>0$для всіх n; якщо$б<0$, потім$a+б>0$означає, що$a=\left|a\right|>\left|б\right|$, так$a^{п}>{б}^{п}$для всіх п.

Нехай$Р(п)$бути твердженням:

»$\frac{a^{п}+{б}^{п}}{2}\ge {\left(\frac{a+б}{2}\right)}^{п}$».

• LHS$Р(1)=\frac{a+б}{2}=\text{RHS}Р(1)$. Звідси$Р(1)$це правда.

• Припустимо, ми знаємо, що$Р(к)$вірно для деяких$к\ge 1$. Ми хочемо довести, що$Р(к+1)$тримає.

$\begin{array}{ccc}\text{RHS}\mathbf{Р}(к+1)\hfill & =\hfill & {\left(\genfrac{}{}{0.1ex}{}{a+б}{2}\right)}^{к+1}\hfill \\ \hfill & =\hfill & \genfrac{}{}{0.1ex}{}{a+б}{2}\cdot {\left(\genfrac{}{}{0.1ex}{}{a+б}{2}\right)}^{к}\hfill \\ \hfill & \le \hfill & \genfrac{}{}{0.1ex}{}{a+б}{2}\cdot \genfrac{}{}{0.1ex}{}{a^{к}+{б}^{к}}{2}\left(\text{від}\mathbf{Р}\right(к\left)\right)\hfill \\ \hfill & =\hfill & \genfrac{}{}{0.1ex}{}{a^{к+1}+{б}^{к+1}}{4}+\genfrac{}{}{0.1ex}{}{a{б}^{к}+бa^{к}}{4}\hfill \\ \hfill & <\hfill & \genfrac{}{}{0.1ex}{}{a^{к+1}+{б}^{к+1}}{2}\left(\text{так як}\right(a^{к}-{б}^{к}\left)\right(a-б)>0).\hfill \end{array}$

Звідси$Р(к+1)$тримає.

$\therefore$ $Р(1)$тримає; і коли завгодно$Р(к)$як відомо, правда,$Р(к+1)$також вірно.

$\therefore$ $Р(п)$правда, для всіх$п\ge 1$.

251. Нехай x - будь-яке дійсне число$\ge -1$.

Якщо$х=-1$, потім${(1+х)}^{п}=0\ge 1-п=1+пх$, для всіх$п\ge 1$.

Таким чином, ми можемо припустити, що$х>-1$, так$1+х>0$.

Нехай$Р(п)$бути твердженням:»${(1+х)}^{п}\ge 1+пх$».

• LHS$Р(1)=1+х=\text{RHS}Р(1)$. Звідси$Р(1)$це правда.

• Припустимо, ми знаємо, що$Р(к)$вірно для деяких$к\ge 1$. Ми хочемо довести, що$Р(к+1)$тримає.

$\begin{array}{ccc}\text{ЛГС}\mathbf{Р}(к+1)\hfill & =\hfill & {(1+х)}^{к+1}\hfill \\ \hfill & =\hfill & (1+х)\cdot {(1+х)}^{к}\hfill \\ \hfill & \ge \hfill & (1+х)\cdot (1+кх)\left(\text{від}\mathbf{Р}\right(к),\text{так як}1+х>0)\hfill \\ \hfill & =\hfill & 1+(к+1)х+к{х}^2\hfill \\ \hfill & \ge \hfill & 1+(к+1)х\hfill \end{array}$

Звідси$Р(к+1)$тримає.

$\therefore$ $Р(1)$тримає; і коли завгодно$Р(к)$як відомо, правда,$Р(к+1)$також вірно.

$\therefore$ $Р(п)$правда, для всіх$п\ge 1$.

252. Проблема обговорюється після постановки завдання 252. в основному тексті.

253.

(а) (i)$3>2$, так$\frac{1}{3}<\frac{1}{2}$.$\therefore$ $\frac{1}{2}+\frac{1}{3}<\frac{1}{2}+\frac{1}{2}=1$.

(ii)$5,6,7>4$; звідси$\frac{1}{5},\frac{1}{6},\frac{1}{7}$є всі$<\frac{1}{4}$.$\therefore$ $\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}<\frac{1}{4}+\frac{1}{4}+\frac{1}{4}+\frac{1}{4}=1$.

(iii) Нехай$Р(п)$бути твердженням:

»$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{2^{п}-1}<п$».

Тоді

•$Р(2)$істинно по (i), так як

$$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}<1+\left(\frac{1}{2}+\frac{1}{2}\right)=2.$$

• Припустимо, що$Р(к)$вірно для деяких$к\ge 2$.

$$\begin{array}{lll}\text{ЛГС}Р(к+1)\hfill & =\hfill & \left[\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{2^{к}-1}\right]\hfill \\ \hfill & \hfill & +\left[\frac{1}{2^{к}}+\cdots +\frac{1}{2^{к+1}-1}\right].\hfill \end{array}$$

Перший кронштейн - це$<к$(по$Р(к)$); і кожен з$2^{к}$терміни в другій дужці$\le \frac{1}{2^{к}}$, Таким чином, весь кронштейн$\le 1$.

Звідси LHS$Р(к+1)<к+1$, так$Р(к+1)$це правда.

Звідси$Р(п)$вірно для всіх$п\ge 2$.

(iv) На найпершому етапі (частина (i)) ми замінили$\frac{1}{2}+\frac{1}{3}$від$\frac{1}{2}+\frac{1}{2}=1$. Звідси, коли$п\ge 2$, ми знаємо, що дві сторони$Р(п)$відрізняються щонайменше$\frac{1}{2}-\frac{1}{3}$. Ця різниця більше$\frac{}{}$12пколи$п\ge 3$, Отже (iv) випливає.

(б)

(i)$3<4$, так$\frac{1}{3}>\frac{1}{4}$.

$\therefore$ $\frac{1}{3}+\frac{1}{4}>\frac{1}{4}+\frac{1}{4}=\frac{1}{2}$.

(ii)$5,6,7<8$; звідси$\frac{1}{5},\frac{1}{6},\frac{1}{7}$є всі$>\frac{1}{8}$.

$\therefore$ $\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}>\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}=\frac{1}{2}$.

(iii) Нехай$Р(п)$бути твердженням:

»$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{}{}$12п>1+п2».

Тоді

•$Р(2)$істинно по (i), так як

$\begin{array}{ccc}\genfrac{}{}{0.1ex}{}{1}{1}+\genfrac{}{}{0.1ex}{}{1}{2}+\genfrac{}{}{0.1ex}{}{1}{3}+\genfrac{}{}{0.1ex}{}{1}{4}\hfill & =\hfill & 1+\genfrac{}{}{0.1ex}{}{1}{2}+(\genfrac{}{}{0.1ex}{}{1}{3}+\genfrac{}{}{0.1ex}{}{1}{4})\hfill \\ \hfill & >\hfill & 1+\genfrac{}{}{0.1ex}{}{1}{2}+(\genfrac{}{}{0.1ex}{}{1}{4}+\genfrac{}{}{0.1ex}{}{1}{4})\hfill \\ \hfill & =\hfill & 1+2\times \genfrac{}{}{0.1ex}{}{1}{2}.\hfill \end{array}$

• Припустимо, що$Р(к)$вірно для деяких$к\ge 2$.

ЛГС$Р(к+1)=\left[\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{}{}\right]$12к+12к+1+⋯+12к+1.

Перший кронштейн - це$>1+\frac{к}{2}$(по$Р(к)$); і кожен з$2^{к}$терміни в другій дужці$\ge \frac{1}{2^{к+1}}$, Таким чином, весь кронштейн$\ge \frac{1}{2}$. Звідси LHS$Р(к+1)>1+\frac{к+1}{2}$, так$Р(к+1)$це правда.

Звідси$Р(п)$вірно для всіх$п\ge 2$.

254.

(а) Ми використовуємо індукцію. Нехай$Р(п)$бути твердженням:

«n однакових прямокутних смуг довжиною 2 рівноважуються точно по краю столу, якщо послідовні відстані виступу (спочатку за край столу, потім за передній край смуги, безпосередньо нижче, і так далі) є термінами$\frac{1}{п},\frac{1}{п-1},\frac{1}{п-2},...,\frac{1}{3},\frac{1}{2},\frac{1}{1}$скінченного гармонійного ряду в зворотному порядку».

• Коли$п=1$, одна смуга, яка виступає на відстані 1 за край столу, має свій центр ваги точно над краєм столу. Звідси$Р(1)$це правда.

• Припустимо, що ми знаємо, що$Р(к)$вірно для деяких$к\ge 1$.

Нехай$к+1$однакові смуги розташовуються так, як описано в заяві$Р(к+1)$.

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

Дозволяти M - маса кожної смуги; так як передній край нижньої смуги - відстань$\frac{1}{к+1}$за край столу верхні k смужки виробляють комбінований момент про край столу, рівний$$кМ×1к+1.

Центр ваги нижньої смуги - відстань$1-\frac{1}{к+1}=\frac{к}{к+1}$від краю столу в зворотному напрямку; отже, сприяє момент про край столу рівний$М\times \left(-\frac{к}{к+1}\right)$.

$\therefore$сумарний момент всієї стопки навколо краю столу дорівнює нулю, тому центр ваги комбінованого стека$к+1$смужки лежать рівно над краєм столу. Звідси$Р(к+1)$це правда.

Звідси$Р(п)$вірно для всіх$п\ge 1$.

(б) Проблема 253. (b) (iii) тепер гарантує, що стек$2^{п}$смуги можуть виступати на відстань$>1+\frac{п}{2}$за край столу.

Примітка: Математичний туристичний блог Іварса Петерсена містить запис у 2009

http://mathtourist.blogspot.com/2009/01/overhang.html

який досліджує, як можна отримати великі звіси з меншою кількістю смуг, якщо дозволяється використовувати смуги для противаги тих, що виступають за край столу.

255.

(а) (i) Нехай$Р(п)$бути твердженням:

»$s_{2р-2}<{}_{}$s2р<s2q+1<s2q−1для всіх$р,q$такий, що$1\le р,q\le п$».

•$Р(1)$вірно (так як$s_0$порожня сума, тому

$$0=s_0<s_2=\frac{1}{2}<s_3=\frac{5}{6}<s_1=1.$$

• Припустимо, що$Р(к)$вірно для деяких$к\ge 1$. Тоді велика частина нерівностей у твердженні$Р(к+1)$є частиною заяви$Р(к)$; єдиними видатними нерівностями, які залишаються доведені, є:

$${}_{}$$s2к<s2к+2<s2к+3<s2к+1.

які правдиві, так як

$${}_{}$$s2к+3=s2к+2+12к+3=s2к+1−12к+2+12к+3

і

$${}_{}$$s2к+2=s2к+12к+1−12к+2.

Звідси$Р(к+1)$це правда.

Звідси$Р(п)$вірно для всіх$п\ge 2$.

(ii) «парні суми»$s_0,s_2,s_4,...$збільшуються, але все менше$s_1=1$, тому вони наближаються до деякого значення$s_{еvеп}\le 1$.

«Непарні суми»$s_1,s_3,s_5,...$зменшуються, але всі більше, ніж$s_2=\frac{1}{2}$, тому вони наближаються до деякого значення$s_{odd}\ge \frac{1}{2}$.

«парні суми»$s_0,s_2,s_4,...$збільшуються, але все менше$s_5=\frac{47}{60}$, тому вони наближаються до деякого значення$s_{еvеп}\le \frac{47}{60}$.

«Непарні суми»$s_1,s_3,s_5,...$зменшуються, але всі більше, ніж$s_6=\frac{37}{60}$, тому вони наближаються до деякого значення$s_{odd}\ge \frac{37}{60}$.

Більш того, різниця між послідовними сумами становить$\frac{1}{п}$, і це прагне до нуля, тому різниця між кожною «непарною сумою» і наступною «парною сумою» прагне до нуля, тому$s_{еvеп}={}_{}$sodd.

(b) Доказ з частини (а) переносить слово в слово, з»$\frac{1}{к}$» замінюється на кожному етапі»$a_{к}$».

256. Нехай$Р(п)$бути твердженням:

»$f_{к}$має щонайменше k чітких простих множників».

•$f_1=2$має рівно 1 простий коефіцієнт, тому$Р(1)$це правда.

• Припустимо, що$Р(к)$вірно для деяких$к\ge 1$.

Тоді$f_{к+1}=f_{к}(f_{к}+1)$. перший фактор$f_{к}$має щонайменше k різних простих множників.

І другий фактор$f_{к}+1>f_{к}>1$, Таким чином, має принаймні один простий коефіцієнт.

Більше того$$ЧCF(fк,fк+1)=1, тому другий кронштейн не має спільного з$f_{к}$.

Звідси$f_{к+1}$має принаймні$к+1$різні прості множники, так$Р(к+1)$це правда.

Звідси$Р(п)$вірно для всіх$п\ge 1$.

Примітка: Ця проблема [запропонована Серкан Доган] дає інший доказ результату (Проблема 76. (d)), що список простих чисел продовжується назавжди.

257.

(а) Нехай$Р(п)$бути твердженням: «n різних точок на прямій лінії ділять лінію на$п+1$інтервали».

• 0 точок залишають лінію в первозданному стані — а саме один інтервал — так$Р(0)$це правда.

• Припустимо, що$Р(к)$вірно для деяких$к\ge 0$.

Розглянемо довільну пряму лінію, розділену на$к+1$балів$A_0,A_1,...,A_{к}$.

Тоді k балів$A_1,...,A_{к}$розділити лінію на$к+1$інтервали (по$Р(к)$).

Додаткова точка$A_0$відрізняється від$A_1$,...,$A_{к}$і так повинні лежати всередині одного з цих$к+1$інтервали, і ділить його на дві частини — даючи$(к+1)+1=к+2$інтервали взагалі.

Звідси$Р(к+1)$це правда.

Звідси$Р(п)$вірно для всіх$п\ge 0$.

(b) (i) Ми хочемо, щоб функція R задовольняла

${Р}_0=1,{Р}_1=2,{Р}_2=4,{Р}_3=7.$

Якщо ми помічаємо, що частково (а)$п+1=1+\left(\begin{array}{c}п\\ 1\end{array}\right),$то ми можемо здогадатися, що

$${Р}_{п}=1+\left(\begin{array}{c}п\\ 1\end{array}\right)+\left(\begin{array}{c}п\\ 2\end{array}\right).$$

(ii) Нехай$Р(п)$бути твердженням:

«N різних прямих ліній у площині ділять площину на щонайменше$f(п)=1+\left(\begin{array}{c}п\\ 1\end{array}\right)+\left(\begin{array}{c}п\\ 2\end{array}\right)$регіони».

• 0 ліній залишають площину в первозданному стані — а саме в одній області — так$Р(0)$правда, за умови, що

$$1+\left(\begin{array}{c}0\\ 1\end{array}\right)+\left(\begin{array}{c}0\\ 2\end{array}\right)=1.$$

• Припустимо, що$Р(к)$вірно для деяких$к\ge 0$.

Розглянемо площину, розділену на$к+1$прямі лінії${м}_0,{м}_1,...,{м}_{к}$.

Потім k рядків${м}_1,...,{м}_{к}$розділити площину на максимум

$${Р}_{к}=1+\left(\begin{array}{c}к\\ 1\end{array}\right)+\left(\begin{array}{c}к\\ 2\end{array}\right)$$

регіони (по$Р(к)$).

Додаткова лінія${м}_0$відрізняється від${м}_1,...,{м}_{к}$і так відповідає кожній з цих ліній максимум в одній точці - даючи не більше k точок на лінії${м}_0$. Ці точки ділять${м}_0$в максимум$к+1$інтервалів, і кожному з цих інтервалів відповідає лінія зрізу, де лінія${м}_0$вирізає одну з областей, створених лініями${м}_1,{м}_2,...,{м}_{к}$на дві частини — даючи щонайбільше

$\begin{array}{ccc}{Р}_{к}+(к+1)\hfill & =\hfill & 1+\left(\genfrac{}{}{0ex}{}{к}{1}\right)+\left(\genfrac{}{}{0ex}{}{к}{2}\right)+к+1\hfill \\ \hfill & =\hfill & 1+\left(\genfrac{}{}{0ex}{}{к+1}{1}\right)+\left(\genfrac{}{}{0ex}{}{к+1}{2}\right)\hfill \\ \hfill & =\hfill & {Р}_{к+1}\hfill \end{array}$

регіони взагалі.

Звідси$Р(к+1)$це правда.

Звідси$Р(п)$вірно для всіх$п\ge 0$.

(c) (i) Ми хочемо, щоб функція S задовольняла

$$S_0=1,S_1=2,S_2=4,S_3=8,S_4=15,...$$

Подумавши про відмінності між послідовними термінами в частині (b), ми можемо здогадатися, що

$$S_{п}=\left(\begin{array}{c}п\\ 0\end{array}\right)+\left(\begin{array}{c}п\\ 1\end{array}\right)+\left(\begin{array}{c}п\\ 2\end{array}\right)+\left(\begin{array}{c}п\\ 3\end{array}\right).$$

(ii) Нехай$Р(п)$бути твердженням:

«N різних площин у 3-просторі ділять простір на щонайменше

$S_{п}=\left(\begin{array}{c}п\\ 0\end{array}\right)+\left(\begin{array}{c}п\\ 1\end{array}\right)+\left(\begin{array}{c}п\\ 2\end{array}\right)+\left(\begin{array}{c}п\\ 3\end{array}\right)$

регіони».

• 0 площин залишають наш 3D простір в первозданному стані - а саме один регіон - так$Р(0)$правда — за умови, що

$$\left(\begin{array}{c}0\\ 0\end{array}\right)+\left(\begin{array}{c}0\\ 1\end{array}\right)+\left(\begin{array}{c}0\\ 2\end{array}\right)+\left(\begin{array}{c}0\\ 3\end{array}\right)=1.$$

• Припустимо, що$Р(к)$вірно для деяких$к\ge 0$.

Розглянемо 3D розділений на$к+1$плани${м}_0,{м}_1,...,{м}_{к}$.

Потім k площин${м}_1,...,{м}_{к}$розділити 3D на максимум

$$S_{к}=\left(\begin{array}{c}к\\ 0\end{array}\right)+\left(\begin{array}{c}к\\ 1\end{array}\right)+\left(\begin{array}{c}к\\ 2\end{array}\right)+\left(\begin{array}{c}к\\ 3\end{array}\right)$$

регіони (по$Р(к)$).

Додаткова площина${м}_0$відрізняється від${м}_1,...,{м}_{к}$і так зустрічає кожну з цих площин в (максимум) лінії - породжуючи не більше k ліній на площині${м}_0$. Це розташування ліній на площині${м}_0$ділить${м}_0$в максимум

${Р}_{к}=1+\left(\begin{array}{c}к\\ 1\end{array}\right)+\left(\begin{array}{c}к\\ 2\end{array}\right)$

регіони, і кожен з цих регіонів на площині${м}_0$це «розріз», де площина${м}_0$розрізає існуючий регіон на дві частини - породжуючи щонайменше

$\begin{array}{ccc}{S}_{к}+{Р}_{к}\hfill & =\hfill & [\left(\genfrac{}{}{0ex}{}{к}{0}\right)+\left(\genfrac{}{}{0ex}{}{к}{1}\right)+\left(\genfrac{}{}{0ex}{}{к}{2}\right)+\left(\genfrac{}{}{0ex}{}{к}{3}\right)]+[1+\left(\genfrac{}{}{0ex}{}{к}{1}\right)+\left(\genfrac{}{}{0ex}{}{к}{2}\right)]\hfill \\ \hfill & =\hfill & \left(\genfrac{}{}{0ex}{}{к+1}{0}\right)+\left(\genfrac{}{}{0ex}{}{к+1}{1}\right)+\left(\genfrac{}{}{0ex}{}{к+1}{2}\right)+\left(\genfrac{}{}{0ex}{}{к+1}{3}\right)\hfill \\ \hfill & =\hfill & S_{к+1}\hfill \end{array}$

регіони взагалі. (Тут немає ніякої алгебри: потрібно лише використовувати умову трикутника Паскаля.)

Звідси$Р(к+1)$вірно, коли$Р(к)$це правда.

Звідси$Р(п)$вірно для всіх$п\ge 0$.

258. Зверніть увагу, що, враховуючи розсічення квадрата на k квадратів, ми завжди можемо розрізати один квадрат на чотири чверті (по лініях через центр і паралельно сторонам), і так створити розсічення з$к+3$квадратів.

Нехай$Р(п)$бути твердженням:

«Будь-який заданий квадрат можна розрізати на m (не обов'язково конгруентних) менших квадратів, для кожного m,$6\le м\le п$».

• Нехай$п=6$. Задано будь-який квадрат сторони s (скажімо). Ми можемо вирізати квадрат з боку$\frac{}{}$2s3з одного кута, залишаючи Г-подібну смугу ширини$\frac{s}{3}$, які ми можемо потім розрізати на 5 менших квадратів, кожен зі сторін$\frac{s}{3}$. Звідси$Р(6)$це правда.

Нехай$п=7$. Враховуючи будь-який квадрат, ми можемо розділити квадрат спочатку на чотири чверті; потім розділити один з цих менших квадратів на чотири чверті, щоб отримати розсічення на 7 менших квадратів. Звідси$Р(7)$це правда.

Нехай$п=8$. Задано квадрат сторони s (скажімо). Ми можемо вирізати квадрат з боку$\frac{}{}$3s4з одного кута, залишаючи Г-подібну смугу ширини$\frac{s}{4}$, які ми можемо потім розрізати на 7 менших квадратів, кожна зі сторін$\frac{s}{4}$. Звідси$Р(8)$це правда.

• Припустимо, що$Р(к)$вірно для деяких$к\ge 8$.

Тоді$к-2\ge 6$, тому будь-який заданий квадрат може бути розсічений на$к-2$менші квадрати (по$Р(к)$). Прийняття цього розтину і поділ одного з менших квадратів на чотири чверті дає розсічення початкового квадрата на$к-2+3$квадратів. Звідси$Р(к+1)$це правда.

Звідси$Р(п)$вірно для всіх$п\ge 6$.

259. Нехай$Р(п)$бути твердженням:

«Будь-яке дерево з n вершинами має точно$п-1$краю».

• Дерево з 1 вершиною - це просто вершина з 0 ребрами (оскільки будь-яке ребро повинно бути петлею, а потім створить цикл). Звідси$Р(1)$це правда.

• Припустимо, що$Р(к)$вірно для деяких$к\ge 1$.

Розглянемо довільне дерево T з$к+1$вершин.

[Ідея: Нам потрібно знайти спосіб зменшення T до дерева${Т}^{\prime }$з k вершин. Це говорить про «видалення кінцевої вершини». Тому ми повинні спочатку довести, що «будь-яке дерево T має кінцеву вершину».]

Визначення Кількість ребер, що впадають із заданою вершиною v, називається валентністю v.

Лема Нехай S буде кінцевим деревом з$s>1$вершин. Тоді S має вершину валентності 1 — тобто «кінцеву вершину».

Доказ Виберіть будь-яку вершину$v_0$. Тоді$v_0$повинні бути з'єднані з рештою дерева, тому$v_0$має валентність не менше 1.

Якщо$v_0$це «кінцева вершина», то зупинка; якщо немає, то вибираємо вершину$v_1$яка примикає до$v_0$.

Якщо$v_1$це «кінцева вершина», потім зупинка; якщо ні, виберіть вершину$v_2\ne v_0$яка примикає до$v_1$.

Якщо$v_2$це «кінцева вершина», потім зупинка; якщо ні, виберіть вершину$v_3\ne v_1$яка примикає до$v_2$.

Продовжуйте таким чином.

Всі вершини$v_0,v_1,v_2,v_3,...$повинен бути різним (так як будь-який повтор$v_{м}=v_{п}$із$м<п$визначив би цикл

$$v_{м},v_{м+1},v_{м+2},...,v_{п-1},v_{п}=v_{м}$$

в дереві S). Оскільки ми знаємо, що дерево є кінцевим (має точно s вершини), процес повинен завершитися на певному етапі. кінцева вершина$v_{е}$тоді є «кінцевою вершиною», валентності 1.

Якщо ми застосуємо лему до нашого довільного дерева Т з$к+1$вершин, ми можемо вибрати «кінцеву вершину» v і видалити як її, так і ребро e, що падає з нею, щоб отримати дерево${Т}^{\prime }$мають k вершин. За$Р(к)$ми знаємо, що${Т}^{\prime }$має саме$к-1$краю, тому, коли ми відновлюємо край е, ми бачимо, що T має точно$(к-1)+1$краю, так$Р(к+1)$це правда.

Звідси$Р(п)$вірно для всіх$п\ge 1$.

260.

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

(а) (i) Правильний тетраедр.

(ii) Квадратна піраміда з вершиною на Північному полюсі.

(b) Якщо сферичний багатогранник має V вершин, E ребер і F граней, то

$$V-Е+F=2.$$

Тепер кожне ребро має рівно дві кінцеві вершини, так$2Е$підраховує точну кількість впорядкованих пар (v, e), де e - ребро, а v - вершина «падаюча з e».

З іншого боку, у сферичному багатограннику кожна вершина v має валентність щонайменше 3; тому кожна вершина v зустрічається щонайменше в 3 парах (v, e) такого роду. Звідси$2Е\ge 3V$.

Таким же чином кожне ребро е лежить на кордоні рівно 2 граней, так$2Е$підраховує точну кількість впорядкованих пар (f, e), де e - ребро грані f.

З іншого боку, у сферичному багатограннику кожна грань f має щонайменше 3 ребра; тому кожна грань f зустрічається принаймні в 3 парах (f, e) такого роду. Звідси$2Е\ge 3F$.

Якщо$Е=7$, потім$14\ge 3V$, і$14\ge 3F$; Тепер V і F є цілими числами, так$V\le 4$і$F\le 4$. Звідси$V+F\le 8$. Проте$V+F=Е+2=9$. Це протиріччя показує, що такого багатогранника не існує.

(c) За допомогою індукції ми показуємо, як побудувати певні «сферичні» багатогранники, щонайменше з однією нетрикутною гранню. Нехай$Р(п)$бути твердженням:

«Існує сферичний багатогранник з щонайменше однією нетрикутною гранню та з e краями для кожного$е,$ $8\le е\le п$».

• Ми знаємо, що існує такий сферичний багатогранник з$п=6$ребра — а саме правильний тетраедр (з чотирма гранями, які є рівносторонніми трикутниками).

Ми знаємо, що немає такого багатогранника з$п=7$краю (по частині (б)).

Коли$п=8$, немає сферичного багатогранника з$п=8$ребра і всі грані трикутні (так як ми б тоді$16=2Е=3F$, як і в частині (б)). Однак існує сферичний багатогранник з$п=8$ребра і лише одна нетрикутна грань — а саме квадратна піраміда з вершиною на Північному полюсі.

Коли$п=9$, ми можемо об'єднати три точки на екваторі до Північного та Південного полюсів, щоб отримати трикутну бі-піраміду (подвійну трикутну призму), з усіма гранями трикутними та$п=9$краї.

Коли$п=10$, немає сферичного багатогранника з$п=10$ребра і з усіма гранями трикутники (так як нам тоді доведеться мати$20=2Е=3F$, як і в частині (b)); але існує сферичний багатогранник з$п=10$ребра і лише одна грань, яка не є рівностороннім трикутником, а саме піраміда на основі п'ятикутника з вершиною на Північному полюсі.

Це дає нам відправну точку для індуктивної конструкції. Зокрема$Р(8)$,$Р(9)$, і$Р(10)$все вірно.

• Припустимо, що$Р(к)$вірно для деяких$к\ge 10$. Єдина частина заяви$Р(к+1)$що ще належить продемонструвати - це існування відповідного багатогранника з$к+1$краї.

Так як$к\ge 10$, ми знаємо, що$к-2\ge 8$, Отже (по$Р(к)$) існує багатогранник з усіма його вершинами на одиничній сфері, максимум з однією нетрикутною гранню, а з$е=к-2$краї. Візьміть цей багатогранник і видаліть трикутну грань.$AБC$. Тепер додайте нову вершину X на сферу, внутрішню до сферичного трикутника$AБC$, і додати краю$ХA$,$ХБ$,$ХC$і три трикутні грані$$ХAБ,$$ХБC,$$ХCA, для отримання сферичного багатогранника з$е=(к-2)+3=к+1$краях, причому максимум з одним нетрикутним обличчям. Звідси$Р(к+1)$це правда.

Звідси$Р(п)$вірно для всіх$п\ge 8$.

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

Почнемо з доведення частини «тільки якщо»:

«карту можна правильно пофарбувати двома кольорами, лише якщо кожна вершина має рівну валентність».

Нехай M — це карта, яку можна правильно пофарбувати двома кольорами. Дозвольте v бути будь-якою вершиною карти M.

Краї${е}_1,{е}_2,{е}_3,...$падаючі з v утворюють частини меж послідовності областей навколо вершини v (з${е}_1$,${е}_2$межує з одним регіоном;${е}_2$,${е}_3$межує з наступною; і так далі). Оскільки ми припускаємо, що області карти M можуть бути «належним чином пофарбовані» двома кольорами, послідовність областей навколо вершини v може бути належним чином забарвлена лише двома кольорами. Отже, кольори областей навколо вершини v повинні чергуватися (скажімо, чорно-біло-чорний-...). А оскільки карта кінцева, ця послідовність повинна повернутися до початку — тому кількість таких областей у вершині v (а отже, і кількість ребер, що падають з v — тобто валентність v) має бути парним.

Тепер доведемо частину «якщо»:

«Карту можна правильно пофарбувати двома кольорами, якщо кожна вершина має рівну валентність».

Припустимо, що у нас є карта M, в якій кожна вершина має рівну валентність. Треба довести, що будь-яка така карта М може бути правильно забарвлена лише двома кольорами.

Нехай$Р(п)$бути твердженням:

«Будь-яка карта з m ребрами, у якій кожна вершина має рівну валентність, може бути правильно забарвлена двома кольорами, коли m задовольняє$1\le м\le п$,».

• Якщо$п=1$, карта, в якій кожна вершина має рівну валентність, і яка має лише одне ребро$е$, повинна складатися з однієї вершини v, з$е$як петля з$v$до$v$(так$v$має валентність 2, починаючи з краю$е$це інцидент з$v$двічі). Це створює карту з двома регіонами — «островом» всередині петлі та «морем» зовні; тож ми можемо пофарбувати «острів» чорний і «морський» білий. Звідси$Р(1)$це правда.

• Припустимо, що$Р(к)$вірно для деяких$к\ge 1.$

Велика частина змісту заяви$Р(к+1)$вже гарантуються$Р(к)$. Щоб довести, що$Р(к+1)$правда, все, що залишається довести, це те, що

будь-яка карта з точно$к+1$ребра, у яких кожна вершина має рівну валентність, можна правильно пофарбувати лише двома кольорами.

Розглянемо довільну карту M з$к+1$ребра, у яких кожна вершина має рівну валентність.

[Ідея: Нам потрібно знайти спосіб зменшення карти M до карти${М}^{\prime }$із$\le к$ребра, у яких кожна вершина все ще має рівну валентність.]

Так як$к\ge 1$, карта M має щонайменше 2 ребра. Виберіть будь-яке ребро e з M, з (скажімо) вершинами${у}_1$,${у}_2$як його кінцевих точок, так і з областями R, S по обидва боки e.

Припустимо спочатку, що${у}_1={у}_2$, Тому межа області R (скажімо) складається тільки з ребра е. Отже e - це цикл, а S - єдина область, що сусідить R. Край е сприяє 2 валентності${у}_1$; так що якщо ми видаляємо край e, ми отримаємо карту${М}^{\prime }$в якому кожна вершина знову має рівну валентність, в якій регіони R і S були об'єднані в регіон$S^{\prime }$. Так як${М}^{\prime }$має лише k країв,${М}^{\prime }$можна правильно пофарбувати лише двома кольорами. Якщо ми тепер відновити край e і область R, ми можемо дати S того ж кольору, що і$S^{\prime }$(в належному фарбуванні${М}^{\prime }$) і дати R протилежний колір$S^{\prime }$щоб отримати належне забарвлення карти M лише двома кольорами.

Отже, ми можемо припустити, що${у}_1\ne {у}_2$, так що е не є повною межею R. Потім ми можемо повільно стиснути ребро e до точки - врешті-решт зливаючи старі вершини.${у}_1$,${у}_2$разом, щоб сформувати нову вершину${у}^{\prime }$, де два нові регіони${Р}^{\prime }$,$S^{\prime }$зустрітися. Результатом є нова карта${М}^{\prime }$, в якому всі інші вершини незмінні (і так мають парну валентність), і в якій

$$\text{валентність}({у}^{\prime })=(\text{валентність}({у}_1)-1)+(\text{валентність}({у}_2)-1)$$

що теж рівне.

Звідси кожна вершина нової карти${М}^{\prime }$має рівну валентність. Більш того,${М}^{\prime }$має не більше k країв, так (по$Р(к)$) ми знаємо, що карта${М}^{\prime }$можна правильно пофарбувати лише двома кольорами. І в цьому розфарбовуванні${М}^{\prime }$, є непарна кількість змін кольору, як один йде від${Р}^{\prime }$до$S^{\prime }$через інші регіони, які зустрічаються навколо старої вершини${у}_1$М, так$S^{\prime }$отримує протилежний колір${Р}^{\prime }$. Гарантоване правильне двоколірне фарбування${М}^{\prime }$Тому поширюється назад, щоб надати належну двоколірну забарвлення оригінальної карти M. Звідси$Р(к+1)$це правда.

Звідси$Р(п)$вірно для всіх$п\ge 1$.

262. Нехай$Р(п)$бути твердженням:

«The$2^{п}$послідовності довжини n, що складаються з 0 і 1s, можуть бути розташовані в циклічному списку таким чином, щоб будь-які дві сусідні послідовності (включаючи останню і першу) відрізнялися рівно однією координатною позицією».

• Коли$п=2$, Необхідний цикл очевидний:

$$00\to 10\to 11\to 01(\to 00).$$Так$Р(2)$це правда.

• Загальна конструкція, мабуть, найкраще проілюстрована спочатку показуючи, як$Р(2)$призводить до$Р(3)$.

Вищевказаний цикл для послідовностей довжини 2 породжує два неспільних циклів для послідовностей довжиною 3:

— спочатку додавши третю координату «0»:

$$000\to 100\to 110\to 010(\to 000)$$

— потім, додавши третю координату «1»:

$$001\to 101\to 111\to 011(\to 001).$$

Тепер усуньте остаточне приєднання в кожному циклі ($010\to 000$і$011\to 001$) і замість цього зв'язати два цикли разом, спочатку змінюючи порядок першого циклу, а потім вставляючи приєднання$000\to 001$і$011\to 010$сформувати єдиний цикл.

Загалом, припустимо, що$Р(к)$вірно для деяких$к\ge 1$. Потім ми будуємо єдиний цикл для$2^{к+1}$послідовності довжини$к+1$наступним чином:

Візьміть цикл$2^{к}$послідовності довжини k гарантовані$Р(к)$, і утворюють два неспільних циклів довжини$2^{к}$

• спочатку додаючи остаточну координату «0»

• потім шляхом додавання кінцевої координати «1».

Потім зв'яжіть два цикли в єдиний цикл довжини$2^{к+1}$, усунувши завершальний крок

$$v_1{v}_2\cdots v_{к}0\to 00\cdots 00$$в першому циклі, і$v_1{v}_2\cdots v_{к}1\to 00\cdots 01$

у другому циклі, повертаючи перший цикл, і вставляючи з'єднання

$$00\cdots 00\to 00\cdots 01\text{і}{v}_1{v}_2\cdots v_{к}1\to v_1{v}_2\cdots v_{к}0$$

виробляти єдиний цикл необхідного виду, об'єднавши всі$2^{к+1}$послідовності довжини$к+1$. Звідси$Р(к+1)$це правда.

Звідси$Р(п)$вірно для всіх$п\ge 2$.

Примітка: Значення того, що ми називаємо кодами Грея, було підкреслено в патенті 1953 року інженером Френком Греєм (1887-1969) - де їх називали відображеними двійковими кодами (оскільки найважливіший крок у їх побудові вище передбачає прийняття двох копій попередніх циклів, реверсування одного з циклів, а потім вироблення половини необхідного циклу шляхом обходу першого примірника перед поверненням назад уздовж другого примірника). Їх найосновніше використання полягає в повторному кодуванні звичайної бінарної послідовності підрахунку.

$$1\to 10\to 11\to 100\to 101\to 110\to 111\to 1000\to 1001\to 1010\to \cdots ,$$

де один крок може призвести до необхідності змінювати довільно багато двійкових цифр (наприклад, крок з$3=\text{«}11$» до$4=\text{«}100$» змінює 3 цифри, а крок від$7=\text{«}111$» до$8=$«1000» змінює 4 цифри і т.д.) — вимога, неефективна в плані електронного «перемикання», і яка збільшує ймовірність помилок. На відміну від цього, послідовність кодів Грея змінює одну двійкову цифру на кожному кроці. Однак фізична енергія, яка зберігається за рахунок зменшення кількості «перемикання» в схемотехніці, відповідає зростанню потреби в незнайомих математичних формулах, які переосмислюють кожен вектор в коді Грея як звичайне ціле число в послідовності підрахунку, до якої він відповідає.

263.

(а) Вся конструкція є індуктивною (кожна мітка походить від попередньої етикетки). Так нехай$Р(п)$бути твердженням:

«якщо$$ЧCF(р,s)=1і$2\le р+s\le п$, то позитивний раціональний$\frac{р}{s}$відбувається один раз і лише один раз як мітка, і це відбувається в найнижчі терміни».

• За конструкцією кореню дається мітка$\genfrac{}{}{0.1ex}{}{1}{1}$, так$\genfrac{}{}{0.1ex}{}{1}{1}$відбувається. І це не може повторитися, оскільки чисельник і знаменник кожної батьківської вершини обидва позитивні, ні i, ні j ніколи не можуть бути 0. Звідси$Р(2)$це правда.

Зверніть увагу, що основна конструкція:

«якщо$\frac{я}{j}$є «батьківською» вершиною, тоді ми позначимо його `лівий нащадк' як$\frac{я}{я+j}$, і його `правий нащадка'$\frac{я+j}{j}$»

гарантує, що, оскільки ми починаємо з маркування кореня позитивним раціональним$\genfrac{}{}{0.1ex}{}{1}{1}$, всі наступні `нащадки' є позитивними.

Більш того, якщо будь-який «нащадок» раптом виявився не «в найнижчих вираженнях», то або

—$$ЧCF(я,я+j)>1, в якому випадку$$ЧCF(я,я+j)=ЧCF(я,j), так$$ЧCF(я,j)>1на попередньому етапі; або

—$$ЧCF(я+j,j)>1, в якому випадку$$ЧCF(я+j,j)=ЧCF(я,j), так$$ЧCF(я,j)>1на попередньому етапі.

Так як ми починаємо з маркування кореня$\genfrac{}{}{0.1ex}{}{1}{1}$, де$$ЧCF(1,1)=1, Звідси випливає, що всі наступні мітки є позитивними раціональними в найнижчих вираженнях.

• Припустимо, що$Р(к)$вірно з деяких$к\ge 2$.

Більшість частин заяви$Р(к+1)$гарантуються$Р(к)$. Щоб показати, що$Р(к+1)$правда, залишається розглянути випадки, коли$$ЧCF(р,s)=1і$р+s=к+1$($\ge 3$). Або (i)$р>s$, або (ii)$s>р$.

(i) Припустимо, що$р>s$. Тоді$\frac{р}{s}$виникає в цій (повністю скасованій) формі тільки як прямий (правий) нащадок$\frac{р-s}{s}$. Так$\frac{р}{s}$відбувається. Більше того, кожна етикетка зустрічається в найнижчих показниках, тому$\frac{р}{s}$не може повторитися.

(ii) Припустимо, що$s>р$. Тоді$\frac{р}{s}$виникає в цій (повністю скасованій) формі тільки як прямий (лівий) нащадок$\frac{р}{s-р}$. Так$\frac{р}{s}$відбувається. Більше того, кожна етикетка зустрічається в найнижчих показниках, тому$\frac{р}{s}$не може повторитися.

Звідси$Р(к+1)$це правда.

Звідси$Р(п)$вірно для всіх$п\ge 2$.

(b) Той факт, що мітки симетричні зліва вправо, також є індуктивним явищем. Відзначимо, що один повністю «ліво-правий симетричний» мітка, а саме$\genfrac{}{}{0.1ex}{}{1}{1}$, відбувається в єдиному повністю «ліво-правому симетричному» положенні — а саме в корені.

Всі інші мітки зустрічаються відповідними парами:$\frac{р}{s}$і$\frac{s}{р}$, де ми можемо припустити, що$р>s$. Той факт, що вони зустрічаються як мітки «ліво-правих симетричних» вершин, випливає з того, що

$\frac{р}{s}$є `правим нащадком' з$\frac{р-s}{s}$і

$\frac{s}{р}$є `лівим нащадком' з$\frac{s}{р-s}$.

Отже, якщо ми знаємо, що раніше зворотна пара зворотна пара$\frac{р-s}{s}$і$\frac{s}{р-s}$виникають у вигляді міток симетрично розташованих вершин, тоді випливає, що те ж саме стосується і нащадної зворотної пари$\frac{р}{s}$і$\frac{s}{р}$. Ми залишаємо читачеві виписати доказ шляхом індукції — наприклад, за допомогою заяви

»$Р(п)$: якщо$р,s>0$, і$2\le р+s\le п$, то зворотна пара$\frac{р}{s}$,$\frac{s}{р}$відбуваються як мітки вершин на одному рівні нижче кореня, причому дві мічені вершини є дзеркальними зображеннями один одного про вертикальне дзеркало через кореневу вершину».

264. Інтервали в цій задачі можуть бути будь-якого роду (включаючи кінцеві або нескінченні). Кожен інтервал має дві «кінцеві точки», які є або звичайними дійсними числами, або$\pm \infty$(Що означає, що інтервал сходить до нескінченності в одному або обох напрямках).

Нехай$Р(п)$бути твердженням:

«якщо колекція з n інтервалів на осі x має властивість, що будь-які два інтервали перекриваються в інтервалі (можливо нульової довжини — тобто точка), то перетин усіх інтервалів у колекції є непорожнім інтервалом».

Коли$п=2$, гіпотеза$Р(2)$це те ж саме, що і висновок. Так$Р(2)$це правда.

Припустимо, що$Р(к)$вірно для деяких$к\ge 2$. Ми прагнемо довести, що$Р(к+1)$це правда.

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

Серед$к+1$інтервали, розглянемо спочатку ті з найбільшою правою кінцевою точкою. Якщо такий інтервал всього один, позначте його${Я}_0$; якщо існує більше одного інтервалу з однаковою найбільшою правою кінцевою точкою, нехай${Я}_0$бути інтервалом серед тих, у кого найбільша права кінцева точка, яка має найбільшу ліву кінцеву точку. У будь-якому випадку ставлять${Я}_0$осторонь на даний момент, залишивши колекцію S з k інтервалів з необхідною властивістю.

За$Р(к)$ми знаємо, що інтервали в колекції S перетинаються в непорожньому інтервалі I, з лівою кінцевою точкою a і правою кінцевою точкою b (скажімо).

Ми повинні показати, що перехрестя$Я\cap {Я}_0$не порожній.

Наступний доказ працює, якщо кінцева точка b включена в інтервал I. Невелике регулювання, необхідне, якщо b не включається в інтервал I, залишається читачеві.

Так як права кінцева точка${Я}_0$є максимально можливим, і оскільки точки між a і b належать всім інтервалам S, ми можемо бути впевнені, що права кінцева точка${Я}_0$є$\ge б$.

Більш того, для кожного пункту$х>б$, ми знаємо, що повинен бути певний інтервал${Я}_{х}$в колекції S, яка не розтягується так далеко вправо, як х. Так як, за гіпотезою, перетин${Я}_0\cap {Я}_{х}$не порожній, ліва кінцева точка${Я}_0$лежить ліворуч від кожної такої точки х, так${Я}_0$повинен перекривати інтервал I, звідки випливає, що$Я\cap {Я}_0$є непорожнім інтервалом, якщо потрібно.

Звідси$Р(к+1)$це правда.

Звідси$Р(п)$вірно для всіх$п\ge 2$.

265. Якщо поекспериментувати трохи, повинно з'ясуватися.

• що якщо бак${Т}_2$містить більше, ніж бак${Т}_1$, потім зв'язуючи танк Т${Т}_2$призводить до кращого негайного результату (тобто більшої кількості в резервуарі T), ніж зв'язування T з${Т}_1$;

• що якщо на певному етапі послідовності зв'язування бак Т містить проміжну кількість літрів, і збирається послідовно зв'язатися з резервуаром, що містить b літрів, а потім з резервуаром, що містить c літрів, ця впорядкована пара змін змінює кількість в Танк Т до$\frac{a+б+}{}$2c4літрів; тому для кращого кінцевого результату ми завжди повинні вибирати послідовність так, щоб$б<c$;

• після того, як кран, що зв'язує бак T з іншим резервуаром, був відкритий, щоб два рівні стали рівними, немає ніякої користі від відкриття крана, що зв'язує ці два резервуари, коли-небудь знову, тому бак T повинен бути пов'язаний один з одним резервуаром максимум один раз.

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

Для доказу шляхом індукції, нехай$Р(п)$бути твердженням:

«дано n танків, що містять$a_1,a_2,a_3,...,a_{п}$літрів відповідно, де

$a_1<a_2<a_3<...<a_{п},$

якщо T - резервуар, що містить найменшу кількість$a_1$літрів, то оптимальна послідовність для зв'язування іншого$п-1$резервуари до бака Т (оптимально в тому сенсі, що він передає максимальну кількість води в бак Т) - це послідовність, яка послідовно пов'язує Т з іншими резервуарами в порядку збільшення їх початкового вмісту».

• Коли$п=2$, Існує лише одна можлива послідовність, яка є описуваною, тому$Р(2)$це правда.

• Припустимо, що$Р(к)$вірно для деяких$к\ge 2$, і розглянути невідому колекцію$к+1$цистерни, що містять$a_1,a_2,a_3,...,a_{к+1}$літрів відповідно, де

$$a_1<a_2<a_3<...<a_{к+1},$$

і де T - резервуар, який спочатку містить$a_1$літрів.

Припустимо, що в оптимальній послідовності k послідовних приєднань до інших k резервуарів (тобто, що передає найбільшу можливу кількість води в бак Т) послідовність з'єднань полягає в тому, щоб приєднатися T спочатку до резервуару${Т}_2$, потім до танку${Т}_3$, і так далі, аж до бака${Т}_{к+1}$(де танк${Т}_{м}$не обов'язково резервуар, що містить$a_{м}$літрів). Зараз є дві можливості: або

(i)${Т}_{к+1}$є резервуаром, що містить$a_{к+1}$літрів, або

(ii)${Т}_{к+1}$містить менше$a_{к+1}$літрів.

(i) Припустимо, танк${Т}_{к+1}$є резервуаром, що містить$a_{к+1}$літрів. Тоді перший$к-1$приєднується до k танків, що містять$a_1,a_2,a_3,...,a_{к}$літрів. І ми знаємо (за найпершою точкою кулі вище), що для того, щоб максимізувати остаточну кількість в танку Т, кількість в танку T після зв'язування його з танком${Т}_{к}$повинен бути «настільки великим, наскільки це можливо». Отже, по$Р(к)$, перший$к-1$приєднується до посилання T послідовно до інших резервуарів у порядку збільшення їх вмісту - перш ніж остаточно зв'язуватися з резервуаром, що містить$a_{к+1}$літрів. Звідси висновок$Р(к+1)$тримає.

(ii) Тепер припустимо, що танк${Т}_{к+1}$містить$a_{м}<a_{к+1}$літрів.

До найпершої точки кулі, щоб гарантувати оптимальний загальний результат остаточного зв'язку з танком${Т}_{к+1}$кількість в танку T після того, як він був пов'язаний з танком${Т}_{к}$повинен бути «настільки великим, наскільки це можливо» (враховуючи суми в резервуарах$Т,{Т}_2,{Т}_3,...,{Т}_{к}$). Звідси заяву$Р(к)$застосовується до початкової послідовності$к-1$приєднується (від T до${Т}_2$, потім${Т}_3$, і так далі аж до${Т}_{к}$), і гарантує, що ці резервуари повинні бути в порядку збільшення їх початкового вмісту. Зокрема, останній танк в такій послідовності,${Т}_{к}$, повинен бути той, що містить$a_{к+1}$літрів. Але якщо ми позначимо літрами кількість в резервуарі Т безпосередньо перед тим, як він зв'язується з танком.${Т}_{к}$(містить$a_{к+1}$л), потім останні два зв'язки, з$б=a_{к+1}$і$c=a_{м}$суперечити другій точці кулі на початку цього рішення. Отже, випадок (ii) не може відбутися.

Звідси$Р(к+1)$це правда.

Звідси$Р(п)$вірно для всіх$п\ge 2$.

266.

Примітка: Як і всі практичні завдання, ця потребує елемента початкового «моделювання» для того, щоб ситуація піддавалася математичному аналізу.

`Залишок 'чіпляється за поверхні; тому загальна кількість `залишку' буде залежати від

(а) в'язкість хімічної речовини (наскільки «товста» або «липка»), і

(б) загальна площа поверхні внутрішньої частини колби.

Оскільки нам не дають інформації про кількості, ми можемо зафіксувати кількість залишку, що залишилася в «порожній» колбі, на «1 одиниці», а кількість розчинника в іншій колбі як «s одиниці».

Якщо додати розчинник, то отримаємо комбіновану кількість$1+s$одиниць розчину - який ми можемо вважати (після відповідного струшування) однорідним, з хімічною концентрацією, зменшеною до «1 частини в$1+s$».

Перший виклик моделювання виникає, коли ми намагаємося зробити математичний сенс того, що залишається на кожному етапі після спорожнення колби. Площа внутрішньої поверхні колби, до якої може прилипати будь-який розведений залишок, фіксується. Якщо ми допустимо помилку, вважаючи оригінальну хімічну речовину «товстим і липким», а розчинник - «тонким», то в'язкість розведеного залишку зміниться відносно оригіналу і буде робити це способами, які ми не можемо знати. Отже, єдине розумне припущення (яке може бути дійсним або не може бути дійсним в конкретному випадку) полягає в тому, щоб припустити, що в'язкість вихідної хімічної речовини приблизно така ж, як в'язкість суміші хіміко-розчинника. Це потім говорить про те, що при спорожненні розведеної суміші приблизно однакова кількість (1 одиниця) розведеної суміші залишиться прилипати до стінок колби. Так у нас залишиться 1 одиниця залишку, з концентрацією$\frac{1}{1+s}$. Зокрема, якщо$s=1$, використовуючи весь розчинник одночасно, зменшує кількість токсичних хімічних залишків до$\genfrac{}{}{0.1ex}{}{1}{2}$одиниця (з іншим$\genfrac{}{}{0.1ex}{}{1}{2}$одиниця, що складається з розчинника).

Але що робити, якщо спочатку використати лише половину розчинника, спорожнити колбу, а потім використовувати іншу половину? Додавання$\frac{s}{2}$одиниць розчинника (і ретельно струшуючи) виробляє$1+\frac{s}{2}$одиниць однорідної суміші, з концентрацією 1 частина на$1+\frac{s}{2}$. Коли ми спорожняємо колбу, ми очікуємо приблизно 1 одиницю залишку з такою концентрацією - так що просто$\frac{2}{2+s}$одиниць хімічної, з$\frac{s}{2+s}$одиниць розчинника.

Якщо ми потім додамо інший$\frac{s}{2}$одиниць розчинника, це виробляє$1+\frac{s}{2}$одиниць суміші з концентрацією 1 частина на${\left(1+\frac{s}{2}\right)}^2$. Коли ми спорожняємо колбу, ми очікуємо приблизно 1 одиницю залишку з концентрацією 1 частина на${\left(1+\frac{s}{2}\right)}^2$. Зокрема, якщо$s=1$, ця стратегія зменшує кількість токсичної хімічної речовини в 1 одиниці залишку до$\genfrac{}{}{0.1ex}{}{4}{9}$одиниць. Так як$\frac{4}{9}<\frac{1}{2}$ця двоетапна стратегія здається більш ефективною, ніж попередня стратегія «все відразу».

Припустимо, що ми використовуємо чотириетапну стратегію — використовуючи спочатку одну чверть платоспроможника, потім ще чверть і так далі. Потім ми висаджуємо приблизно 1 одиницю залишку з концентрацією 1 частина на${\left(1+\frac{s}{4}\right)}^4$. Зокрема, якщо$s=1$, висаджуємо з кількістю токсичної хімічної речовини в 1 одиницю залишку, рівну$\genfrac{}{}{0.1ex}{}{256}{625}$одиниць, і$\frac{256}{625}<\frac{4}{9}$. Більш загально, якщо ми використовуємо$\left(\frac{1}{п}\right)$го розчинника, в n раз, кінцева кількість токсичної хімічної речовини в 1 одиниці залишку дорівнює${\left(1+\frac{s}{п}\right)}^{-п}$. І як n стає все більше і більше, цей вираз стає все ближче і ближче до${е}^{-s}$. Зокрема, коли$s=1$, ця стратегія залишає остаточну кількість хімічної речовини в 1 одиниці залишку приблизно рівною$\frac{1}{е}=0.367879\cdots$.

Примітка: Ситуація тут аналогічна тій, з якою стикається дизайнер пральної машини, який бажає видалити сліди миючого засобу з речей, які були випрані, не використовуючи необмежену кількість води. Ідея мати «фіксовану кількість розчинника» відповідає меті «водоефективного» промивання. Однак цикл пральної машини, або програма, явно не може повторювати полоскання нескінченно довго (як це було б потрібно в обмеженому випадку вище).

267.

(i) Якщо$\sqrt{2}=\frac{м}{п}$, потім

$$$$2п2=м2

Звідси m ² рівний.

Звідси випливає, що m повинен бути рівним.

Примітка: Це факт, що, якщо$м=2к$рівний, тоді${м}^2=$4к2також рівний. Але це тут абсолютно не має значення. Для того щоб зробити висновок, що «m повинен бути парним», ми повинні довести:

Претензія m не може бути непарною.

Доказ Припустимо, m непарне.

$\therefore$ $м=2к+1$для деякого цілого числа k.

Але потім

$${м}^2={(2к+1)}^2=4{к}^2+4к+1$$

буде непарним, всупереч «m ² повинен бути парним».

Отже m не може бути непарним.

(ii) Оскільки m парний, ми можемо написати$м=2{м}^{\prime }$для деякого цілого числа${м}^{\prime }$. Рівняння (*) в (i) вище тоді стає${п}^2=2{({м}^{\prime })}^2$, Таким чином, n ² рівний. Отже, як і в Примітці вище, п повинен бути парним, так що ми можемо написати$п=2{п}^{\prime }$для деякого цілого числа${п}^{\prime }$.

(iii) Якщо$\sqrt{2}=\frac{м}{п}$, потім$м=2{м}^{\prime }$, і$п=2{п}^{\prime }$обидва рівні.

$\therefore$ $\sqrt{2}=\frac{м}{п}=\frac{2{м}^{\prime }}{2{п}^{\prime }}=\frac{{м}^{\prime }}{{п}^{\prime }}$.

Таким же чином випливає, що${м}^{\prime }$і${п}^{\prime }$обидва рівні, тому ми можемо написати${м}^{\prime }=2м\text{'}\text{'}$,${п}^{\prime }=2п\text{'}\text{'}$для деяких цілих чисел$м\text{'}\text{'}$,$п\text{'}\text{'}$.

Продовжуючи таким чином, потім виробляє нескінченну спадну послідовність позитивних знаменників.

$$п>{п}^{\prime }>п\text{'}\text{'}>...>0.$$

всупереч тому, що така послідовність може мати довжину не більше$п-1$(або насправді, не більше$1+$журнал2п).

268.

(i) Якщо$a<б$і$c>0$, потім$ac<бc$.

Якщо$0<\sqrt{2}\le 1$, потім (множимо на$\sqrt{2}$) випливає, що$2\le \sqrt{2}\le 1$, Що є помилковим. Звідси$\sqrt{2}>1$.

Тепер ми знаємо, що$1<\sqrt{2}$, так множивши на$\sqrt{2}$дає$\sqrt{2}<2$. Звідси$1<\sqrt{2}<2$. Зокрема,$\sqrt{2}$не можна записати як дріб зі знаменником 1, тому$Р(1)$це правда.

(ii) Припустимо$Р(к)$вірно для деяких$к\ge 1$. Велика частина заяви$Р(к+1)$мається на увазі$Р(к)$: все, що залишається довести, це те, що$\sqrt{2}$не можна записати як дріб із знаменником$п=к+1$.

Припустимо$\sqrt{2}=\frac{м}{п}$, де$п=к+1$і m - натуральні числа.

Тоді$м=2{м}^{\prime }$і$п=2{п}^{\prime }$обидва рівні (як у задачі 267).

Так$\sqrt{2}=\frac{{м}^{\prime }}{{п}^{\prime }}$із${п}^{\prime }\le к$, всупереч$Р(к)$. Звідси$Р(к+1)$тримає.

$\therefore$ $Р(п)$вірно для всіх$п\ge 1$.

269.

(а) Припустимо, що S не порожній. Тоді за принципом найменших елементів множина S повинна містити найменший елемент k: тобто найменше ціле число k, якого немає у множині T. Тоді$к\ne 1$(Оскільки нам кажуть, що T містить ціле число 1). Звідси$к>1$.

Тому$к-1$є натуральним числом, меншим за k. Так$к-1$не є елементом S, а отже, повинен бути елементом T. Але якщо$к-1$є елементом T, тоді нам кажуть, що$(к-1)+1$також повинен бути членом Т. Це протиріччя показує, що S має бути порожнім, тому T містить всі натуральні числа.

(b) Припустимо, що T не має найменшого елемента. Очевидно, що 1 не належить до множини T (або це був би найменший елемент T). Звідси 1 повинен бути елементом множини S.

Тепер припустимо, що для деяких$к\ge 1$, всі натуральні числа$1,2,3,...,к$є елементами S, але$к+1$не є елементом S. Тоді$к+1$був би елементом T, і був би найменшим елементом T, що неможливо. Звідси S має властивість, що

«всякий раз$к\ge 1$є елементом S, ми можемо бути впевнені, що$к+1$також є елементом S».

Принцип математичної індукції гарантує, що ці два спостереження (що 1 є елементом S, і що всякий раз, коли k є елементом S,$к+1$) мають на увазі, що S містить всі натуральні числа, так що множина T повинна бути порожньою — всупереч припущенню.

Звідси T повинен мати найменший елемент.

270.

(i) Трикутник$O{Р}^{\prime }{Q}^{\prime }$являє собою прямокутний трикутник з$\angle {Р}^{\prime }O{Q}^{\prime }={45}^{°}$. Звідси два базових кута (при О і в$Q^{\prime }$) рівні, тому трикутник рівнобедрений:$\underset{\_}{{Р}^{\prime }{Q}^{\prime }}=\underset{\_}{{Р}^{\prime }O}$.

(ii) Трикутники$Q{Q}^{\prime }{Р}^{\prime }$і$Q{Q}^{\prime }Р$конгруентні по RHS (так як вони поділяють гіпотенузу$\underset{\_}{Q{Q}^{\prime }}$, і мають рівні сторони ($\underset{\_}{Q{Р}^{\prime }}=\underset{\_}{QР}=\underset{\_}{QР}$). Звідси$\underset{\_}{Q^{\prime }{Р}^{\prime }}=\underset{\_}{Q^{\prime }Р}$.

(iii) Якщо$\underset{\_}{OQ}:\underset{\_}{OР}=м:п$, ми можемо вибрати одиницю так, щоб$\underset{\_}{OQ}$має довжину m одиниць і$\underset{\_}{OР}$має довжину n одиниць. Тоді

$$\underset{\_}{O{Р}^{\prime }}=\underset{\_}{OQ}-\underset{\_}{Q{Р}^{\prime }}=\underset{\_}{OQ}-\underset{\_}{QР}=м-п,$$

і

$$\underset{\_}{O{Q}^{\prime }}=\underset{\_}{OР}-\underset{\_}{Q^{\prime }Р}=\underset{\_}{OР}-\underset{\_}{Q^{\prime }{Р}^{\prime }}=\underset{\_}{OР}-\underset{\_}{O{Р}^{\prime }}=п-(м-п).$$

(iv)$\underset{\_}{OР}<\underset{\_}{OQ}<\underset{\_}{OР}+\underset{\_}{РQ}$, так$п<м<п+п$. Звідси$0<м-п<п$, і$0<2п-м$.

(v) У квадраті$O{Р}^{\prime }{Q}^{\prime }{Р}^{\prime }$, Співвідношення «діагональ: сторона»$=\underset{\_}{O{Q}^{\prime }}:\underset{\_}{O{Р}^{\prime }}=\sqrt{2}:1$. Якщо співвідношення$\underset{\_}{OQ}:\underset{\_}{OР}=м:п$, з m, n натуральних чисел, то конструкція тут замінює натуральні числа m, n на менші натуральні$2п-м$і$м-п$, з$м-п<п$. І процес може повторюватися нескінченно довго, щоб генерувати нескінченну послідовність спадних натуральних чисел.

$$п>м-п>(2п-м)-(м-п)=3п-2м>...>0.$$

Останній, найбільш життєвий урок Заратустри: «Тепер обійтися без мене».

Джордж Штайнер (1929-)