Метод математичної індукції та її застосування до вирішення завдань. Приклади індукції Метод математичної індукції: приклади розв'язання
Відеоурок «Метод математичної індукції» допомагає освоїти метод математичної індукції. Відео містить матеріал, що допомагає зрозуміти суть методу, запам'ятати особливості його застосування, навчиться застосовувати цей метод під час вирішення завдань. Мета даного відеопосібника – полегшити освоєння матеріалу, формувати вміння вирішувати математичні завдання методом індукції.
Для утримання уваги учнів вивчення матеріалу використовуються анімаційні ефекти, ілюстрації, подання інформації у кольорі. Відеоурок звільняє час вчителя на уроці для покращення якості індивідуальної роботи, вирішення інших навчальних завдань.
Поняття методу математичної індукції вводиться з прикладу розгляду послідовності a n , у якій a 1 =4, а a n+1 = a n +2n+3. Відповідно до загального подання члена послідовності, визначається, що a 1 =4, a 2 =4+2·1+3=9, a 3 =9+2·2+3=16, тобто послідовність чисел 4, 9, 16,… Передбачається, що з даної послідовності правильно a n =(n+1) 2 . Для зазначених членів послідовності – першого, другого, третього – формула вірна. Необхідно довести справедливість даної формули для будь-якого скільки завгодно великого n. Вказується, що у подібних випадках застосовується метод математичної індукції, що допомагає довести твердження.
Розкривається суть методу. Передбачається справедливість формули для n=k значення a k =(k+1) 2 . Необхідно довести, що рівність буде справедливою також за k+1, що означає a k +1 =(k+2) 2 . Для цього у формулі a k +1 = a k +2k+3 замінюємо a k (k+1) 2 . Після підстановки та приведення подібних одержуємо рівність a k +1 =(k+2) 2 . Це дає право стверджувати, що справедливість формули для n робить її вірною і n=k+1. Розглянутий доказ стосовно послідовності a n , яка представлена числами 4, 9, 16,… і загальним членом a n =(n+1) 2 дає право стверджувати, якщо формула перетворюється на правильну рівність для n=1, то також для n=1+ 1=2 і для 3 і т.д., тобто при всякому натуральному n.
Далі суть методу індукції викладається математичною мовою. Принцип методу заснований на справедливості твердження, що факт має місце для довільного натурального n при виконанні двох умов: 1) твердження є правильним для n=1 2) із справедливості даної формули для n=k слід справедливість її для n=k+1. З цього принципу випливає і будова підтвердження, з допомогою методу математичної індукції. Зазначається, що це метод передбачає для n=1 доказ справедливості затвердження, а при припущенні справедливості докази для n=k доводиться, що також n=k+1.
Розбирається приклад підтвердження формули Архімеда шляхом математичної індукції. Дано формулу 1 2 +2 2 +3 2 +…+n 2 =n(n+1)(2n+1)/6. На екрані проводяться обчислення, що виводять справедливість формули n=1. Другим пунктом доказу є припущення, що для n=k формула справедлива, тобто вона набуває вигляду 1 2 +2 2 +3 2 +…+k 2 =k(k+1)(2k+1)/6.Грунтуючись на цьому , Доводиться, що формула правильна і для n=k+1. Після підстановки n=k+1 отримуємо значення формули 1 2 +2 2 +3 2 +…+k 2 +(k+1) 2 =(k+1)(k+2)(2k+3)/6. Отже, формула Архімеда доведено.
Ще одному прикладі розглядається доказ кратності 7 суми 15 n +6 для всякого натурального n. У доказі користуємося методом математичної індукції. Спочатку справедливість затвердження перевіряємо для n=1. Справді, 151+6=21. Потім допускаємо справедливість n=k. Це означає, що 15 k +6 є кратним 7. Підстановкою n=k+1 формулу доводимо кратність 7 значення 15 k +1 +6. Після перетворення виразу отримуємо: 15 k +1 +6 = 15 k +1 · 14 + (15 k +6). Тому сума 15 n +6 є кратною 7.
Відеоурок «Метод математичної індукції» дохідливо та детально розкриває суть та механізм застосування методу математичної індукції у доказі. Тому цей відеоматеріал може послужити не лише наочним посібником на уроці алгебри, але буде корисним при самостійному вивченні матеріалу учнем, допоможе пояснити тему вчителю під час дистанційного навчання.
Бібліографічний опис:Баданін А. С., Сізова М. Ю. Застосування методу математичної індукції до розв'язання задач на подільність натуральних чисел // Юний вчений. 2015. №2. С. 84-86..04.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) всім значень змінної часто вдається провести методом математичної індукції, заснований на наступному принципі.
Пропозиція А(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 - парне число, то й 
парне. Отже, парність доведена при n=1, з парності виведено парність 
.Отже, парно при всіх натуральних значеннях n.
приклад 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 – натуральне число.
Рішення.
При 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.Довести, що 
, де >-1, n - натуральне число, більше 1.
Рішення.
При n=2 нерівність справедлива, оскільки .
Нехай нерівність справедлива за n=k, де k - деяке натуральне число, тобто.
. (1)
Покажемо, що тоді нерівність справедлива і за n=k+1, тобто.
. (2)
Дійсно, за умовою, тому справедлива нерівність
, (3)
отримане з нерівності (1) множенням кожної частини його на . Перепишемо нерівність (3) так: . Відкинувши у правій частині останньої нерівності позитивний доданок, отримаємо справедливу нерівність (2).
приклад 4.Довести, що
(1)
де , , n – натуральне число, більше 1.
Рішення.
При n=2 нерівність (1) набуває вигляду
. (2)
Оскільки , то справедлива нерівність
. (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) маємо добуток двох негативних чисел. В обох випадках нерівність (9) є справедливою.
Цим доведено, що із справедливості нерівності (1) при n=k випливає його справедливість за n=k+1.
Метод математичної індукції застосування до інших
завданням
Найбільш природне застосування методу математичної індукції в геометрії, близьке до використання цього методу теорії чисел і в алгебрі, - це застосування до вирішення геометричних завдань на обчислення. Розглянемо кілька прикладів.
приклад 1.Обчислити сторону правильного - косинця, вписаного в коло радіусу R.
Рішення.
При n=2 правильний 2 n - косинець є квадрат; його сторона. Далі, згідно з формулою подвоєння
знаходимо, що сторона правильного восьмикутника 
сторона правильного шістнадцятикутника 
сторона правильного тридцятидвокутника 
. Можна припустити тому, що сторона правильного 2 n - косинця при будь-якому рівні
. (1)
Припустимо, що сторона правильного вписаного - косинця виражається формулою (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 кіл. Видаливши одне з цих кіл, ми отримаємо карту, яку в силу зробленого припущення можна правильно розфарбувати двома фарбами, наприклад чорною та білою.
Урок №50
Тема урока : Метод математичної індукції
Мета уроку: Познайомитись зсутністю методу математичної індукції, навчитеся застосовувати цей метод при вирішенні завдань на доказ, продовжити розвиток обчислювальних навичок, продовжити формування математичної грамотності.
Хід уроку.
Організаційний момент. Постановка цілей уроку
Активізація опорних знань.
Визначення геометричної прогресії, формули n-го члена геометричної прогресії.
Повторити формулу суми перших членів арифметичної прогресії.
Повторити формулу суми геометричної прогресії, що нескінченно убуває.
3. Вивчення нового матеріалу
При вирішенні багатьох завдань, при доказі справедливості математичних речень, а також при виведенні формули часто використовується міркування, яке називаєтьсяметодом математичної індукції.
Таке міркування ви, наприклад, використовували під час виведення формулиn-го члена, а також при виведенні формули суми першихnчленів арифметичної та геометричної прогресій.
Сутність цього методу полягає в наступному: якщо треба встановити справедливість деякого твердження, в якій фігурує натуральне числоn, то:
1) перевіряється, що передбачуване твердження має місце для конкретного значенняn(наприклад дляn=1).
2) передбачається, що твердження справедливе при якомусь довільному значенніn = k , і доводиться, що в такому випадку воно справедливе і приn = k + 1. Звідси робиться висновок, що твердження справедливе за будь-якого значенняnбо справедливість його була виявлена приn=1, а по доведеному воно вірне і приn= 2, а якщо справедливо приn= 2, то справедливо і заn= 3 і т.д.
Тепер розглянемо приклади використання цього методу.
приклад 1. Доведемо, що за будь-якого натуральногоnмає місце рівність
Формула вірна дляn= 1, оскільки:
Припустимо, що формула вірна прип = k .
Доведемо, що в такому випадку вона вірна і приn = k+ 1, тобто.
Безпосередня перевірка показала, що формула правильна приn =1; отже, вона буде справедлива також заn= 2, а тому і приn= 3, отже, і прип = 4 і взагалі при будь-якому натуральномуn.
4.Рішення завдань
№249 (а)
У цьому завдання потрібно довести формулуn – гочлена арифметичної прогресії методом математичної індукції
Приn=1 маємо а 1 =а 1.
Припустимо, що ця формула вірна дляk-го члена, тобто має місце рівність а k = a 1 + d( k-1)
Доведемо, що в даному випадку ця формула вірна і для (k+1)-го члена. Справді,
а k +1 = a 1 + d( k+1-1) = а 1 + dk
З іншого боку, за визначенням ариф. прогр. а k +1 = а k + d
Оскільки ліві частини двох останніх виразів рівні = і праві рівні:
а k + d= а 1 + dkабо а k = a 1 + d( k-1)
Отримана правильна рівність дозволяє стверджувати, що формулаn-го члена арифметичної прогресії підходить для будь-якого натуральногоn
№ 255
Доведемо, що число 11 n+1 +12 2 n -1 при всіх натуральних значенняхnділитися на 133
Приn=1 маємо 11 1+1 +12 2*1-1 =133, 133 ділитися на 133
Припустимо, що заn= kсума 11 k +1 +12 2 k -1 ділитися на 133
Доведемо, що ця сума ділитися на 133n= k+1, тобто. 11 k +2 +12 2 k +1 ділитися на 133
11 k+2 +12 2k+1 =11*11 k +1 +144*12 k-1 =11*11 k +1 +11*12 2k-1 +133*12 2k-1 =11(11 k+1 +12 2k-1 )+133*12 2k-1
Кожен доданок отриманої суми поділяється на 133. Отже, 11 k +2 +12 2 k +1 теж ділити на 133.
5. Рефлексія
6. Постановка Д/з
§15 вирішити №251
Індукція є методом отримання загального затвердження з приватних спостережень. Якщо математичне твердження стосується кінцевого числа об'єктів, його можна довести, перевіряючи для кожного об'єкта. Наприклад, твердження: «Кожне двозначне парне число є сумою двох простих чисел,» – випливає із серії рівностей, які цілком реально встановити:
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 різних.
