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

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

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

Термін "індукція" (induction) має латинське коріння і дослівно перекладається як "наведення". При пильному вивченні можна виділити структуру слова, саме латинську приставку - in- (позначає спрямоване дію всередину чи перебування усередині) і -duction - вступ. Слід зазначити, що є два види - повна і неповна індукції. Повну формухарактеризують висновки, зроблені виходячи з вивчення всіх предметів деякого класу.

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

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

• на першому доводиться правильність становища математичної індукції. Приклад: f = 1 індукції;
• Наступний етап будується на припущенні про правомірність становища всім натуральних чисел. Тобто f=h це припущення індукції;
• на етапі доводиться справедливість становища для числа f=h+1, виходячи з вірності становища попереднього пункту - це індукційний перехід, чи крок математичної індукції. Прикладом може бути так званий якщо падає перша кісточка в ряду (базис), то впадуть усі кісточки в ряду (перехід).

І жартома, і всерйоз

Для простоти сприйняття приклади рішення методом математичної індукції викривають форму завдань-жартів. Таким є завдання «Ввічлива черга»:

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

Яскравим прикладом методу математичної індукції є завдання «Безрозмірний рейс»:

• Потрібно довести, що у маршрутку міститься будь-яка чисельність людей. Правдиво твердження, що одна людина може розміститися всередині транспорту без утруднень (базис). Але як би не була заповнена маршрутка, 1 пасажир завжди поміститься (крок індукції).

Знайомі кола

Приклади розв'язання методом математичної індукції завдань та рівнянь трапляються досить часто. Як ілюстрацію такого підходу можна розглянути таке завдання.

Умова: на площині розміщено h кіл. Потрібно довести, що за будь-якого розташування фігур утворена ними карта може бути правильно розфарбована двома фарбами.

Рішення: при h=1 істинність твердження очевидна, тому доказ будуватиметься кількості кіл h+1.

Приймемо припущення, що твердження достовірне для будь-якої карти, а на площині задано h+1 кіл. Видаливши із загальної кількості одну з кіл, можна отримати правильно розфарбовану двома фарбами (чорною та білою) карту.

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

Приклади з натуральними числами

Нижче показано застосування методу математичної індукції.

Приклади рішення:

Довести, що за будь-якого h правильною буде рівність:

1 2 +2 2 +3 2 +…+h 2 =h(h+1)(2h+1)/6.

1. Нехай h=1, отже:

R 1 =1 2 =1(1+1)(2+1)/6=1

З цього випливає, що за h=1 твердження правильно.

2. При припущенні, що h = d, виходить рівняння:

R 1 =d 2 =d(d+1)(2d+1)/6=1

3. При припущенні, що h=d+1, виходить:

R d+1 =(d+1) (d+2) (2d+3)/6

R d+1 = 1 2 +2 2 +3 2 +…+d 2 +(d+1) 2 = d(d+1)(2d+1)/6+ (d+1) 2 =(d( d+1)(2d+1)+6(d+1) 2)/6=(d+1)(d(2d+1)+6(k+1))/6=

(d+1)(2d 2 +7d+6)/6=(d+1)(2(d+3/2)(d+2))/6=(d+1)(d+2)( 2d+3)/6.

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

Завдання

Умова: потрібен доказ того, що при будь-якому значенні h вираз 7 h -1 ділимо на 6 без залишку.

Рішення:

1. Припустимо, h=1, у разі:

R 1 =7 1 -1=6 (тобто. ділиться на 6 без залишку)

Отже, за h=1 твердження є справедливим;

2. Нехай h=d та 7 d -1 ділиться на 6 без залишку;

3. Доказом справедливості затвердження h=d+1 є формула:

R d +1 =7 d +1 -1=7∙7 d -7+6=7(7 d -1)+6

В даному випадку перший доданок ділиться на 6 за припущенням першого пункту, а другий доданок дорівнює 6. Твердження про те, що 7 h -1 ділимо на 6 без залишку при будь-якому натуральному h - справедливо.

Помилковість суджень

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

Завдання

Умова: потрібен доказ того, що будь-яка купа каміння - не є купкою.

Рішення:

1. Припустимо, h=1, у разі в купці 1 камінь і твердження вірно (базис);

2. Нехай при h=d вірно, що купа каміння - не є купкою (припущення);

