6.2: «Математична індукція» та «наукова індукція»

Ідея «списку, який триває назавжди» виникла в послідовності повноважень 4 ще в задачі 16, де ми запитали

Виконайте дві послідовності, що виникають з послідовних ступенів 4:

• провідні цифри:

$$\begin{array}{cc}& \mathrm{4,\; 2,\; 6,\; 2,\; 1,\; 4,\; 2,\; 6,\; 2,\; 1,\; 4,...,}\hfill \end{array}$$

і

• цифри одиниць:

$$\begin{array}{cc}& \mathrm{4,\; 6,\; 4,\; 6,\; 4,\; 6,\; 4,\; 6,...,}\hfill \end{array}$$

дійсно «повторити назавжди», як вони здаються?

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

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

Доказ за допомогою математичної індукції зовсім інший. Справді, це часто вимагає розумних здогадок на попередньому етапі, щоб зробити припущення, яке дозволяє нам точно сформулювати, що саме ми повинні намагатися довести. Але це початкове припущення окремо від доказу, яке залишається строго дедуктивної конструкцією. Наприклад,

той факт, що «1»,$1+3$»,»$1+3+5$»,»$1+3+5+7$», і т.д. всі здаються послідовними квадратами дає нам уявлення про те, що, можливо, ідентичність

П (п):$1+3+5+\cdots +($2п-1)=п2
правда, для всіх$п\ge 1$.

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

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

У задачі 76 ми дали сувору конструкцію шляхом математичної індукції:

• ми вперше показали, як почати (з${р}_1=2$сказати);
• то ми показали, як, враховуючи будь-який кінцевий список різних простих чисел${р}_1,{р}_2,{р}_3,...,{р}_{к}$, завжди можна побудувати новий прайм${р}_{к+1}$(як найменше просте число ділення${П}_{к}={р}_1\times {р}_2\times {р}_3\times \cdots \times {р}_{к}+1$).

Ця конструкція була дуже ретельно сформульована, щоб бути логічно правильною.

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

$$\begin{array}{cc}& (2;)2+1=\mathbf{3};2\times 3+1=\mathbf{7};2\times 3\times 5+1=\mathbf{31};2\times 3\times 5\times 7+1=\mathbf{211};...\hfill \end{array}$$

як спосіб генерації все більшої кількості простих чисел.

Проблема 228

(а) Чи є 3, 7, 31, 211 всі прості?

(б)$2\times 3\times 5\times 7\times 11+1$прем'єр?

(c) Є$2\times 3\times 5\times 7\times 11\times 13+1$прем'єр? A

Ми вже зустрічали два чудові історичні приклади небезпеки правдоподібного візерунка - плямистість у зв'язку з проблемою 118. Там ви довели, що:

«якщо$$2п-1є простим, тоді n має бути простим».

Ви тоді показали, що$2^2-1$,$2^3-1$,$2^5-1$,$2^7-1$всі прості, але що$2^{11}-1=2047=23\times 89$не є. Це підкреслює необхідність уникати стрибків до (можливо, помилкових) висновків і ніколи не плутати твердження з його зворотним.

У цій же задачі ви показали, що:

«якщо$a^{б}+1$це бути простим і$a\ne 1$, то a має бути парним, а b має бути силою 2».

Ви тоді розглянули найпростіше сімейство таких простих кандидатів, а саме послідовність чисел Ферма.$f_{п}$:

$$\begin{array}{cc}& f_0=2^1+1=3,f_1=2^2+1=5,f_2=2^4+1=17,f_3=2^8+1=257,f_4=2^{16}+1.\hfill \end{array}$$

Виявилося, що, хоча фо,$f_0,f_1,f_2,f_3,f_4$всі прості, і хоча Ферма (1601—1665) стверджував (у листі до Марін Мерсенн (1588—1648)), що всі числа Ферма$f_{п}$є першими, нам ще належить відкрити шостий прем'єр Ферма!

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

Рівняння Пелла (Джон Пелл (1611—1685)) дає деякі драматичні приклади.

• Якщо ми оцінюємо вираз»${п}^2+1$» для$п=\mathrm{1,2}\mathrm{,\; 3},...$, ми можемо помітити, що виходи$\mathrm{2,5}\mathrm{,\; 10}\mathrm{,\; 17}\mathrm{,\; 26},...$ніколи не даруй ідеальний квадрат. І цього слід очікувати, так як наступний квадрат після${п}^2$є

$\begin{array}{cc}& {(п+1)}^2={п}^2+2п+1,\hfill \end{array}$

і це завжди більше, ніж${п}^2+1$.

• Однак, якщо ми оцінюємо»$991{п}^2+1$» для$п=\mathrm{1,\; 2,\; 3,...,}$ми можемо помітити, що виходи ніколи не включають ідеальний квадрат. Але цього разу немає очевидних причин, чому це повинно бути так - тому ми можемо передбачити, що це просто випадковість «малих» чисел. І ми повинні соромитися, щоб змінити наш погляд, хоча ця аварія триває дуже, дуже, дуже довго: найменше значення п, для якого$$991п2+1породжує ідеальний квадрат, мабуть

$\begin{array}{cc}& п=12055735790331359447442538767.\hfill \end{array}$