Математическая индукция

математична індукція

1. Повна і неповна індукція

В основі всякого математичного дослідження лежать дедуктивний і індуктивний методи. Дедуктивний метод міркувань – це міркування від загального до частинного, тобто міркування, вихідним моментом якого є загальний результат, а заключним моментом – частинний результат. У математиці застосовуємо дедуктивний метод, проводячи міркування такого типу: дана фігура – прямокутник, а в кожного прямокутника діагоналі рівні, отже, і в даного прямокутника діагоналі рівні.

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

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

4=2+2; 6=3+3; 8=5+3; 10=7+3; 12=7+5; 14=7+7; 16=11+5; 18=11+7; 20=13+7.

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

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

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

Нехай, наприклад, потрібно знайти суму перших n послідовних непарних чисел. Розглянемо окремі випадки:

1=1=12;

1+3=4=22;

1+3+5=9=32;

1+3+5+7=16=42;

1+3+5+7+9=25=52.

Після розгляду цих деяких окремих випадків напрошується наступний загальний висновок:

1+3+5+...+(2n-1)=n2,

тобто сума n перших послідовних непарних чисел дорівнює n2.

Зрозуміло, зроблене спостереження ще не може бути доказом справедливості приведеної формули. Далі ми познайомимося з методом, користаючись яким, можна довести, що ця формула вірна.

2. Помилки в індуктивних міркуваннях

Наведемо приклади того, як індуктивні міркування призводять до помилкових висновків.

1. Різниця двозначного числа і  числа, записаного тими ж цифрами, але в зворотному порядку, ділиться націло на 9. Різниця тризначного числа і числа, записаного тими ж цифрами, але в зворотному порядку, ділиться на 99. Виникає припущення про те, що різниця чотиризначного числа і числа, записаного тими ж цифрам, але в зворотному порядку, розділиться на 999. Це, однак, невірно, наприклад, 2231-1322 = 909, але 909 не поділяється на 999.

2. Розглядаючи числа виду 22 +1, французький математик П. Ферма помітив, що при n=1, 2, 3, 4 виходять прості числа. Він припустив, що всі числа такого виду – прості. Однак Л. Эйлер знайшов, що вже при n=5 це невірно: число 232+1 не є простим - воно ділиться на 641.

3. Розглянемо ще один приклад. Підставляючи в квадратний тричлен P(x)=x2+x+41 замість x натуральні числа 1, 2, 3, 4, 5, знайдемо: P(1)=43, P(2)=47, P(3)=53, P(4)=61, P(5)=71. Всі отримані значення даного тричлена є простими числами. Підставляючи замість x числа 0, -1, -2, -3, -4, одержимо: P(0)=41, P(-1)=41, P(-2)=43, P(-3)=47, P(-4)=53. Значення даного тричлена при зазначених значеннях змінної x також є простими числами. Виникає гіпотеза, що значення тричлена P(x) є простим числом при будь-якому цілому значенні x. Але висловлена гіпотеза помилкова, тому що, наприклад, P(41)=412+41+41=41· 43.

4. Знаменитий німецький математик XVII ст., один із творців вищої математики, Г.В. Лейбніц довів, що при всякому цілому додатному n число n3-n ділиться на 3, число n5-n ділиться на 5, число n7-n ділиться на 7. На підставі цього він припустив, що при всякому непарному k і будь-якому натуральному n число nk-n ділиться на k, але незабаром сам помітив, що 29-2=510 не ділиться на 9.

5. Потрібно з'ясувати, чи існує таке натуральне число n, що число виду 991n2+1 є точним квадратом. Розглядаючи часткові випадки при n = 1, 2, 3, 4, ..., ми будемо одержувати числа, що не є точними квадратами. Якби ми робили обчислення для послідовних натуральних чисел, то щораз одержували би числа, що не є точними квадратами. Цілком природно припустити, що при всіх натуральних n числа виду 991n2+1 не є точними квадратами. Однак це невірно: за допомогою обчислювальної машини було знайдено 29-значне число m таке, що число 991m2+1 виявилося точним квадратом.

Розглянуті приклади дозволяють зробити простий і в той же час важливий висновок: неповна індукція може привести до помилки. Однак важливо підкреслити, що вона іноді приводить до істини, хоча можливість помилки виключати не можна. Твердження може бути справедливим у цілому ряді окремих випадків і в той же час несправедливим узагалі.

3. Принцип математичної індукції

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

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

Нехай потрібно довести справедливість деякого твердження для будь-якого натурального числа n (наприклад, потрібно довести, що сума перших n непарних чисел дорівнює n2). Безпосередня перевірка цього твердження для кожного n неможлива, оскільки множина натуральних чисел нескінчена. Щоб довести це твердження, перевіряють спочатку його справедливість для n=1. Потім доводять, що при будь-якому натуральному значенні k зі справедливості розглянутого  твердження при n=k випливає його справедливість і при n=k+1. Тоді твердження вважається доведеним для всіх n. Справді, твердження справедливе при n=1. Але тоді воно справедливо і для наступного числа n=1+1=2. Зі справедливості твердження для n=2 його справедливість для n=2+1=3. Звідси, у свою чергу, випливає справедливість твердження для n=4 і т.д. Ясно, що зрештою ми дійдемо до будь-якого натурального числа n. Виходить, твердження вірне для будь-якого n.

Узагальнюючи сказане, сформулюємо загальний принцип.

Принцип математично ї індукції. Якщо речення А (n), що залежить від натурального числа n, істинно для n=1 з того, що воно істинно для n=k (де k - будь-яке натуральне число), випливає, що воно істинно і для наступного числа n=k+1, то А (n) істинно для будь-якого натурального числа n.

4. Узагальнення принципу математичної  індукції 

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

Якщо речення А (n) істинно при n=р і якщо А (k)ÞА (k+1)для будь-якого k³р, то А (n) істинно для будь-якого n³р.

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

5. Метод математичної індукції 

Доведення по методу математичної індукції проводитися в такий спосіб. З початку доказуване твердження перевіряється для n=1, тобто встановлюється істинність висловлення А (1). Цю частину доведення називають початком або базисом індукції. Потім йде частина доведення, що називається індукційним кроком. У цій частині доводять справедливість твердження для n=k+1 у припущенні справедливості твердження для n=k (припущення індукції), тобто доводять, що А (k)ÞА (k+1). Уперше такий спосіб запропонували Б. Паскаль і Я. Бернуллі.

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

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

6. Приклад доведення методом  математичної індукції

1. Доведіть, що число, яке складається  з 243 одиниць, ділиться на 243.

Розв’язування:

Помітимо, що 243 = 35. Спробуємо довести більш загальне твердження, що число, складене з 3n одиниць, поділяється на Зn. Виявляється, це простіше. Для n = 1 твердження вірне (111 поділяється на 3). Помітимо, що 111111111 = 111 • 1001001, і взагалі число з 3n одиниць розкладається на множники:

I ... 1  = 1 ... 1 *10...010... 01

причому, другий множник ділиться на 3 (по ознаці подільності на 3).

  Отже, у послідовності чисел 111, 111111111, ..., «3n одиниць» кожне наступне дорівнює попередньому, помноженому на число, кратне трьом. Тому, якщо 1...1  ділиться на  3n-1, то і 1...1 ділиться на 3n.

Завдання. 1. Доведіть, що довільну суму, більшу 7 коп., можна сплатити монетами вартістю в 3 коп. та в 5 коп.

2. Дійсне число х таке, що  – ціле. Доведіть, що для довільного натурального п число також ціле.