3. Нехай h=d+1, з чого випливає, що при додаванні ще одного каменю безліч не буде купкою. Напрошується висновок, що припущення справедливе за всіх натуральних h.

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

Індукція та закони логіки

Історично склалося так, що завжди "крочать пліч-о-пліч". Такі наукові дисциплінияк логіка, філософія описують їх як протилежностей.

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

В Естонії – посуха, у Латвії – посуха, у Литві – посуха.

Естонія, Латвія та Литва – прибалтійські держави. В усіх прибалтійських державах посуха.

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

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

Індукція у науковому середовищі

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

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

Розрізняють два види індукції в науковому світі(у зв'язку зі способом вивчення):

1. індукція-відбір (або селекція);
2. індукція – виняток (елімінація).

Перший вид відрізняється методичним (скрупульозним) відбором зразків класу (підкласів) із різних його областей.

Приклад індукції цього виду є наступним: срібло (або солі срібла) очищає воду. Висновок ґрунтується на багаторічних спостереженнях (своєрідний відбір підтверджень та спростування - селекція).

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

Індукція та дедукція з позиції філософії

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

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

Усвідомлення неспроможності теорій Бекона та Мілля призвело вчених до дослідження імовірнісної основи індукції. Однак і тут не обійшлося без крайнощів: були спроби звести індукцію до теорії ймовірності з усіма наслідками.

Вотум довіри індукція отримує у практичному застосуванніу певних предметних областях та завдяки метричній точності індуктивної основи. Прикладом індукції та дедукції у філософії можна вважати Закон всесвітнього тяжіння. На дату відкриття закону Ньютону вдалося перевірити його з точністю 4 відсотки. А при перевірці більш ніж через двісті років правильність була підтверджена з точністю до 0,0001 відсотка, хоча перевірка велася тими ж індуктивними узагальненнями.

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

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

Застосування індукції економіки

Індукція та дедукція давно використовуються як методи дослідження економіки та прогнозування її розвитку.

Спектр використання методу індукції досить широкий: вивчення виконання прогнозних показників (прибутки, амортизація тощо) та Загальна оцінкастани підприємства; формування ефективної політикипросування підприємства з урахуванням фактів та його взаємозв'язків.

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

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

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

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

Наочний приклад індукції економіки, що відноситься до помилкових міркувань:

• прибуток компанії скоротився на 30%;
  конкуруюча компанія розширила лінійку продукції;
  більше нічого не змінилося;
• виробнича політика конкуруючої компанії спричинила скорочення прибутку на 30%;
• отже, потрібно запровадити таку ж виробничу політику.

Приклад є яскравою ілюстрацією того, як невміле використання методу індукції сприяє розоренню підприємства.

Дедукція та індукція у психології

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

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

• учень ні на що не здатний, якщо отримав двійку з математики;
• він - дурень;
• він розумний;
• я можу все;

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

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

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

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

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

Психологи, працюючи над темою дедуктивного мислення, склали список рекомендацій, покликаний допомогти людям освоїти цей метод.

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

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

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

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

Замість ув'язнення

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

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

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

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

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

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

Існує також варіація так званий принцип повної математичної індукції. Ось його строге формулювання:

Принцип повної математичної індукції також еквівалентний аксіомі індукції в аксіомах Пеано.

Приклади

Завдання.Довести, що, які б не були натуральні nта речовинне q≠ 1, виконується рівність

Доведення.Індукція з n.

База, n = 1:

Перехід: Припустимо, що

,

що і потрібно було довести.

Коментар:вірність затвердження P nу цьому доказі - те саме, що вірність рівності

Див. також

Варіації та узагальнення

Література

• Н. Я. Віленкініндукція. Комбінаторика. Посібник для вчителів. М., Просвітництво, 1976.-48 з
• Л. І. Головіна, І. М. ЯгломІндукція в геометрії, «Популярні лекції з математики», Випуск 21, Фізматгіз 1961.-100 с.
• Р. Курант, Г. РоббінсЩо таке математика? Глава I, § 2.
• І. С. СомінськийМетод математичної індукції. "Популярні лекції з математики", Випуск 3, Видавництво "Наука" 1965.-58 с.

Wikimedia Foundation. 2010 .

Дивитись що таке "Метод математичної індукції" в інших словниках:

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

Спосіб побудови теорії, наприклад в її основу кладуться деякі її положення - аксіоми або постулати, - з решти всі інші положення теорії (теореми) виводяться шляхом міркувань, званих докази. м в. Правила, до яких… … Філософська енциклопедія

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

ГЕНЕТИЧНИЙ МЕТОД- спосіб завдання змісту та сутності досліджуваного предмета не шляхом конвенції, ідеалізації або логічного висновку, а за допомогою вивчення його походження (спираючись на вивчення причин, що призвели до виникнення, механізм становлення). Широко… … Філософія науки: Словник основних термінів

Спосіб побудови наукової теорії, у якому її основу кладуться деякі вихідні становища (судження) аксіоми (Див. Аксіома), чи Постулати, у тому числі й інші твердження цієї науки (теореми) повинні виводитися… Велика Радянська Енциклопедія

аксіоматичний метод- АКСІОМАТИЧНИЙ МЕТОД (від грец. axioma) прийнятий стан спосіб побудови наукової теорії, при якому в доказах користуються лише аксіомами, постулатами і раніше виведеними з них твердженнями. Вперше яскраво продемонстровано… Енциклопедія епістемології та філософії науки

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

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

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

Бібліографічний опис:Баданін А. С., Сізова М. Ю. Застосування методу математичної індукції до розв'язання задач на подільність натуральних чисел // Юний вчений. 2015. №2. С. 84-86..02.2019).

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

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

Метод математичної індукції ми бачимо теоретично чисел. На зорі теорії чисел математики відкрили багато фактів індуктивним шляхом: Л. Ейлер і К. Гаус розглядали часом тисячі прикладів, перш ніж помітити числову закономірність і повірити в неї. Але одночасно вони розуміли, наскільки оманливими можуть бути гіпотези, що пройшли «кінцеву» перевірку. Для індуктивного переходу від твердження, перевіреного для кінцевого підмножини, до аналогічного твердження для всієї нескінченної множини необхідний доказ. Такий спосіб запропонував Блез Паскаль, який знайшов загальний алгоритм знаходження ознак ділимості будь-якого цілого числа на будь-яке інше ціле число (трактат «Про характер ділимості чисел).

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

Рішення завдань на підтвердження істинності деякого затвердження методом математичної індукції складається з чотирьох етапів (рис. 1):

Рис. 1. Схема розв'язання задачі

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

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

3. Індукційний перехід . Доводимо, що твердження є справедливим для k+1.

4. Висновок . Якщо такий доказ вдалося довести остаточно, то, з урахуванням принципу математичної індукції можна стверджувати, що твердження правильне будь-якого натурального числа n.

Розглянемо застосування методу математичної індукції до розв'язання задач на доказ подільності натуральних чисел.

Приклад 1. Довести, що число 5 кратне 19, де n – натуральне число.

Доведення:

1) Перевіримо, що ця формула вірна за n = 1: число =19 кратно 19.

