Розв'зування задач методом математичної індукції

2

Курсова робота

РОЗВ'ЗУВАННЯ ЗАДАЧ

МЕТОДОМ МАТЕМАТИЧНОЇ ІНДУКЦІЇ

 Івано-Франківськ

2008

ПЛАН

ВСТУП

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

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

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

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

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

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

ЛІТЕРАТУРА

ВСТУП

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

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

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

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

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

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

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

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

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

1=1=1²;

1+3=4=2²;

1+3+5=9=3²;

1+3+5+7=16=4²;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЛІТЕРАТУРА

1. Алгебра и начала анализа (система проведения занятий на подготовительных отделениях вузов): Учеб. пособие для подготовительных отделений вузов / В.С. Кра-мор - М.: Высш. школа, 1981. - 336 с., ил.

2. Александров Б.И., Максимов В.М., Лурье М.В., Колесниченко А.В. Пособие по математике для поступающих в вузы. Изд-во МГУ, 1972.

3. Большая советская энциклопедия / Гл. Ред. Б.А. Введенский. - 2-е изд. - Большая советская энциклопедия, Т. 18. Индекс - истон. 1953. - 620 с.: ил.

4. Виленкин Н.Я. и др. Алгебра и математический анализ для 10 класса: Учеб. пособие для учащихся шк. и классов с углубл. изуч. математики. - 3-е изд., дораб. - М.: Просвещение, 1992. - 335 с.: ил. - ISBN 5-09-003839-2.

5. Галицкий М.Л., Гольдман А.М., Звавич Л.И. Сборник задач по алгебре для 8-9 классов: Учеб. пособие для учащихся шк. и классов с углубл. изуч. курса математики. - М.: Просвещение, 1992. - 271 с.: ил. - ISBN 5-09-003875-9.

6. Галкин Е.В. Нестандартные задачи по математике: Задачи логического харак-тера: Кн. для учащихся 5-11 кл. М.: Просвещение; Учебная литература, 1996. - 160 с.: ил. - ISBN 5-09-007092-Х.

7. Говоров В.М., Дыбов П.Т., Мирошин С.Ф. Сборник конкурсных задач по ма-тематике (с методическими указаниями и решениями). - М.: Наука, Главная редакция физико-математической литературы, 1983. - 384 с.

8. Головина Л.И., Яглом И.М. Индукция в геометрии. Популярные лекции по математике, вып. 21. - М.: Физматгиз, 1961. - 100 с.: ил.

9. Дорофеев Г.В., Потапов М.К., Розов Н.Х. Пособие по математике для посту-пающих в вузы. - М.: Наука, Главная редакция физико-математической литературы, 1972. - 528 с.

10. Задачи повышенной трудности по алгебре и началам анализа: Учеб. пособие для 10-11 кл. сред. шк. / Б.М. Ивлев, А.М. Абрамов, Ю.П. Дудницын, С.И. Шварц-бурд. - М.: Просвещение, 1990. - 48 с.: ил. : ISBN 5-09-003597-0.

11. Каганов Э.Д. 400 самых интересных задач с решениями по школьному курсу математике для 6-11 классов. - М. - ЮНВЕС. - 1997. - 288 с. ISBN 5-88682-029-9.

12. Колмогоров А.Н., Шварцбурд С.И. Алгебра и начала анализа. Метод мате-матической индукции // Математика в школе - 1975. - № 1 - с. 8 -14.

13. Коровин П.П. Неравенства. Популярные лекции по математике, вып. 5. - М.: Наука, Главная редакция физико-математической литературы, 1974. - 72 с.: ил.

14. Мордкович А.Г. Алгебра и начала анализа.: Учеб. пособие для подготови-тельных отделений вузов. - М.: Высш. Школа, 1979. - 400 с., ил.

15. Пособие по математике для поступающих в вузы / под ред. Яковлева Г.Н. - М.: Наука, Главная редакция физико-математической литературы, 1985. - 480 с.

16. Родосский К.А. Обобщённая форма полной математической индукции // Ма-тематика в школе - 1975. - № 1 - c. 8.

17. Соминский И.С. Метод математической индукции. Популярные лекции по математике, вып. 3. - М.: Наука, Главная редакция физико-математической литера-туры, 1965. - 56 с.: ил.

18. Соминский И.С., Головина Л.И., Яглом И.М. О математической индукцц. - М.: Наука, Главная редакция физико-математической литературы, 1967. - 144 с.: ил.

19. Шарыгин И.Ф. Факультативный курс по математике: Решение задач: Учеб. пособие для 10 кл. сред. шк. - М.: Просвещение, 1989. - 252с.: ил.: ISBN 5-09-001288-1.

20. Энциклопедический словарь юного математика / Сост. - М.: Педагогика, 1989. - 352 с.: ил.