Індукція є методом отримання загального затвердження з приватних спостережень. Якщо математичне твердження стосується кінцевого числа об'єктів, його можна довести, перевіряючи для кожного об'єкта. Наприклад, твердження: "Кожне двозначне парне число є сумою двох простих чисел," - випливає із серії рівностей, які цілком реально встановити:
10=5+5 12=5+7 14=7+7 16=5+11 . . . 92=3+89 94=5+89 96=7+89 98=19+79.
p align="justify"> Метод доказу, при якому перевіряється затвердження для кінцевого числа випадків, вичерпних всі можливості, називають повною індукцією. Цей метод можна застосувати порівняно рідко, оскільки математичні твердження стосуються, як правило, не кінцевих, а нескінченних множин об'єктів. Наприклад, доведене вище повної індукцією твердження про парних двозначних числах є лише окремим випадком теореми: «Будь-яке парне число є сумою двох простих чисел». Ця теорема досі не доведена, ні спростована.
Математична індукція – спосіб доказу деякого твердження для будь-якого натурального n заснований на принципі математичної індукції: «Якщо твердження правильне для n=1 і з справедливості його для n=k випливає справедливість цього твердження для n=k+1, воно правильне всім n ». Спосіб доказу методом математичної індукції полягає в наступному:
1) база індукції: доводять чи безпосередньо перевіряють справедливість затвердження для n=1 (іноді n=0 чи n=n 0);
2) індукційний крок (перехід): припускають справедливість твердження для деякого натурального n=k і, виходячи з цього припущення, доводять справедливість твердження для n=k+1.
Завдання з рішеннями
1. Довести, що з будь-якому натуральному n число 3 2n+1 +2 n+2 ділиться на 7.
Позначимо А(n)=3 2n+1 +2 n+2.
Основа індукції. Якщо n=1, то А(1)=3 3 +2 3 =35 і, мабуть, ділиться на 7.
Припущення індукції. Нехай А(k) поділяється на 7.
Індукційний перехід. Доведемо, що А(k+1) ділиться на 7, тобто справедливість утвердження задачі за n=k.
А(k+1)=3 2(k+1)+1 +2 (k+1)+2 =3 2k+1 ·3 2 +2 k+2 ·2 1 =3 2k+1 ·9+2 k+2 ·2=
3 2k+1 ·9+2 k+2 ·(9–7)=(3 2k+1 +2 k+2)·9–7·2 k+2 =9·А(k)–7·2 k +2.
Останнє число ділиться на 7, тому що є різницею двох цілих чисел, що діляться на 7. Отже, 3 2n+1 +2 n+2 ділиться на 7 при будь-якому натуральному n.
2. Довести, що з будь-якому натуральному n число 2 3 n +1 ділиться на 3 n+1 і ділиться на 3 n+2 .
Введемо позначення: а i = 2 3 i +1.
За n=1 маємо, а 1 =2 3 +1=9. Отже, а 1 ділиться на 32 і не ділиться на 33.
Нехай при n=k число а k ділиться на 3 k+1 і не ділиться на 3 k+2, тобто а k =2 3 k +1=3 k+1 ·m, де m не ділиться на 3.
а k+1 =2 3 k+1 +1=(2 3 k) 3 +1=(2 3 k +1)(2 3 k ·2 –2 3 k +1)=3 k+1 ·m· ((2 3 k +1) 2 –3·2 3 k)=3 k+1 ·m·((3 k+1 ·m) 2 –3·2 3 k)=
3 k+2 ·m·(3 2k+1 ·m 2 –2 3 k).
Очевидно, а k+1 ділиться на 3 k+2 і ділиться на 3 k+3 .
Отже, твердження підтверджено для будь-якого натурального n.
3. Відомо, що х+1/x – ціле число. Довести, що х n +1/х n – так само ціле число за будь-якого цілому n.
Введемо позначення: а i = x i +1 / x i і відразу зазначимо, що а i = а -i, тому далі вестимемося про натуральні індекси.
Зауважимо: а 1 – ціле число за умовою; а 2 - ціле, тому що а 2 = (а 1) 2 -2; а 0 =2.
Припустимо, що а k ціле за будь-якого натурального k не перевищує n. Тоді а 1 · а n – ціле число, але а 1 · а n = а n+1 + а n–1 та а n+1 = а 1 · а n –а n–1 . Однак, а n–1 згідно індукційного припущення – ціле. Отже, цілим є й а n+1 . Отже, х n +1/х n – ціле число за будь-якого цілому n, що потрібно було довести.
4. Довести, що за будь-якого натурального n більшого 1 справедлива подвійна нерівність
5. Довести, що з натуральному n > 1 і |х|
(1-x) n + (1+x) n
При n=2 нерівність вірна. Справді,
(1–x) 2 +(1+x) 2 = 2+2·х 2
Якщо нерівність правильна при n=k, то за n=k+1 маємо
(1-x) k+1 +(1+x) k+1
Нерівність доведена будь-якого натурального n > 1.
6. На площині дано n кіл. Довести, що при будь-якому розташуванні цих кіл утворювану ними карту можна правильно розфарбувати двома фарбами.
Скористаємося методом математичної індукції.
При n=1 твердження очевидне.
Припустимо, що твердження справедливе для будь-якої карти, утвореної n колами, і нехай на площині задано n+1 кіл. Видаливши одне з цих кіл, ми отримаємо карту, яку в силу зробленого припущення можна правильно розфарбувати двома фарбами (дивіться перший малюнок з наведених нижче).
Відновимо потім відкинуте коло і з одного боку від нього, наприклад усередині, змінимо колір кожної області на протилежний (дивіться другий малюнок). Легко бачити, що при цьому ми отримаємо карту, правильну розфарбовану двома фарбами, але тільки тепер вже при n+1 колах, що потрібно було довести.
7. Випуклий багатокутник називатимемо «красивим», якщо виконуються такі умови:
1) кожна його вершина пофарбована в один із трьох кольорів;
2) будь-які дві сусідні вершини забарвлені у різні кольори;
3) у кожен із трьох кольорів пофарбована, принаймні, одна вершина багатокутника.
Довести, що будь-який красивий n-кутник можна розрізати діагоналі, що не перетинаються, на «красиві» трикутники.
Скористаємося методом математичної індукції.
Основа індукції. При найменшому з можливих n=3 твердження задачі очевидне: вершини «красивого» трикутника забарвлені у три різних кольори і ніякі розрізи не потрібні.
Припущення індукції. Припустимо, що затвердження завдання правильне для будь-якого «красивого» n-кутника.
Індукційний крок. Розглянемо довільний "гарний" (n+1)-кутник і доведемо, використовуючи припущення індукції, що його можна розрізати деякими діагоналями на "гарні" трикутники. Позначимо через А1, А2, А3, … Аn, Аn+1 – послідовні вершини (n+1)-кутника. Якщо в якомусь із трьох кольорів забарвлена лише одна вершина (n+1)-кутника, то, з'єднавши цю вершину діагоналями з усіма не сусідніми з нею вершинами, отримаємо необхідне розбиття (n+1)-кутника на «гарні» трикутники.
Якщо кожен із трьох кольорів пофарбовані щонайменше двох вершин (n+1)-угольника, то позначимо цифрою 1 колір вершини А 1 , а цифрою 2 колір вершини А 2 . Нехай k – такий найменший номер, що вершина А k забарвлена на третій колір. Зрозуміло, що k > 2. Відсічемо від (n+1)-кутника діагоналлю А k–2 А k трикутник А k–2 А k–1 А k . Відповідно до вибору числа k всі вершини цього трикутника забарвлені в три різні кольори, тобто цей трикутник «гарний». Випуклий n-кутник А 1 А 2 … А k–2 А k А k+1 … А n+1 , який залишився, також, з огляду на індуктивне припущення, буде «красивим», а значить розбивається на «красиві» трикутники, що і потрібно було довести.
8. Довести, що у опуклому n-кутнику не можна вибрати більше n діагоналей так, щоб будь-які дві з них мали спільну точку.
Проведемо підтвердження методом математичної індукції.
Доведемо більш загальне твердження: у опуклому n-кутнику не можна вибрати більше n сторін та діагоналей так, щоб будь-які дві з них мали спільну точку. При n = 3 твердження очевидне. Припустимо, що це твердження є правильним для довільного n-кутника і, використовуючи це, доведемо його справедливість для довільного (n+1)-кутника.
Припустимо, що з (n+1)-угольника це твердження неправильно. Якщо з кожної вершини (n+1)-кутника виходить не більше двох вибраних сторін або діагоналей, то їх вибрано не більше ніж n+1. Тому з певної вершини А виходить хоча б три обрані сторони або діагоналі AB, AC, AD. Нехай АС лежить між АВ та AD. Оскільки будь-яка сторона або діагональ, яка виходить з точки С і відмінна від СА, не може одночасно перетинати АВ та AD, то з точки С виходить лише одна обрана діагональ СА.
Відкинувши точку З разом із діагоналлю СА, отримаємо опуклий n-кутник, у якому вибрано більше n сторін і діагоналей, будь-які з яких мають загальну точку. Таким чином, приходимо до суперечності з припущенням, що твердження правильне для довільного опуклого n-кутника.
Отже, для (n+1)-кутника твердження вірне. Відповідно до принципу математичної індукції твердження правильне для будь-якого опуклого n-кутника.
9. У площині проведено n прямих, з яких жодні дві не паралельні та ніякі три не проходять через одну точку. Наскільки частин розбивають площину ці прямі.
За допомогою елементарних малюнків легко переконається, що одна пряма розбиває площину на 2 частини, дві прямі – на 4 частини, три прямі – на 7 частин, чотири прямі – на 11 частин.
Позначимо через N(n) число частин, куди n прямих розбивають площину. Можна помітити, що
N(2)=N(1)+2=2+2,
N(3)=N(2)+3=2+2+3,
N(4)=N(3)+4=2+2+3+4.
Природно припустити, що
N(n)=N(n–1)+n=2+2+3+4+5+…+n,
або, як легко встановити, скориставшись формулою суми n перших членів арифметичної прогресії,
N(n)=1+n(n+1)/2.
Доведемо справедливість цієї формули методом математичної індукції.
Для n=1 формула вже перевірено.
Зробивши припущення індукції, розглянемо k+1 прямих, які відповідають умові завдання. Виділимо їх довільним чином k прямих. За припущенням індукції, вони розіб'ють площину на 1+ k(k+1)/2 частин. Решта (k+1)-я пряма розіб'ється виділеними k прямими на k+1 частин і, отже, пройде по (k+1)-ї частини, на які площина вже була розбита, і кожну з цих частин розділить на 2 частини, тобто додасться ще k+1 частина. Отже,
N(k+1)=N(k)+k+1=1+ k(k+1)/2+k+1=1+(k+1)(k+2)/2,
що й потрібно було довести.
10. У виразі х 1:х 2: … :х n для вказівки порядку дій розставляються дужки та результат записується у вигляді дробу:
(при цьому кожна з літер х 1, х 2, …, х n стоїть або в чисельнику дробу, або у знаменнику). Скільки різних виразів можна таким чином отримати за всіляких способів розміщення дужок?
Насамперед ясно, що в отриманому дробі х 1 стоятиме в чисельнику. Майже так само очевидно, що х 2 виявиться в знаменнику при будь-якій розстановці дужок (знак поділу, що стоїть перед х 2 відноситься або до самого х 2 або до якого-небудь виразу, що містить х 2 в чисельнику).
Можна припустити, що решта букв х 3 , х 4 , … , х n можуть розташовуватися в чисельнику або знаменнику абсолютно довільним чином. Звідси випливає, що можна отримати 2 n–2 дробів: кожен із n–2 букв х 3 , х 4 , … , х n може бути незалежно від інших у чисельнику чи знаменнику.
Доведемо це твердження щодо індукції.
При n=3 можна отримати 2 дроби:
так що твердження справедливе.
Припустимо, що це справедливо при n=k і доведемо його n=k+1.
Нехай вираз х 1: х 2: … : х k після деякої розстановки дужок записується у вигляді деякого дробу Q. Якщо в цей вираз замість х k підставити х k: х k + 1, то х k виявиться там же, де і було в дробу Q, а х k+1 стоятиме не там, де стояло х k (якщо х k було в знаменнику, то х k+1 опиниться в чисельнику і навпаки).
Тепер доведемо, що можна додати х k+1 туди, де стоїть х k . У дробі Q після розміщення дужок обов'язково буде вираз виду q:х k , де q – літера х k–1 або деякий вираз у дужках. Замінивши q:х k виразом (q:х k):х k+1 =q:(х k ·х k+1), ми отримаємо, очевидно, той самий дріб Q, де замість х k стоїть х k ·х k+1.
Таким чином, кількість всіляких дробів у разі n=k+1 у 2 рази більша ніж у випадку n=k і дорівнює 2 k–2 · 2=2 (k+1)–2 . Тим самим було твердження доведено.
Відповідь: 2 n-2 дробів.
Завдання без рішень
1. Довести, що за будь-якого натурального n:
а) число 5 n -3 n + 2n ділиться на 4;
б) число n 3 +11n поділяється на 6;
в) число 7 n +3n-1 ділиться на 9;
г) число 6 2n +19 n -2 n +1 ділиться на 17;
д) число 7 n+1 +8 2n-1 ділиться на 19;
е) число 2 2n-1 -9n 2 +21n-14 ділиться на 27.
2. Доведіть, що (n+1)·(n+2)· … ·(n+n) = 2 n ·1·3·5·…·(2n–1).
3. Довести нерівність | sin nx | n|sin x| для будь-якого натурального n.
4. Знайдіть натуральні числа a, b, c, які не діляться на 10 і такі, що за будь-якого натурального числа a n + b n і c n мають однакові дві останні цифри.
5. Довести, що якщо n точок не лежать на одній прямій, то серед прямих, що їх з'єднують, не менше ніж n різних.
Метод математичної індукції
Вступ
Основна частина
- Повна та неповна індукція
- Принцип математичної індукції
- Метод математичної індукції
- Рішення прикладів
- Рівності
- Розподіл чисел
- Нерівності
Висновок
Список використаної літератури
Вступ
В основі будь-якого математичного дослідження лежать дедуктивний та індуктивний методи. Дедуктивний спосіб міркування - це міркування від загального до приватного, тобто. міркування, вихідним моментом якого є загальний результат, а заключним моментом – приватний результат. Індукція застосовується під час переходу від приватних результатів до загальних, тобто. є методом, протилежним до дедуктивного.
Метод математичної індукції можна порівняти із прогресом. Ми починаємо з нижчого, в результаті логічного мислення приходимо до вищого. Людина завжди прагнула прогресу, до вміння розвивати свою думку логічно, отже, сама природа накреслила йому розмірковувати індуктивно.
Хоча й зросла сфера застосування методу математичної індукції, у шкільній програмі йому приділяється мало часу. Ну, скажіть, що корисній людині принесуть ті два-три уроки, за які вона почує п'ять слів теорії, вирішить п'ять примітивних завдань, і в результаті отримає п'ятірку за те, що вона нічого не знає.
Адже це так важливо - вміти розмірковувати індуктивно.
Основна частина
За своїм первісним змістом слово “індукція” застосовується до міркувань, з яких отримують загальні висновки, спираючись низку приватних тверджень. Найпростішим методом міркувань такого роду є повна індукція. Ось приклад такої міркування.
Нехай потрібно встановити, що кожне натуральне парне число 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=13+5; 20=13+7.
Ці дев'ять рівностей показують, що кожна з чисел, що нас цікавлять, дійсно представляється у вигляді суми двох простих доданків.
Отже, повна індукція у тому, що загальне твердження доводиться окремо у кожному з кінцевого числа можливих випадків.
Іноді загальний результат вдається передбачити після розгляду не всіх, а досить великої кількості окремих випадків (так звана неповна індукція).
Результат, отриманий неповною індукцією, залишається, однак, лише гіпотезою, доки він не доведений точним математичним міркуванням, що охоплює всі окремі випадки. Іншими словами, неповна індукція в математиці не вважається законним методом суворого доказу, але є сильним методом відкриття нових істин.
Нехай, наприклад, потрібно знайти суму перших n послідовних непарних чисел. Розглянемо окремі випадки:
1+3+5+7+9=25=5 2
Після розгляду цих кількох окремих випадків напрошується наступний загальний висновок:
1+3+5+…+(2n-1)=n 2
тобто. сума n перших послідовних непарних чисел дорівнює n 2
Зрозуміло, зроблене спостереження ще може бути доказом справедливості наведеної формули.
Повна індукція має у математиці лише обмежене застосування. Багато цікавих математичних тверджень охоплюють нескінченну кількість окремих випадків, а провести перевірку для нескінченної кількості випадків ми не в змозі. Неповна індукція часто призводить до помилкових результатів.
У багатьох випадках вихід з таких труднощів полягає у зверненні до особливого методу міркувань, званого методом математичної індукції. Він полягає у наступному.
Нехай потрібно довести справедливість деякого твердження для будь-якого натурального числа n (наприклад, треба довести, що сума перших n непарних чисел дорівнює n 2). Безпосередня перевірка цього твердження кожного значення 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.
У ряді випадків потрібно довести справедливість деякого твердження не для всіх натуральних чисел, а лише для n>p, де p-фіксоване натуральне число. І тут принцип математичної індукції формулюється так.
Якщо пропозиція А(n) істинно при n=p і якщо А(k)ÞА(k+1) для будь-якого k>p, то пропозиція А(n) істинно для будь-якого n>p.
Доказ методом математичної індукції проводитися в такий спосіб. Спочатку доводиться твердження перевіряється для n=1, тобто. встановлюється істинність висловлювання А(1). Цю частину підтвердження називають базисом індукції. Потім слідує частина докази, звана індукційним кроком. У цьому частині доводять справедливість твердження для n=k+1 у припущенні справедливості твердження для n=k (припущення індукції), тобто. доводять, що А(k) ÞA(k+1).
Довести, що 1+3+5+…+(2n-1)=n 2 .
Рішення: 1) Маємо n=1=1 2 . Отже,
твердження правильне при n=1, тобто. А(1) істинно.
2) Доведемо, що А(k) ÞA(k+1).
Нехай k-будь-яке натуральне число і нехай твердження справедливо для n = k, тобто.
1+3+5+…+(2k-1)=k 2 .
Доведемо, що тоді твердження справедливе й у наступного натурального числа n=k+1, тобто. що
1+3+5+…+(2k+1)=(k+1) 2 .
Справді,
1+3+5+…+(2k-1)+(2k+1)=k 2 +2k+1=(k+1) 2 .
Отже, А(k) ÞА(k+1). З принципу математичної індукції укладаємо, що припущення А(n) істинно будь-якого nÎN.
Довести, що
1+х+х 2 +х 3 +…+х n =(х n+1 -1)/(х-1), де х1
Рішення: 1) При n=1 отримуємо
1+х=(х 2 -1)/(х-1)=(х-1)(х+1)/(х-1)=х+1
отже, при n=1 формула вірна; А(1) істинно.
2) Нехай k-будь-яке натуральне число і нехай формула правильна при n = k, тобто.
1+х+х 2 +х 3 +…+х k =(х k+1 -1)/(х-1).
Доведемо, що тоді виконується рівність
1+х+х 2 +х 3 +…+х k +x k+1 =(x k+2 -1)/(х-1).
Справді
1+х+х 2 +x 3 +…+х k +x k+1 =(1+x+x 2 +x 3 +…+x k)+x k+1 =
=(x k+1 -1)/(x-1)+x k+1 =(x k+2 -1)/(x-1).
Отже, А(k) ÞA(k+1). З принципу математичної індукції укладаємо, що форму-ла правильна будь-якого натурального числа n.
Довести, що число діагоналей опуклого n-кутника дорівнює n(n-3)/2.
Рішення: 1) При n=3 затвердження спра-
А 3 ведливо, бо в трикутнику
A 3 =3(3-3)/2=0 діагоналей;
А 2 А(3) істинно.
2) Припустимо, що у всякому
опуклому k-кутнику має-
А 1 ся А k = k (k-3) / 2 діагоналей.
А k Доведемо, що тоді у опуклому
(k+1)-кутник число
діагоналей А k+1 =(k+1)(k-2)/2.
Нехай А 1 А 2 А 3 …A k A k +1 - опуклий (k + 1)-кутник. Проведемо в ньому діагональ A1Ak. Щоб підрахувати загальне число діагоналей цього (k+1)-угольника треба підрахувати число діагоналей в k-кутнику A 1 A 2 …A k , додати до отриманого числа k-2, тобто. число діагоналей (k+1)-кутника, що виходять з вершини А k+1 і, крім того, слід врахувати діагональ А 1 А k .
Таким чином,
k+1 = k +(k-2)+1=k(k-3)/2+k-1=(k+1)(k-2)/2.
Отже, А(k) ÞA(k+1). Внаслідок принципу математичної індукції твердження правильне для будь-якого опуклого n-кутника.
Довести, що за будь-якого n справедливе твердження:
1 2 +2 2 +3 2 +…+n 2 =n(n+1)(2n+1)/6.
Рішення: 1) Нехай n = 1, тоді
Х 1 = 1 2 = 1 (1 +1) (2 +1) / 6 = 1.
Отже, при n=1 твердження правильне.
2) Припустимо, що n=k
Х k =k 2 =k(k+1)(2k+1)/6.
3) Розглянемо дане твердження при n=k+1
X k+1 = (k+1)(k+2)(2k+3)/6.
X k+1 =1 2 +2 2 +3 2 +…+k 2 +(k+1) 2 =k(k+1)(2k+1)/6+ +(k+1) 2 =(k (k+1)(2k+1)+6(k+1) 2)/6=(k+1)(k(2k+1)+
6(k+1))/6=(k+1)(2k 2 +7k+6)/6=(k+1)(2(k+3/2)(k+
2))/6=(k+1)(k+2)(2k+3)/6.
Ми довели справедливість рівності і при n = k + 1, отже, в силу методу математичної індукції, твердження правильне для будь-якого натурального n.
Довести, що для будь-якого натурального n справедлива рівність:
1 3 +2 3 +3 3 + ... + n 3 = n 2 (n + 1) 2 /4.
Рішення: 1) Нехай n = 1.
Тоді Х 1 = 13 = 12 (1 +1) 2 / 4 = 1.
Ми, що з n=1 твердження правильно.
2) Припустимо, що рівність правильна при n = k
X k = k 2 (k +1) 2/4.
3) Доведемо істинність цього твердження для n=k+1, тобто.
Х k+1 =(k+1) 2 (k+2) 2/4. X k+1 =1 3 +2 3 +…+k 3 +(k+1) 3 =k 2 (k+1) 2 /4+(k+1) 3 =(k 2 (k++1) 2 +4(k+1) 3)/4=(k+1) 2 (k 2 +4k+4)/4=(k+1) 2 (k+2) 2 /4.
З наведеного доказу видно, що твердження вірне при n = k + 1, отже, рівність вірно при будь-якому натуральному n.
Довести, що
((2 3 +1)/(2 3 -1))´((3 3 +1)/(3 3 -1))´…´((n 3 +1)/(n 3 -1))= 3n(n+1)/2(n 2 +n+1), де n>2.
Рішення: 1) При n=2 тотожність виглядає: (2 3 +1)/(2 3 -1)=(3´2´3)/2(2 2 +2+1),
тобто. воно вірне.
2) Припустимо, що вираз правильно при n = k
(2 3 +1)/(2 3 -1)´…´(k 3 +1)/(k 3 -1)=3k(k+1)/2(k 2 +k+1).
3) Доведемо вірність виразу при n=k+1.
(((2 3 +1)/(2 3 -1))´…´((k 3 +1)/(k 3 -1))))(((k+1) 3 +
1)/((k+1) 3 -1))=(3k(k+1)/2(k 2 +k+1))´((k+2)((k+
1) 2 -(k+1)+1)/k((k+1) 2 +(k+1)+1))=3(k+1)(k+2)/2´
´((k+1) 2 +(k+1)+1).
Ми довели справедливість рівності і при n=k+1, отже, через метод математичної індукції, твердження правильне для будь-якого n>2
Довести, що
1 3 -2 3 +3 3 -4 3 +…+(2n-1) 3 -(2n) 3 =-n 2 (4n+3)
для будь-якого натурального n.
Рішення: 1) Нехай n = 1, тоді
1 3 -2 3 =-1 3 (4+3); -7=-7.
2) Припустимо, що n=k тоді
1 3 -2 3 +3 3 -4 3 +…+(2k-1) 3 -(2k) 3 =-k 2 (4k+3).
3) Доведемо істинність цього твердження при n=k+1
(1 3 -2 3 +…+(2k-1) 3 -(2k) 3)+(2k+1) 3 -(2k+2) 3 =-k 2 (4k+3)+
+(2k+1) 3 -(2k+2) 3 =-(k+1) 3 (4(k+1)+3).
Доведено і справедливість рівності при n=k+1, отже твердження правильне для будь-якого натурального n.
Довести вірність тотожності
(1 2 /1´3)+(2 2 /3´5)+…+(n 2 /(2n-1)´(2n+1))=n(n+1)/2(2n+1)
для будь-якого натурального n.
1) При n = 1 тотожність вірно 1 2 /1 '3 = 1 (1 +1) / 2 (2 +1).
2) Припустимо, що з n=k
(1 2 /1´3)+…+(k 2 /(2k-1)´(2k+1))=k(k+1)/2(2k+1).
3) Доведемо, що тотожність правильна при n=k+1.
(1 2 /1´3)+…+(k 2 /(2k-1)(2k+1))+(k+1) 2 /(2k+1)(2k+3)=(k(k+ 1)/2(2k+1))+((k+1) 2 /(2k+1)(2k+3))=((k+1)/(2k+1))´((k/2 )+((k+1)/(2k+3)))=(k+1)(k+2)´ (2k+1)/2(2k+1)(2k+3)=(k+1 )(k+2)/2(2(k+1)+1).
З наведеного доказу видно, що твердження вірне за будь-якого натурального n.
Довести, що (11n+2+122n+1) ділиться на 133 без залишку.
Рішення: 1) Нехай n = 1, тоді
11 3 +12 3 = (11 +12) (11 2 -132 +12 2) = 23 '133.
Але (23´133) ділиться на 133 без залишку, отже при n=1 твердження вірне; А(1) істинно.
2) Припустимо, що (11 k+2 +12 2k+1) ділиться на 133 без залишку.
3) Доведемо, що у такому разі
(11 k+3 +12 2k+3) ділиться на 133 без залишку. Справді 11 k+3 +12 2л+3 =11´11 k+2 +12 2´ 12 2k+1 =11´11 k+2 +
+(11+133)´12 2k+1 =11(11 k+2 +12 2k+1)+133´12 2k+1 .
Отримана сума ділиться на 133 без залишку, так як перше її доданок ділиться на 133 без залишку за припущенням, а в другому одним з множників виступає 133. Отже, А(k) ÞА(k+1). У силу методу математичної індукції твердження доведено.
Довести, що за будь-якого n 7 n -1 ділиться на 6 без залишку.
Рішення: 1) Нехай n = 1, тоді Х 1 = 7 1 -1 = 6 ділиться на 6 без залишку. Значить при n = 1 твердження вірно.
2) Припустимо, що з n=k
7 k-1 ділиться на 6 без залишку.
3) Доведемо, що твердження є справедливим для n=k+1.
X k +1 = 7 k +1 -1 = 7 '7 k -7 +6 = 7 (7 k -1) +6.
Перше доданок ділиться на 6, оскільки 7 k -1 ділиться на 6 за припущенням, а другим доданком є 6. Значить 7 n -1 кратно 6 при будь-якому натуральному n. У силу методу математичної індукції твердження доведено.
Довести, що 3 3n-1 +2 4n-3 при довільному натуральному n ділиться на 11.
Рішення: 1) Нехай n = 1, тоді
Х 1 = 3 3-1 +2 4-3 = 3 2 +2 1 = 11 ділиться на 11 без залишку. Отже, при n=1 твердження правильне.
2) Припустимо, що з n=k
X k =3 3k-1+24k-3 ділиться на 11 без залишку.
3) Доведемо, що твердження правильне для n=k+1.
X k+1 =3 3(k+1)-1 +2 4(k+1)-3 =3 3k+2 +2 4k+1 =3 3´ 3 3k-1 +2 4´ 2 4k-3 =
27´3 3k-1 +16´2 4k-3 =(16+11)´3 3k-1 +16´2 4k-3 =16´3 3k-1 +
11´3 3k-1 +16´2 4k-3 =16(3 3k-1 +2 4k-3)+11´3 3k-1 .
Перше доданок ділиться на 11 без залишку, оскільки 3 3k-1 +2 4k-3 ділиться на 11 за припущенням, друге ділиться на 11, тому що одним з його множників є число 11. Значить і сума поділяється на 11 без залишку за будь-якого натурального n. У силу методу математичної індукції твердження доведено.
Довести, що 11 2n -1 при довільному натуральному n ділиться на 6 без залишку.
Рішення: 1) Нехай n=1, тоді 112-1=120 ділиться на 6 без залишку. Значить при n = 1 твердження вірно.
2) Припустимо, що з n=k
11 2k -1 ділиться на 6 без залишку.
11 2(k+1) -1=121´11 2k -1=120´11 2k +(11 2k -1).
Обидва доданків діляться на 6 без залишку: перше містить кратне 6-ти число 120, а друге ділиться на 6 без залишку за припущенням. Значить, і сума ділиться на 6 без залишку. З методу математичної індукції твердження доведено.
Довести, що 3 3n+3 -26n-27 при довільному натуральному n ділиться на 26 2 (676) без залишку.
Рішення: Попередньо доведемо, що 33n+3-1 ділиться на 26 без залишку.
- При n=0
- Припустимо, що з n=k
- Доведемо, що твердження
3 3 -1=26 ділиться на 26
3 3k+3 -1 поділяється на 26
Правильно при n=k+1.
3 3k+6 -1=27´3 3k+3 -1=26´3 3л+3 +(3 3k+3 -1) –ділиться на 26
Тепер проведемо доказ твердження, сформульованого за умови завдання.
1) Очевидно, що при n = 1 твердження вірно
3 3+3 -26-27=676
2) Припустимо, що з n=k
вираз 3 3k+3 -26k-27 ділиться на 26 2 без залишку.
3) Доведемо, що твердження правильне за n=k+1
3 3k+6 -26(k+1)-27=26(3 3k+3 -1)+(3 3k+3 -26k-27).
Обидва доданків діляться на 26 2; перше ділиться на 26 2 , тому що ми довели подільність на 26 вирази, що стоїть у дужках, а друге ділиться за припущенням індукції. З огляду на методу математичної індукції твердження доведено.
Довести, що якщо n>2 і х>0, то справедлива нерівність
(1+х) n >1+n´х.
Рішення: 1) При n=2 нерівність справедливо, оскільки
(1+х) 2 = 1+2х+х 2 >1+2х.
Отже, А(2) істинно.
2) Доведемо, що А(k) ÞA(k+1), якщо k> 2. Припустимо, що А(k) істинно, тобто справедлива нерівність
(1+х) k >1+k´x. (3)
Доведемо, що тоді і А(k+1) істинно, тобто, що справедлива нерівність
(1+x) k+1 >1+(k+1)´x.
Справді, помноживши обидві частини нерівності (3) на позитивне число 1+х, отримаємо
(1+x) k+1 >(1+k´x)(1+x).
Розглянемо праву частину останнього нерівний-
ства; маємо
(1+k´x)(1+x)=1+(k+1)´x+k´x 2 >1+(k+1)´x.
У результаті отримуємо, що
(1+х) k+1 >1+(k+1)´x.
Отже, А(k) ÞA(k+1). На підставі принципу математичної індукції можна стверджувати, що нерівність Бернуллі справедлива для будь-якого
Довести, що справедлива нерівність
(1+a+a 2) m > 1+m'a+(m(m+1)/2)'a 2 при а> 0.
Рішення: 1) При m=1
(1+а+а 2) 1 > 1+а+(2/2)´а 2 обидві частини рівні.
2) Припустимо, що з m=k
(1+a+a 2) k >1+k´a+(k(k+1)/2)´a 2
3) Доведемо, що з m=k+1 не-рівність правильна
(1+a+a 2) k+1 =(1+a+a 2)(1+a+a 2) k >(1+a+a 2)(1+k+a+)
+(k(k+1)/2)´a 2)=1+(k+1)´a+((k(k+1)/2)+k+1)´a 2 +
+((k(k+1)/2)+k)´a 3 +(k(k+1)/2)´a 4 > 1+(k+1)´a+
+((k+1)(k+2)/2)'a 2 .
Ми довели справедливість нерівності при m=k+1, отже, в силу методу математичної індукції, нерівність справедлива для будь-якого натурального m.
Довести, що за n>6 справедлива нерівність
3 n >n´2 n+1 .
Рішення: Перепишемо нерівність у вигляді
- При n=7 маємо
- Припустимо, що з n=k
3 7 /2 7 = 2187/128> 14 = 2 '7
нерівність вірна.
3) Доведемо вірність нерівності при n = k +1.
3 k+1 /2 k+1 =(3 k /2 k)'(3/2)>2k'(3/2)=3k>2(k+1).
Оскільки k>7, остання нерівність очевидна.
У силу методу математичної індукції нерівність справедлива для будь-якого натурального n.
Довести, що за n>2 справедлива нерівність
1+(1/2 2)+(1/3 2)+…+(1/n 2)<1,7-(1/n).
Рішення: 1) При n=3 нерівність вірна
1+(1/2 2)+(1/3 2)=245/180<246/180=1,7-(1/3).
- Припустимо, що з n=k
1+(1/2 2)+(1/3 2)+…+(1/k 2)=1,7-(1/k).
3) Доведемо справедливість не-
рівності за n=k+1
(1+(1/2 2)+…+(1/k 2))+(1/(k+1) 2)<1,7-(1/k)+(1/(k+1) 2).
Доведемо, що 1,7-(1/k)+(1/(k+1) 2)<1,7-(1/k+1)Û
û(1/(k+1) 2)+(1/k+1)<1/kÛ(k+2)/(k+1) 2 <1/kÛ
K(k+2)<(k+1) 2Û k 2 +2k Останнє очевидно, а тому 1+(1/2 2)+(1/3 2)+…+(1/(k+1) 2)<1,7-(1/k+1). З огляду на методу математичної індукції не-рівність доведено. Висновок Зокрема вивчивши метод математичної індукції, я підвищив свої знання в цій галузі математики, а також навчився вирішувати завдання, які раніше були мені не під силу. У це були логічні і цікаві завдання, тобто. саме ті, які підвищують інтерес до самої математики як до науки. Вирішення таких завдань стає цікавим заняттям і може залучити в математичні лабіринти все нових допитливих. На мою думку, це є основою будь-якої науки. Продовжуючи вивчати метод математичної індукції, я намагатимусь навчитися застосовувати його не лише в математиці, а й у вирішенні проблем фізики, хімії та самого життя. МАТЕМАТИКА: ЛЕКЦІЇ, ЗАВДАННЯ, РІШЕННЯ Навчальний посібник/В.Г.Болтянський, Ю.В.Сідоров, М.І.Шабунін. ТОВ "Попурі" 1996. АЛГЕБРА І ПОЧАТКУ АНАЛІЗУ Навчальний посібник / І. Т. Демідов, А. Н. Колмогоров, С. І. Шварцбург, О. С. Івашев-Мусатов, Б. Є. Вейц. "Освіта" 1975. Застосовуючи метод математичної індукції, довести, що для будь-якого натурального 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.Довести такі рівність Рішення. a) При n= 1 рівність набуде вигляду 1=1, отже, P(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. Припустимо, що істинна рівність d) При n= 1 рівність справедливо: 1=1. Припустимо, що має місце Справді, e) Затвердження P(1) справедливо: 2=2. Припустимо, що рівність Отже, вихідна рівність має місце для будь-якого натурального n. f) P(1) справедливо: Дійсно, враховуючи, що P(n) має місце, отримаємо Отже, рівність доведено. g) При n= 1 маємо a + b = b + aі, отже, рівність справедлива. Нехай формула бінома Ньютона справедлива за n = k, тобто, приклад 2.Довести нерівності Рішення. a) При n= 1 отримуємо справжню нерівність 1 + a ≥ 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позитивних чисел Оскільки (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 = Зауваження 4.Знак рівності має місце тоді і лише тоді, коли x 1 = x 2 = ... = x n = 1. c) Нехай x 1 ,x 2 ,...,x n- Довільні позитивні числа. Розглянемо такі nпозитивних чисел: Примітка 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 . Припустимо, що 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. Дійсно, оскільки Таким чином, 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. МЕТОД МАТЕМАТИЧНОЇ ІНДУКЦІЇ Слово індукція російською означає наведення, а індуктивними називають висновки, з урахуванням спостережень, дослідів, тобто. отримані шляхом ув'язнення від частки до загального. Наприклад, ми щодня спостерігаємо, що Сонце сходить зі сходу. Тому можна бути впевненим, що й завтра воно з'явиться на сході, а не на заході. Цей висновок ми робимо, не вдаючись до жодних припущень про причину руху Сонця по небу (більше того, саме цей рух виявляється уявним, оскільки насправді рухається земна куля). Проте цей індуктивний висновок правильно описує ті спостереження, які ми проведемо завтра. Роль індуктивних висновків у експериментальних науках дуже велика. Вони дають ті положення, з яких потім шляхом дедукції робляться подальші висновки. І хоча теоретична механіка ґрунтується на трьох законах руху Ньютона, самі ці закони стали результатом глибокого продумування досвідчених даних, зокрема законів Кеплера руху планет, виведених ним при обробці багаторічних спостережень датського астронома Тихо Браге. Спостереження, індукція виявляються корисними й надалі уточнення зроблених припущень. Після дослідів Майкельсона з вимірювання швидкості світла в середовищі, що рухається, виявилося необхідним уточнити закони фізики, створити теорію відносності. У математиці роль індукції значною мірою полягає в тому, що вона лежить в основі аксіоматики, що вибирається. Після того як тривала практика показала, що прямий шлях завжди коротший за кривий або ламаний, природно було сформулювати аксіому: для будь-яких трьох точок А, В і С виконується нерівність Поняття, що лежить в основі арифметики, слідувати за теж з'явилося при спостереженнях за строєм солдатів, кораблів та іншими впорядкованими множинами. Не слід, проте, думати, що це вичерпується роль індукції в математиці. Зрозуміло, ми повинні експериментально перевіряти теореми, логічно виведені з аксіоми: якщо під час висновку було зроблено логічних помилок, всі вони настільки вірні, оскільки істинні прийняті нами аксіоми. Але з цієї системи аксіом можна вивести дуже багато тверджень. І відбір тих тверджень, які треба доводити, знову нагадує індукція. Саме вона дозволяє відокремити корисні теореми від марних, вказує, які теореми можуть виявитися вірними, і навіть допомагає намітити шлях доказу. У багатьох розділах арифметики, алгебри, геометрії, аналізу доводиться доводити істинність речень А(n), що залежать від натуральної змінної. Доказ істинності пропозиції А(n) всім значень змінної часто вдається провести методом математичної індукції, заснований на наступному принципі. Пропозиція А(n) вважається істинною для всіх натуральних значень змінної, якщо виконані такі дві умови: Пропозиція А(n) істинно для n=1. З припущення, що А(n) істинно для n=k (де k - будь-яке натуральне число), випливає, що воно є істинним і для наступного значення n=k+1. Цей принцип називається принципом математичної індукції. Зазвичай він вибирається як один з аксіом, що визначають натуральний ряд чисел, і, отже, приймається без доказів. Під методом математичної індукції розуміють такий спосіб доказу. Якщо потрібно довести істинність пропозиції А(n) всім натуральних n, то, по-перше, слід перевірити істинність висловлювання А(1) і, по-друге, припустивши істинність висловлювання А(k), спробувати довести, що висловлювання А(k) +1) істинно. Якщо це вдається довести, причому доказ залишається справедливим для кожного натурального значення k, то відповідно до принципу математичної індукції, пропозиція А(n) визнається істинною для всіх значень n. Метод математичної індукції широко застосовується при доказі теорем, тотожностей, нерівностей, під час вирішення завдань ділимість, під час вирішення деяких геометричних та багатьох інших завдань. ділимість За допомогою методу математичної індукції можна доводити різні твердження щодо ділимості натуральних чисел. Наступне твердження можна порівняно легко довести. Покажемо, як виходить з допомогою методу математичної індукції. Приклад 1. Якщо n – натуральне число, то число парне. При n=1 наше твердження істинно: парне число. Припустимо, що – парне число. Оскільки , a 2k - парне число, то й приклад 2.Довести істинність речення A(n)=(число 5 кратно 19), n - натуральне число. Рішення. Висловлювання А (1) = (число кратно 19) істинно. Припустимо, що з деякого значення n=k А(k)=(число кратно 19) істинно. Тоді, оскільки Вочевидь, як і A(k+1) істинно. Дійсно, перший доданок ділиться на 19 з припущення, що A(k) істинно; друге доданок теж ділиться на 19, оскільки містить множник 19. Обидві умови принципу математичної індукції виконані, отже, пропозиція A(n) істинно за всіх значеннях n. підсумовування рядів
приклад 1.Довести формулу Рішення. При n=1 обидві частини рівності перетворюються на одиницю і, отже, перша умова принципу математичної індукції виконано. Припустимо, формула правильна при n=k, тобто. Додамо до обох частин цієї рівності та перетворимо праву частину. Тоді отримаємо Таким чином, з того, що формула вірна за n=k, випливає, що вона вірна і за n=k+1. Це твердження справедливе за будь-якого натурального значення k. Отже, друга умова принципу математичної індукції також виконана. Формулу доведено. приклад 2.Довести, що сума n перших чисел натурального ряду дорівнює . Рішення. Позначимо шукану суму, тобто. При n=1 гіпотеза вірна. Нехай Справді, Завдання вирішено. приклад 3.Довести, що сума квадратів n перших чисел натурального ряду дорівнює Рішення. Нехай. Припустимо, що І остаточно. приклад 4.Довести, що . Рішення. Якщо то Приклад 5.Довести, що Рішення. При n=1 гіпотеза явно правильна. Нехай. Доведемо, що . Справді, Приклади застосування методу математичної індукції до
доказу нерівностей
приклад 1.Довести, що за будь-якого натурального n>1 Рішення. Позначимо ліву частину нерівності через . Отже, за n=2 нерівність справедлива. Нехай у деякому k. Доведемо, що тоді і . Маємо Порівнюючи і маємо За будь-якого натурального k права частина останньої рівності позитивна. Тому. Але, отже, і . приклад 2.Знайти помилку у міркуванні. Твердження. При будь-якому натуральному n справедлива нерівність. Доведення. . (1)
Доведемо, що тоді нерівність справедлива і за n=k+1, тобто. Справді, не менше 2 за будь-якого натурального k. Додамо до лівої частини нерівності (1), а до правої 2. Отримаємо справедливу нерівність, або приклад 3.Довести, що Рішення. При n=2 нерівність справедлива, оскільки . Нехай нерівність справедлива за n=k, де k - деяке натуральне число, тобто. Покажемо, що тоді нерівність справедлива і за n=k+1, тобто. . (2)
Дійсно, за умовою, тому справедлива нерівність , (3)
отримане з нерівності (1) множенням кожної частини його на . Перепишемо нерівність (3) так: . Відкинувши у правій частині останньої нерівності позитивний доданок, отримаємо справедливу нерівність (2). приклад 4.Довести, що (1)
де , , n – натуральне число, більше 1. Рішення. При n=2 нерівність (1) набуває вигляду Оскільки , то справедлива нерівність . (3)
Додавши до кожної частини нерівності (3) по отримаємо нерівність (2). Цим доведено, що з n=2 нерівність (1) справедливо. Нехай нерівність (1) справедливо при n=k, де k - деяке натуральне число, тобто. . (4)
Доведемо, що тоді нерівність (1) має бути справедливим і за n=k+1, тобто. (5)
Помножимо обидві частини нерівності (4) на a+b. Оскільки, за умовою, то отримуємо таку справедливу нерівність: . (6)
Щоб довести справедливість нерівності (5), достатньо показати, що , (7)
або, що те саме, . (8)
Нерівність (8) рівнозначна нерівності Якщо , то і в лівій частині нерівності (9) маємо добуток двох позитивних чисел. Якщо , то і в лівій частині нерівності (9) маємо добуток двох негативних чисел. В обох випадках нерівність (9) є справедливою. Цим доведено, що із справедливості нерівності (1) при n=k випливає його справедливість за n=k+1. Метод математичної індукції застосування до інших
завданням Найбільш природне застосування методу математичної індукції в геометрії, близьке до використання цього методу теорії чисел і в алгебрі, - це застосування до вирішення геометричних завдань на обчислення. Розглянемо кілька прикладів. приклад 1.Обчислити сторону правильного - косинця, вписаного в коло радіусу R. Рішення. При n=2 правильний 2 n - косинець є квадрат; його сторона. Далі, згідно з формулою подвоєння знаходимо, що сторона правильного восьмикутника Припустимо, що сторона правильного вписаного - косинця виражається формулою (1). У такому разі за формулою подвоєння звідки випливає, що формула (1) справедлива за всіх n. приклад 2.На скільки трикутників n-кутник (не обов'язково опуклий) може бути розбитий своїми діагоналями, що не перетинаються? Рішення. Для трикутника це число дорівнює одиниці (у трикутнику не можна провести жодної діагоналі); для чотирикутника це число одно, очевидно, двом. Припустимо, що ми вже знаємо, що кожен k-кутник, де k А n А 1 А 2 Нехай А 1 А k – одна з діагоналей цього розбиття; вона ділить n-кутник А 1 А 2 …А n на k-кутник A 1 A 2 … Ak і (n-k+2)-кутник А 1 А k Ak +1 …A n . У силу зробленого припущення, загальна кількість трикутників розбиття буде рівна (k-2)+[(n-k+2)-2]=n-2; цим наше твердження доведено всім n. приклад 3.Вказати правило обчислення числа P(n) способів, якими опуклий n-кутник може бути розбитий на трикутники діагоналі, що не перетинаються. Рішення. Для трикутника це число одно, очевидно, одиниці: P(3)=1. Припустимо, ми вже визначили числа P(k) всім k P(n)=P(n-1)+P(n-2)P(3)+P(n-3)P(4)+…+P(3)P(n-2)+P(n -1). За допомогою цієї формули послідовно отримуємо: P(4)=P(3)+P(3)=2, P(5)=P(4)+P(3)P(3)+P(4)+5, P(6)=P(5)+P(4)P(3)+P(3)P(4)+P(5)=14 і т.д. Також за допомогою методу математичної індукції можна вирішувати завдання з графами. Нехай на площині задана мережа ліній, які з'єднують між собою якісь точки і не мають інших точок. Таку мережу ліній ми називатимемо картою, задані точки її вершинами, відрізки кривих між двома суміжними вершинами - межами карти, частини площини, куди вона розбивається кордонами - країнами карти. Нехай на площині задано деяку карту. Ми говоритимемо, що вона правильно розфарбована, якщо кожну її країну зафарбовано певною фарбою, причому будь-які дві країни, які мають між собою спільний кордон, зафарбовані в різні кольори. приклад 4.На площині дано n кіл. Довести, що при будь-якому розташуванні цих кіл утворювану ними карту можна правильно розфарбувати двома фарбами. Рішення. При n=1 наше твердження очевидне. Припустимо, що наше твердження справедливе для будь-якої карти, утвореної n колами, і нехай на площині задано n+1 кіл. Видаливши одне з цих кіл, ми отримаємо карту, яку в силу зробленого припущення можна правильно розфарбувати двома фарбами, наприклад чорною та білою. Математична індукція є основою одного з найпоширеніших методів математичних доказів. З його допомогою можна довести більшу частину формул з натуральними числами n , наприклад, формулу знаходження суми перших членів прогресії S n = 2 a 1 + n - 1 d 2 · n формулу бінома Ньютона a + b n = C n 0 · a n · C n 1 · a n - 1 · b +. . . + C n n - 1 · a · b n - 1 + C n n · b n . У першому пункті ми розберемо основні поняття, потім розглянемо основи самого методу, а потім розповімо, як за його допомогою доводити рівність та нерівність. Yandex.RTB R-A-339285-1 Спочатку розглянемо, що таке взагалі індукція і дедукція. Визначення 1 Індукція- це перехід від приватного до загального, а дедукціянавпаки – від загального до часткового. Наприклад, у нас є твердження: 254 можна поділити на два націло. З нього ми можемо зробити безліч висновків, серед яких будуть як справжні, так і хибні. Наприклад, твердження, що всі цілі числа, які мають наприкінці цифру 4 , можуть ділитися на два без залишку - істинне, а те, що будь-яке число із трьох знаків ділиться на 2 - хибне. Загалом можна сказати, що з допомогою індуктивних міркувань можна отримати безліч висновків з одного відомого чи очевидного міркування. Математична індукція дає нам змогу визначити, наскільки справедливі ці висновки. Припустимо, ми маємо послідовність чисел виду 1 1 · 2 , 1 2 · 3 , 1 3 · 4 , 1 4 · 5 , . . . , 1 n (n + 1) , де n означає деяке натуральне число. У такому разі при складанні перших елементів послідовності ми отримаємо наступне: S 1 = 1 1 · 2 = 1 2 , S 2 = 1 1 · 2 + 1 2 · 3 = 2 3 , S 3 = 1 1 · 2 + 1 2 · 3 + 1 3 · 4 = 3 4 , S 4 = 1 1 · 2 + 1 2 · 3 + 1 3 · 4 + 1 4 · 5 = 4 5 , . . . Використовуючи індукцію, можна дійти невтішного висновку, що S n = n n + 1 . У третій частині ми доведемо цю формулу. В основі цього лежить однойменний принцип. Він формулюється так: Визначення 2 Якесь твердження буде справедливим для натурального значення n тоді, коли 1) воно буде вірним при n = 1 і 2) з того, що цей вираз справедливий для довільного натурального n = k , слід, що воно буде вірним і при n = k + 1 . Застосування методу математичної індукції здійснюється у 3 етапи: Візьмемо приклад, про який ми говорили раніше. Приклад 1 Доведіть формулу S n = 1 1 · 2 + 1 2 · 3 +. . . + 1 n (n + 1) = n n + 1 . Рішення
Як ми вже знаємо, для застосування методу математичної індукції треба виконати три послідовні дії. Ми можемо представити k + 1 як сума перших членів вихідної послідовності і k + 1: S k + 1 = S k + 1 k + 1 (k + 2) Оскільки в другій дії ми отримали, що S k = k k + 1 можна записати наступне: S k + 1 = S k + 1 k + 1 (k + 2). Тепер виконуємо необхідні перетворення. Нам потрібно виконати приведення дробу до спільного знаменника, приведення подібних доданків, застосувати формулу скороченого множення та скоротити те, що вийшло: S k + 1 = S k + 1 k + 1 (k + 2) = k k + 1 + 1 k + 1 (k + 2) = = k (k + 2) + 1 k + 1 (k + 2) = k 2 + 2 k + 1 k + 1 (k + 2) = (k + 1) 2 k + 1 (k + 2) = k + 1 k + 2 Таким чином, ми довели рівність у третьому пункті, виконавши всі три кроки методу математичної індукції. Відповідь:припущення про формулу S n = n n + 1 є вірним. Візьмемо більш складне завдання із тригонометричними функціями. Приклад 2 Наведіть доказ тотожності cos 2 α · cos 4 α · . . . · cos 2 n α = sin 2 n + 1 α 2 n sin 2 α. Рішення
Як ми пам'ятаємо, першим кроком має бути перевірка вірності рівності при n, що дорівнює одиниці. Щоб це з'ясувати, треба згадати основні тригонометричні формули. cos 2 1 = cos 2 α sin 2 1 + 1 α 2 1 sin 2 α = sin 4 α 2 sin 2 α = 2 sin 2 α · cos 2 α 2 sin 2 α = cos 2 α Отже, при n рівному одиниці, тотожність буде вірним. Тепер припустимо, що його справедливість збережеться за n = k , тобто. буде вірно, що cos 2 α · cos 4 α · . . . · cos 2 k α = sin 2 k + 1 α 2 k sin 2 α. Доводимо рівність cos 2 α · cos 4 α · . . . · cos 2 k + 1 α = sin 2 k + 2 α 2 k + 1 sin 2 α для випадку, коли n = k + 1, взявши за основу попереднє припущення. Згідно з тригонометричною формулою, sin 2 k + 1 α · cos 2 k + 1 α = = 1 2 (sin (2 k + 1 α + 2 k + 1 α) + sin (2 k + 1 α - 2 k + 1 α)) = = 1 2 sin (2 · 2 k + 1 α) + sin 0 = 1 2 sin 2 k + 2 α Отже, cos 2 α · cos 4 α · . . . · cos 2 k + 1 α = = cos 2 α · cos 4 α · . . . · cos 2 k α · cos 2 k + 1 α = = sin 2 k + 1 α 2 k sin 2 α · cos 2 k + 1 α = 1 2 · sin 2 k + 1 α 2 k sin 2 α = sin 2 k + 2 α 2 k + 1 sin 2 α Приклад розв'язання задачі на доказ нерівності із застосуванням цього методу ми навели у статті про метод найменших квадратів. Прочитайте той пункт, де виводяться формули для знаходження коефіцієнтів апроксимації. Якщо ви помітили помилку в тексті, будь ласка, виділіть її та натисніть Ctrl+Enter
а) 
;
б) 
.
, отримаємо
1/3 = 1/3. Нехай має місце рівність P(n):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.
і покажемо, що тоді має місце і(1 + a) n + 1 ≥ 1 + (n+ 1) a. (1 + a) n ≥ 1 + n a (1)
= 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) справедливо. Нерівність доведена.
і доведемо, що
враховуючи P(n), отримаємо 
, випливає, що
Суть методу математичної індукції
Метод математичної індукції у вирішенні завдань на
парне. Отже, парність доведена при n=1, з парності виведено парність 
.Отже, парно при всіх натуральних значеннях n.
Застосування методу математичної індукції до
, n – натуральне число.
.
.
. Покажемо, що 
.
.
.
. Тоді
.
, .
, тобто. 
.
.
. Твердження доведено.
, де >-1, n - натуральне число, більше 1.
. (1)
. (2)
. (9)
сторона правильного шістнадцятикутника 
сторона правильного тридцятидвокутника 
. Можна припустити тому, що сторона правильного 2 n - косинця при будь-якому рівні
. (1)
,
Поняття індукції та дедукції
У чому полягає метод математичної індукції
Як застосовувати метод математичної індукції при розв'язанні нерівностей та рівнянь