2) Нехай ця формула правильна для n = k, тобто число кратне 19.

Кратно 19. Справді, перший доданок поділяється на 19 з припущення (2); другий доданок теж ділиться на 19, тому що містить множник 19.

приклад 2.Довести, що сума кубів трьох послідовних чисел ділиться на 9.

Доведення:

Доведемо твердження: «Для будь-якого натурального числа n вираз n 3 +(n+1) 3 +(n+2) 3 кратно 9.

1) Перевіримо, що ця формула вірна за n = 1: 1 3 +2 3 +3 3 =1+8+27=36 кратно 9.

2) Нехай ця формула правильна для n = k, тобто k 3 + (k + 1) 3 + (k + 2) 3 кратно 9.

3) Доведемо, що формула вірна і для n = k + 1, тобто (k+1) 3 +(k+2) 3 +(k+3) 3 кратно 9. (k+1) 3 +( k+2) 3 +(k+3) 3 =(k+1) 3 +(k+2) 3 + k 3 + 9k 2 +27 k+ 27=(k 3 +(k+1) 3 +(k +2) 3) +9 (k 2 +3k + 3).

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

4) Обидві умови принципу математичної індукції виконані, отже, речення істинно за всіх значень n.

приклад 3.Довести, що за будь-якого натурального n число 3 2n+1 +2 n+2 ділиться на 7.

Доведення:

1) Перевіримо, що ця формула вірна за n = 1: 3 2*1+1 +2 1+2 = 3 3 +2 3 =35, 35 кратно 7.

2) Нехай ця формула правильна для n = k, тобто 32 k +1 +2 k +2 ділиться на 7.

3) Доведемо, що формула вірна й у n = k + 1, тобто.

3 2(k +1)+1 +2 (k +1)+2 =3 2 k +1 ·3 2 +2 k +2 ·2 1 =3 2 k +1 ·9+2 k +2 ·2 =3 2 k +1 · 9 +2 k +2 · (9-7) = (3 2 k +1 +2 k +2) · 9-7 · 2 k +2 .Т. к. (3 2 k +1 +2 k +2) 9 ділиться на 7 і 7 2 k 2 ділиться на 7, то і їх різниця ділиться на 7.

4) Обидві умови принципу математичної індукції виконані, отже, речення істинно за всіх значень n.

Багато завдань на підтвердження теорії ділимості натуральних чисел зручно вирішувати із застосуванням методу математичної індукції, можна навіть сказати, що розв'язання задач даним методом цілком алгоритмізоване, достатньо виконати 4 основні дії. Але універсальним цей метод назвати не можна, тому що є і недоліки: по-перше, доводити можна тільки на безлічі натуральних чисел, а по-друге, доводити можна тільки для однієї змінної.

Для розвитку логічного мислення, математичної культури цей метод є необхідним інструментом, Адже ще великий російський математик А. М. Колмогоров говорив: «Розуміння і вміння правильно застосовувати принцип математичної індукції, є добрим критерієм логічної зрілості, яка необхідна математику».

Література:

1. Віленкін Н. Я. Індукція. Комбінаторика. - М: Просвітництво, 1976. - 48 с.

2. Генкін Л. Про математичну індукцію. – М., 1962. – 36 с.

3. Соломінський І. С. Метод математичної індукції. - М: Наука, 1974. - 63с.

4. Шаригін І. Ф. Факультативний курс з математики: Розв'язання задач: Навчальний посібник для 10 кл. сред.шк. - М: Просвітництво, 1989. - 252 с.

5. Шень А. Математична індукція. - М.: МЦНМО, 2007. - 32 с.

Застосовуючи метод математичної індукції, довести, що для будь-якого натурального nсправедливі такі рівності:
а) ;
б) .

Рішення.

а) При n= 1 рівність справедлива. Припускаючи справедливість рівності при n, покажемо справедливість його і при n+ 1. Справді,

що і потрібно було довести.

б) При n= 1 справедливість рівності очевидна. З припущення справедливості його за nслід

Враховуючи рівність 1 + 2 + ... + n = n(n+ 1)/2, отримуємо

1 3 + 2 3 + ... + n 3 + (n + 1) 3 = (1 + 2 + ... + n + (n + 1)) 2 ,

тобто твердження справедливе і при n + 1.

приклад 1.Довести такі рівність

де nПро N.

Рішення. a) При n= 1 рівність набуде вигляду 1=1, отже, P(1) істинно. Припустимо, що ця рівність справедлива, тобто має місце

. Слід перевірити (довести), щоP(n+ 1), тобто істинно. Оскільки (використовується припущення індукції)отримаємо тобто, P(n+ 1) – справжнє твердження.

Таким чином, згідно з методом математичної індукції, вихідна рівність справедлива для будь-якого натурального n.

Примітка 2.Цей приклад можна було б вирішити й інакше. Справді, сума 1 + 2 + 3 + ... + nє сума перших nчленів арифметичної прогресіїз першим членом a 1 = 1 і різницею d= 1. У силу відомої формули , отримаємо

b) При n= 1 рівність набуде вигляду: 2 · 1 - 1 = 1 2 або 1 = 1, тобто, P(1) істинно. Припустимо, що має місце рівність

1 + 3 + 5 + ... + (2n - 1) = n 2 і доведемо, що має місцеP(n + 1): 1 + 3 + 5 + ... + (2n - 1) + (2(n + 1) - 1) = (n+ 1) 2 або 1 + 3 + 5 + ... + (2 n - 1) + (2n + 1) = (n + 1) 2 .

Використовуючи припущення індукції, отримаємо

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

Таким чином, P(n+ 1) істинно і, отже, необхідну рівність доведено.

Примітка 3.Цей приклад можна вирішити (подібно до попереднього) без використання методу математичної індукції.

c) При n= 1 рівність істинно: 1=1. Припустимо, що істинна рівність

і покажемо, що тобто істинністьP(n) тягне істинністьP(n+ 1). Справді,і, тому що 2 n 2 + 7 n + 6 = (2 n + 3)(n+ 2), отримаємо і, отже, вихідна рівність справедлива для будь-якого натуральногоn.

d) При n= 1 рівність справедливо: 1=1. Припустимо, що має місце

і доведемо, що

Справді,

e) Затвердження P(1) справедливо: 2=2. Припустимо, що рівність

справедливо, і доведемо, що воно спричиняє рівністьСправді,

Отже, вихідна рівність має місце для будь-якого натурального n.

f) P(1) справедливо: 1/3 = 1/3. Нехай має місце рівність P(n):

. Покажемо, що остання рівність тягне за собою наступне:

Дійсно, враховуючи, що P(n) має місце, отримаємо

Отже, рівність доведено.

g) При n= 1 маємо a + b = b + aі, отже, рівність справедлива.

Нехай формула бінома Ньютона справедлива за n = k, тобто,

Тоді Використовуючи рівністьотримаємо

приклад 2.Довести нерівності

a) нерівність Бернуллі: (1 + a) n ≥ 1 + n a , a > -1, nПро N.

b) x 1 + x 2 + ... + x n ≥ n, якщо x 1 x 2 · ... · x n= 1 і x i > 0, .

c) нерівність Коші щодо середнього арифемтичного та середнього геометричного де x i > 0, , n ≥ 2.

d) sin 2 n a + cos 2 n a ≤ 1, nПро N.

e)

f) 2 n > n 3 , nПро N, n ≥ 10.

Рішення. a) При n= 1 отримуємо справжню нерівність

1 + a ≥ 1 + a. Припустимо, що має місце нерівність

(1 + a) n ≥ 1 + n a

(1)

і покажемо, що тоді має місце і(1 + a) n + 1 ≥ 1 + (n+ 1) a.

Справді, оскільки a > -1 тягне a + 1 > 0, то помножуючи обидві частини нерівності (1) на (a + 1), отримаємо

(1 + a) n(1 + a ) ≥ (1 + n a) (1 + a) або (1 + a) n + 1 ≥ 1 + (n+ 1) a + n a 2 Оскільки n a 2 ≥ 0, отже,(1 + a) n + 1 ≥ 1 + (n+ 1) a + n a 2 ≥ 1 + ( n+ 1) a.

Таким чином, якщо P(n) істинно, те й P(n+ 1) істинно, отже, згідно з принципом математичної індукції, нерівність Бернуллі справедлива.

b) При n= 1 отримаємо x 1 = 1 і, отже, x 1 ≥ 1 тобто P(1) – справедливе твердження. Припустимо, що P(n) істинно, тобто, якщо adica, x 1 ,x 2 ,...,x n - nпозитивних чисел, добуток яких дорівнює одиниці, x 1 x 2 ·...· x n= 1, і x 1 + x 2 + ... + x n ≥ n.

Покажемо, що ця пропозиція тягне за собою істинність наступного: якщо x 1 ,x 2 ,...,x n ,x n+1 - (n+ 1) позитивних чисел, таких, що x 1 x 2 ·...· x n · x n+1 = 1, тоді x 1 + x 2 + ... + x n + x n + 1 ≥n + 1.

Розглянемо наступні два випадки:

1) x 1 = x 2 = ... = x n = x n+1 = 1. Тоді сума цих чисел дорівнює ( n+ 1), та необхідна нерівність виконується;

2) хоча одне число відмінно від одиниці, нехай, наприклад, більше одиниці. Тоді, оскільки x 1 x 2 · ... · x n · x n+ 1 = 1, існує ще хоча б одне число, відмінне від одиниці (точніше, менше одиниці). Нехай x n+ 1 > 1 та x n < 1. Рассмотрим nпозитивних чисел

x 1 ,x 2 ,...,x n-1 ,(x n · x n+1). Добуток цих чисел дорівнює одиниці, і, згідно з гіпотезою, x 1 + x 2 + ... + x n-1 + x n x n + 1 ≥ n. Остання нерівність переписується наступним чином: x 1 + x 2 + ... + x n-1 + x n x n+1 + x n + x n+1 ≥ n + x n + x n+1 або x 1 + x 2 + ... + x n-1 + x n + x n+1 ≥ n + x n + x n+1 - x n x n+1 .

Оскільки

(1 - x n)(x n+1 - 1) > 0, то n + x n + x n+1 - x n x n+1 = n + 1 + x n+1 (1 - x n) - 1 + x n =
= n + 1 + x n+1 (1 - x n) - (1 - x n) = n + 1 + (1 - x n)(x n+1 - 1) ≥ n+ 1. Отже, x 1 + x 2 + ... + x n + x n+1 ≥ n+1, тобто якщо P(n) справедливо, то йP(n+ 1) справедливо. Нерівність доведена.

Зауваження 4.Знак рівності має місце тоді і лише тоді, коли x 1 = x 2 = ... = x n = 1.

c) Нехай x 1 ,x 2 ,...,x n- Довільні позитивні числа. Розглянемо такі nпозитивних чисел:

Оскільки їх добуток дорівнює одиниці: згідно з раніше доведеною нерівністю b), слідує, щозвідки

Примітка 5.Рівність виконується якщо і тільки якщо x 1 = x 2 = ... = x n .

d) P(1) - справедливе твердження: sin 2 a + cos 2 a = 1. Припустимо, що P(n) - справжнє твердження:

Sin 2 n a + cos 2 n a ≤ 1 і покажемо, що має місцеP(n+ 1). Справді, sin 2( n+ 1) a + cos 2( n+ 1) a = sin 2 n a · sin 2 a + cos 2 n a · cos 2 a< sin 2n a + cos 2 n a ≤ 1 (якщо sin 2 a ≤ 1, то cos 2 a < 1, и обратно: если cos 2 a ≤ 1, то sin 2 a < 1). Таким образом, для любого nПро N sin 2 n a + cos 2 n ≤ 1 і знак рівності досягається лише заn = 1.

e) При n= 1 твердження справедливе: 1< 3 / 2 .

Припустимо, що і доведемо, що

Оскільки
враховуючи P(n), отримаємо

f) Враховуючи зауваження 1 , перевіримо P(10): 2 10 > 10 3 , 1024 > 1000, отже, для n= 10 твердження справедливе. Припустимо, що 2 n > n 3 (n> 10) та доведемо P(n+ 1), тобто 2 n+1 > (n + 1) 3 .

Оскільки при n> 10 маємо або , випливає, що

2n 3 > n 3 + 3n 2 + 3n+ 1 або n 3 > 3n 2 + 3n + 1. Враховуючи нерівність (2 n > n 3), отримаємо 2 n+1 = 2 n· 2 = 2 n + 2 n > n 3 + n 3 > n 3 + 3n 2 + 3n + 1 = (n + 1) 3 .

Таким чином, згідно з методом математичної індукції, для будь-якого натурального nПро N, n≥ 10 маємо 2 n > n 3 .

приклад 3.Довести, що для будь-кого nПро N

Рішення. a) P(1) – справжнє твердження (0 ділиться на 6). Нехай P(n) справедливо, тобто n(2n 2 - 3n + 1) = n(n - 1)(2n- 1) ділиться на 6. Покажемо, що тоді має місце P(n+ 1), тобто, ( n + 1)n(2n+ 1) ділиться на 6. Дійсно, оскільки

і як n(n - 1)(2 n- 1), так і 6 n 2 діляться на 6, тоді та їх сумаn(n + 1)(2 n+ 1) ділиться 6.

Таким чином, P(n+ 1) - справедливе твердження, і, отже, n(2n 2 - 3n+ 1) ділиться на 6 для будь-якого nПро N.

b) Перевіримо P(1): 6 0 + 3 2 + 3 0 = 11, отже, P(1) – справедливе твердження. Слід довести, що якщо 6 2 n-2 + 3 n+1 + 3 n-1 ділиться на 11 ( P(n)), тоді і 6 2 n + 3 n+2 + 3 nтакож ділиться на 11 ( P(n+ 1)). Справді, оскільки

6 2n + 3 n+2 + 3 n = 6 2n-2+2 + 3 n+1+1 + 3 n-1 +1 = = 6 2 · 6 2 n-2 + 3 · 3 n+1 + 3·3 n-1 = 3 · (6 2 n-2 + 3 n+1 + 3 n-1) + 33 · 6 2 n-2 і, як 6 2 n-2 + 3 n+1 + 3 n-1 так і 33·6 2 n-2 діляться на 11, тоді та їх сума 6 2n + 3 n+2 + 3 n ділиться на 11. Твердження доведено. Індукція у геометрії

приклад 4.Обчислити бік правильного 2 n-кутника, вписаного в коло радіусу R.

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

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

Індукція (induction – латиною) наведення) наочно ілюструється відомою легендою про те, як Ісаак Ньютон сформулював закон всесвітнього тяжіння після того, як йому на голову впало яблуко. Ще приклад із фізики: у такому явищі, як електромагнітна індукція, електричне поле створює, «наводить» магнітне поле. «Ньютонове яблуко» – типовий приклад ситуації, коли один або кілька окремих випадків, тобто спостереження, «наводять» на загальне твердження, загальний висновок робиться на підставі окремих випадків. Індуктивний метод є основним для отримання загальних закономірностей і в природничих, і гуманітарних науках. Але він має вельми істотний недолік: на підставі приватних прикладів може бути зроблено неправильний висновок. Гіпотези, що виникають при приватних спостереженнях, який завжди є правильними. Розглянемо приклад, що належить Ейлер.

Обчислюватимемо значення тричлена при деяких перших значеннях n:

Зауважимо, що одержувані в результаті обчислень числа є простими. І безпосередньо можна переконатися, що для кожного nвід 1 до 39 значення багаточлена
є простим числом. Однак при n=40 отримуємо число 1681=41 2 яке не є простим. Таким чином, гіпотеза, яка тут могла виникнути, тобто гіпотеза про те, що за кожного nчисло
є простим, виявляється неправильним.

Лейбніц у 17 столітті довів, що при будь-якому цілому позитивному nчисло
ділиться на 3, число
ділиться на 5 і т.д. На підставі цього він припустив, що при кожному непарному kта будь-якому натуральному nчисло
ділиться на k, але незабаром сам помітив, що
не поділяється на 9.

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

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

♦ В основі методу математичної індукції лежить принцип математичної індукції , що полягає в наступному:

1) перевіряється справедливість цього твердження дляn=1 (Базис індукції) ,

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

Доведення. Припустимо неприємне, тобто припустимо, що твердження справедливе не для будь-якого натурального n. Тоді існує таке натуральне m, що:

1) затвердження для n=mнесправедливо,

2) для кожного n, меншого m, твердження справедливе (іншими словами, mє перше натуральне число, котрим твердження несправедливо).

Очевидно, що m>1, т.к. для n=1 твердження справедливе (умова 1). Отже,
- натуральне число. Виходить, що для натурального числа
твердження справедливе, а для наступного натурального числа mвоно несправедливо. Це суперечить умові 2. ■

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

Доказ, заснований на принципі математичної індукції, називається методом повної математичної індукції .

 приклад6.1. Довести, що за будь-якого натурального nчисло
ділиться на 3.

Рішення.

1) При n=1 , тому a 1 ділиться на 3 і затвердження справедливо при n=1.

2) Припустимо, що твердження справедливе при n=k,
, тобто що число
ділиться на 3, і встановимо, що за n=k 1 число ділиться на 3.

Справді,

Т.к. кожне доданок ділиться на 3, їх сума також ділиться на 3. ■ 

 приклад6.2. Довести, що сума перших nнатуральних непарних чисел дорівнює квадрату їх числа, тобто .

Рішення.Скористаємося методом повної математичної індукції.

1) Перевіряємо справедливість даного твердження при n=1: 1=1 2 – це правильно.

2) Припустимо, що сума перших k (
) непарних чисел дорівнює квадрату числа цих чисел, тобто . Виходячи з цієї рівності, встановимо, що сума перших k+1 непарних чисел дорівнює
, тобто .

Користуємося нашим припущенням та отримуємо

. ■ 

Метод повної математичної індукції застосовується докази деяких нерівностей. Доведемо нерівність Бернуллі.

 приклад6.3. Довести, що при
та будь-якому натуральному nсправедлива нерівність
(Нерівність Бернуллі).

Рішення. 1) При n=1 отримуємо
що вірно.

2) Припускаємо, що за n=kмає місце нерівність
(*). Використовуючи це припущення, доведемо, що
. Зазначимо, що за
ця нерівність виконується і тому достатньо розглянути випадок
.

Помножимо обидві частини нерівності (*) на число
та отримаємо:

Тобто (1+
.■ 

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

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

 приклад6.4. Знайти суму
.

Рішення.Знайдемо суми S 1 , S 2 , S 3 . Маємо
,
,
. Висловлюємо гіпотезу, що за будь-якого натурального nсправедлива формула
. Для перевірки цієї гіпотези скористаємося методом повної математичної індукції.

1) При n=1 гіпотеза правильна, т.к.
.

2) Припустимо, що гіпотеза правильна при n=k,
, тобто
. Використовуючи цю формулу, встановимо, що гіпотеза вірна і при n=k+1, тобто

Справді,

Отже, виходячи з припущення, що гіпотеза вірна при n=k,
, доведено, що вона вірна і при n=k+1, і на підставі принципу математичної індукції робимо висновок, що формула справедлива за будь-якого натурального n. ■ 

 приклад6.5. У математиці доводиться, що сума двох рівномірно безперервних функцій є рівномірно безперервною функцією. Маючи це твердження, треба довести, що сума будь-якого числа
рівномірно безперервних функцій є рівномірно безперервною функцією. Але оскільки ми ще не ввели поняття «рівномірно безперервна функція», поставимо завдання абстрактніше: нехай відомо, що сума двох функцій, що мають деяку властивість S, сама має властивість S. Доведемо, що сума будь-якого числа функцій має властивість S.

Рішення.Базис індукції тут міститься у самому формулюванні завдання. Зробивши припущення індукції, розглянемо
функцій f 1 , f 2 , …, f n , f n+1 , що мають властивість S. Тоді. У правій частині перший доданок має властивість Sза припущенням індукції, другий доданок має властивість Sза умовою. Отже, їх сума має властивість S– для двох доданків «працює» базис індукції.

Тим самим твердження доведене і використовуватимемо його далі. ■ 

 приклад6.6. Знайти усі натуральні n, для яких справедлива нерівність

.

Рішення.Розглянемо n=1, 2, 3, 4, 5, 6. Маємо: 2 1 >1 2 , 2 2 =2 2 , 2 3<3 2 , 2 4 =4 2 , 2 5 >5 2 , 2 6 >6 2 . Таким чином, можна висловити гіпотезу: нерівність
має місце для кожного
. Для підтвердження істинності цієї гіпотези скористаємося принципом неповної математичної індукції.

1) Як було встановлено вище, дана гіпотеза істинна при n=5.

2) Припустимо, що вона істинна для n=k,
, тобто справедлива нерівність
. Використовуючи це припущення, доведемо, що справедлива нерівність
.

Т. до.
і при
має місце нерівність

при
,

то отримуємо, що
. Отже, істинність гіпотези при n=k+1 випливає з припущення, що вона вірна при n=k,
.

З пп. 1 і 2 на підставі принципу неповної математичної індукції випливає, що нерівність
вірно при кожному натуральному
. ■ 

 приклад6.7. Довести, що для будь-якого натурального числа nсправедлива формула диференціювання
.

Рішення.При n=1 дана формула має вигляд
, або 1 = 1, тобто вона вірна. Зробивши припущення індукції, матимемо:

що і потрібно було довести. ■ 

 приклад6.8. Довести, що безліч, що складається з nелементів, має підмножин.

Рішення.Безліч, що складається з одного елемента амає два підмножини. Це вірно, оскільки всі його підмножини – порожня множина і сама ця множина, і 2 1 =2.

Припустимо, що всяка множина з nелементів має підмножин. Якщо безліч А складається з n+1 елементів, то фіксуємо в ньому один елемент - позначимо його d, і розіб'ємо всі підмножини на два класи – не містять dта містять d. Усі підмножини з першого класу є підмножинами множини, що виходить з А викиданням елемента d.

Безліч В складається з nелементів, і тому, на думку індукції, у нього підмножин, так що в першому класі підмножин.

Але в другому класі підмножин стільки ж: кожна з них виходить рівно з одного підмножини першого класу додаванням елемента d. Отже, всього у множини А
підмножин.

Тим самим було твердження доведено. Зазначимо, що воно справедливе і для множини, що складається з 0 елементів - порожньої множини: воно має єдине підмножина - самого себе, і 20 = 1. ■ 