Метод математичної індукції n n 1. Приклади індукції

Вступ

Основна частина

Повна та неповна індукція
Принцип математичної індукції
Метод математичної індукції
Рішення прикладів
Рівності
Розподіл чисел
Нерівності

Висновок

Список використаної літератури

Вступ

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

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

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

Але це так важливо - вміти розмірковувати індуктивно.

Основна частина

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

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

4=2+2; 6=3+3; 8=5+3; 10=7+3; 12=7+5;

14=7+7; 16=11+5; 18=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

3 3 -1=26 ділиться на 26

Припустимо, що з n=k

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 маємо

3 7 /2 7 = 2187/128> 14 = 2 '7

нерівність вірна.

Припустимо, що з n=k

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.

p align="justify"> Метод доказу, про який йтиметься в даному пункті, заснований на одній з аксіом натурального ряду.

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

Символічний запис аксіоми:

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

Отже, щоб довести істинність пропозиції А,можна спочатку довести два твердження: істинність висловлювання А( 1), а також слідство А(к) => А(до+ 1).

Враховуючи сказане вище, опишемо сутність методу

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

Нехай потрібно довести, що пропозиція А(п)вірно для всіх натуральних п.Доказ розбивається на два етапи.

1-й етап. Основа індукції.Беремо як значення пчисло 1 і перевіряємо, що А( 1) є справжнє висловлювання.
2-й етап. Індуктивний перехід.Доводимо, що за будь-якої натуральної кількості довірна імплікація: якщо А(до), то А(до+ 1).

Індуктивний перехід починається словами: «Візьмемо довільне натуральне число до,таке, що А(к)»,або «Нехай для натурального числа довірно А(к)».Замість слова "нехай" часто кажуть "припустимо, що...".

Після цих слів буква допозначає фіксований об'єкт, для якого виконується співвідношення А(к).Далі з А(к)виводимо слідства, тобто будуємо ланцюжок речень А(к) 9 Р, Pi, ..., Р„ = А(до+ 1), де кожна пропозиція Р,є справжнім висловом чи наслідком попередніх речень. Останнє речення Р„має збігатися з А(до+ 1). Звідси укладаємо: з А(к)слід А(до+).

Виконання індуктивного переходу можна розчленувати на дві дії:

1) Індуктивне припущення. Тут ми припускаємо, що А дозмінної н.
2) На основі припущення доводимо, що АЧи правильно для числа? +1.

Приклад 5.5.1.Доведемо, що число п+пє парним при всіх натуральних п.

Тут А(п) = «п 2+п- парне число". Потрібно довести, що А -тотожно правдивий предикат. Застосуємо метод математичної індукції.

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

Сформулюємо індуктивне припущення А(к)= «Число до 2 + до -парне». Можна сказати так: «Візьмемо довільне натуральне число дотаке, що до 2+кє парне число».

Виведемо звідси твердження А(кА-)= «Число (До + 1) 2+(?+1) – парне».

За властивостями операцій виконаємо перетворення:

Перший доданок отриманої суми парно за припущенням, друге парно за визначенням (оскільки має вигляд 2 д).Отже, сума є парне число. Пропозиція А(до+ 1) доведено.

За методом математичної індукції робимо висновок: речення А(п)вірно для всіх натуральних п.

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

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

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

Приклад 5.5.2.Доведемо, що число 15 2і_| +1 ділиться на 8 при всіх натуральних п.

Бача індукції.Візьмемо /1=1. Маємо: число 152|_| +1 = 15 +1 = 16 поділяється на число 8.

, що для деякого

натурального числа доЧисло 15 2 * '+1 ділиться на 8.

Доведемо, що тоді число а= 15 2 (ЖН +1 ділиться 8.

Перетворимо число а:

За припущенням, число 15 2А1 +1 ділиться на 8, отже, все перше доданок ділиться на 8. Друге доданок 224 = 8-28 також ділиться на 8. Таким чином, число аяк різницю двох чисел, кратних 8, ділиться на 8. Індуктивний перехід обгрунтований.

На основі методу математичної індукції укладаємо, що для всіх натуральних пЧисло 15 2 "-1 - * -1 ділиться на 8.

Зробимо деякі зауваження щодо вирішеного завдання.

Доведене твердження можна сформулювати трохи інакше: «Число 15”+1 ділиться на 8 за будь-яких непарних натуральних /і».

По-друге, із доведеного загального твердження можна зробити окремий висновок, доказ якого може бути дано як окреме завдання: число 15 2015 +1 ділиться на 8. Тому іноді буває корисно узагальнити завдання, позначивши якесь конкретне значення буквою, а потім застосувати метод математичної індукції.

У найзагальнішому розумінні термін «індукція» означає, що з урахуванням приватних прикладів роблять загальні висновки. Наприклад, розглянувши деякі приклади сум парних чисел 2+4=6, 2+8=10, 4+6=10, 8+12=20, 16+22=38, робимо висновок у тому, що сума будь-яких двох парних чисел є парне число.

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

Приклад 5.5.3. Розглянемо число а= /г+я+41 при натуральному /?

Знайдемо значення апри деяких значеннях п.

Нехай п= I. Тоді а = 43 - просте число.

Нехай / 7 = 2. Тоді а= 4+2+41 = 47 – просте.

Нехай л = 3. Тоді а= 9+3+41 = 53 – просте.

Нехай / 7 = 4. Тоді а= 16 +4 +41 = 61 - просте.

Візьміть як значення пнаступні за четвіркою числа, наприклад 5, 6, 7, і переконайтеся, що число абуде простим.

Робимо висновок: «При всіх натуральних/? число абуде простим».

В результаті вийшло хибне висловлювання. Наведемо контрприклад: / 7 = 41. Переконайтеся, що при цьому пчисло абуде складним.

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

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

Отже, за визначенням а п+ = а п + d,при п> 1.

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

Якщо /7=1, то З 7| = Я |, тобто Я | = tf|+df(l -1).

Якщо /7=2, то я 2 = a+d,тобто а= Я | + * / (2-1).

Якщо /7 = 3, то я 3 = я 2 + = (a+d)+d = a+2d,тобто я 3 = Я | + (3-1).

Якщо /7 = 4, то я 4 = я 3 + * / = ( a+2d)+d= Я1 +3 і т.д.

Наведені приклади дозволяють висунути гіпотезу: формула загального члена має вигляд а„ = a+(n-)dвсім /7>1.

Доведемо цю формулу методом математичної індукції.

База індукціїперевірено у попередніх міркуваннях.

Нехай до -такий номер, за якого я* - a+(k-)d (індуктивне припущення).

Доведемо, Що я * +! = a+((k+)-)d,тобто я * +1 = a x +kd.

За визначенням я*+1 = аь+d. а до= я | +(до-1 )dотже, ац+= я i + (А:-1) ^ / + с / = я | +(А-1+1 )d= я i +kd, що потрібно було довести (для обгрунтування індуктивного переходу).

Тепер формула я„ = a+(n-)dдоведена для будь-якого натурального номера/;.

Нехай дана деяка послідовність я я 2, я,„ ... (не

обов'язково арифметична чи геометрична прогресія). Часто виникають завдання, де потрібно підсумовувати перші пчленів цієї послідовності, тобто встановити суму Я|+я 2 +...+я і формулою, яка дозволяє знаходити значення цієї суми, не обчислюючи члени послідовності.

Приклад 5.5.5. Доведемо, що сума перших пнатуральних чисел дорівнює

/?(/7 + 1)

Позначимо суму 1+2+...+/7 через S n.Знайдемо значення S nдля деяких /7.

Зауважимо: щоб знайти суму S 4 , можна скористатися обчисленим раніше значенням 5 3 , оскільки 5 4 = 5 3 +4.

п(п +1)

Якщо підставити розглянуті значення /? в терм-то

отримаємо, відповідно, самі суми 1, 3, 6, 10. Ці спостереження

. _ п(п + 1)

наштовхують на думку, що формулу S„=--- можна використовувати при

будь-якому //. Доведемо цю гіпотезу методом математичної індукції.

База індукціїперевірено. Виконаємо індуктивний перехід

Припустимо, що формула вірна для деякого натурального числа

, до(до + 1)

до, то мережа сума перших донатуральних чисел дорівнює ----.

Доведемо, Що сума перших (? +1) натуральних чисел дорівнює

(* + !)(* + 2)

Виразимо?*+1 через S k .Для цього у сумі S*+i згрупуємо перші дододанків, а останній доданок запишемо окремо:

За індуктивним припущенням S k =Отже, щоб знайти

суму перших (?+1) натуральних чисел, достатньо вже обчисленої

. „ до(до + 1) _ .. ..

сумі перших дочисел, що дорівнює ---, додати один доданок (к+1).

Індуктивний перехід обґрунтовано. Тим самим висунута спочатку гіпотеза доведена.

Ми навели доказ формули S n =п^п+ методом

математичної індукції. Звісно, є й інші докази. Наприклад, можна записати суму S,у порядку зростання доданків, а потім у порядку спадання доданків:

Сума доданків, що стоять в одному стовпці, постійна (в одній сумі кожне наступне доданок зменшується на 1, а в іншій збільшується на 1) і дорівнює (/г+1). Тому, склавши отримані суми, матимемо пдоданків, рівних (і+1). Отже, подвоєна сума S„дорівнює п(п+ 1).

Доведена формула може бути отримана як окремий випадок формули суми перших пчленів арифметичної прогресії.

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

Приклад 5.5.6. «Докажемо» пропозицію: «Число 7"+1 ділиться на 3 за будь-якого натурального я».

«Припустимо, що за деякого натурального значення дочисло 7*+1 ділиться на 3. Доведемо, що число 7 ж +1 ділиться на 3. Виконаємо перетворення:

Число 6 очевидно ділиться на 3. Число 1 до +ділиться на 3 за індуктивним припущенням, отже, число 7-(7* + 1) також ділиться на 3. Тому різниця чисел, що діляться на 3, також ділитися на 3.

Пропозиція доведена».

Доказ вихідної пропозиції неправильний, незважаючи на те, що індуктивний перехід виконаний правильно. Справді, за п= I маємо число 8, при п=2 -число 50 ... і жодне з цих чисел нс ділиться на 3.

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

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

Приклад 5.5.7. Знайдемо значення суми

У завданні змінна пне фігурує. Однак розглянемо послідовність доданків:

Позначимо S = а+а 2 +...+а„.Знайдемо S„ при деяких п.Якщо / 1 = 1, то S, = а, =-.

Якщо п= 2. то S, = а, + а? = - + - = - = -.

Якщо /? = 3, то S-, = a,+a 7+ я, = - + - + - = - + - = - = -.

3 1 - 3 2 6 12 3 12 12 4

Можете самостійно обчислити значення S„за /7 = 4; 5. Виникає

природне припущення: S n= - за будь-якого натурального /7. Доведемо

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

База індукціїперевірено вище.

Виконаємо індуктивний перехід, позначаючи довільно взяте

значення змінної пцією ж літерою, тобто доведемо, що з рівності

0 /7 _ /7 +1

S n=-Слідує рівність S, =-.

/7+1 /7 + 2

Припустимо,що вірна рівність S= - П -.

Виділимо у сумі S„+перші пдоданків:

Застосувавши індуктивне припущення, отримаємо:

Скорочуючи дріб на (/7+1), матимемо рівність S n +1 - , Л

Індуктивний перехід обґрунтовано.

Тим самим доведено, що сума перших пдоданків

1 1 1 /7 ^
- +-+...+- дорівнює -. Тепер повернемося до первісної
1-2 2-3 /?(// +1) /7 + 1

задачі. Для її вирішення достатньо взяти як значення пЧисло 99.

Тоді сума -!- + -!- + -!- + ...+ --- дорівнюватиме 0,99.

1-2 2-3 3-4 99100

Постарайтеся обчислити цю суму в інший спосіб.

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

Нехай змінна/? позначає кількість цих функцій. У разі, коли дано лише одну функцію, під сумою розуміється саме ця функція. Тож якщо /7=1, то твердження очевидно істинно:/" = /".

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

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

у вигляді g+f„+ 1, де g=f +/г + ... +/ t -сума пфункцій. За індуктивним припущенням похідна функції gдорівнює сумі похідних: g" = ft +ft + ... +ft.Тому має місце наступний ланцюжок рівностей:

Індуктивний перехід виконано.

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

Нерідко потрібно довести істинність пропозиції А(п)для всіх натуральних я, починаючи з деякого значення с.Доказ методом математичної індукції у разі проводиться за наступною схемою.

Основа індукції.Доводимо, що пропозиція Авірно для значення п,рівного с.

Індуктивний перехід. 1) Припускаємо, що пропозиція Авірно для деякого значення дозмінної /?, яке більше чи одно с.

2) Доводимо, що пропозиція Аістинно значення /?, рівного

Знову зауважимо, що замість літери дочасто залишають позначення змінної п.І тут індуктивний перехід починають словами: «Припустимо, що з деякого значення п>свірно А(п).Доведемо, що тоді правильно А(п+) 1)».

Приклад 5.5.9. Доведемо, що за всіх натуральних п> 5 вірна нерівність 2” > та 2 .

Основа індукції.Нехай п= 5. Тоді 25 = 32, 52 = 25. Нерівність 32> 25 істинна.

Індуктивний перехід. Припустимо, що має місце нерівність 2 П >п 2для деякого натурального числа п> 5. Доведемощо тоді 2" +| > (п+1) 2 .

За властивостями ступенів 2”+| = 2-2". Так як 2">я 2 (за індуктивним припущенням), то 2-2" > 2я 2 (I).

Обґрунтуємо, що 2 п 2більше (я+1) 2 . Це можна зробити різними способами. Достатньо вирішити квадратна нерівність 2х 2 >(х+) 2у багатьох дійсних чисел і побачити, що це натуральні числа, великі чи рівні 5, є його рішеннями.

Ми вчинимо так. Знайдемо різницю чисел 2 п 2та (я+1) 2:

Так як і > 5, то я+1 > 6, отже, (я+1) 2 > 36. Тому різниця більша за 0. Отже, 2я 2 > (я+1) 2 (2).

За властивостями нерівностей з (I) і (2) випливає, що 2*2" > (я+1) 2 , що потрібно довести для обгрунтування індуктивного переходу.

На основі методу математичної індукції укладаємо, що нерівність 2" > я 2 істинно для будь-яких натуральних чисел я.

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

1) припустити, що пропозиція А(п)вірно при всіх значеннях змінної я, менших деякого числа р;
2) з висунутого припущення вивести, що пропозиція А(п)справедливо і для числа нар.

Таким чином, індуктивний перехід вимагає доказу слідства: [(Уї?) А(п)] => А(р).Зауважимо, що слідство можна переписати у вигляді: [(Уп^р) А(п)] => А(р+ 1).

У початковому формулюванні методу математичної індукції за доказом пропозиції А(р)ми спиралися лише на «попередню» пропозицію А(р- 1). Дане тут формулювання методу дозволяє виводити А(р),вважаючи, що всі пропозиції А(п),де я менший р, Істинні.

Приклад 5.5.10. Доведемо теорему: «Сума внутрішніх кутів будь-якого я-кутника дорівнює 180 ° (я-2)».

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

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

Замість змінної // можна підставляти будь-які натуральні числа, які більші або рівні 3. Для п=Ътеорема справедлива, оскільки у трикутнику сума кутів дорівнює 180 °.

Візьмемо деякий /7-кутник (Р> 4) і припустимо, що сума кутів будь-якого //-кутника, де // р дорівнює 180 ° (/ / -2). Доведемо, що сума кутів //-кутника дорівнює 180 ° (/ / -2).

Проведемо діагональ //-кутника, що лежить усередині нього. Вона розіб'є //-кутник на два багатокутники. Нехай один із них має досторін, інший - до 2сторін. Тоді до+к 2 -2 = р,оскільки отримані багатокутники мають загальною стороною проведену діагональ, яка є стороною вихідного //-угольника.

Обидва числа доі до 2менше //. Застосуємо отримані багатокутники індуктивне припущення: сума кутів А]-кутника дорівнює 180°-(?i-2), а сума кутів? 2 -кутника дорівнює 180 ° - (Аг 2 -2). Тоді сума кутів //-кутника дорівнюватиме сумі цих чисел:

180°*(Аг|-2)-н 180°(Аг2-2) = 180 про (Аг,-ьАг 2 -2-2) = 180°-(//-2).

Індуктивний перехід обґрунтовано. За підсумками методу математичної індукції теорема доведено будь-якого //-угольника (//>3).

Якщо пропозиція А(n) істинно при n=p і якщо А(k) Ю А(k+1) для будь-якого k>p, то пропозиція А(n) істинно для будь-якого n>p.

Довести, що 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 =3(3-3)/2=0 діагоналей; А 2 А(3) істинно

2) Припустимо, що у кожному опуклому k-кутнику має А 1 ся А k =k(k-3)/2 діагоналей. А k Доведемо, що тоді у опуклому А k+1 (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

Таким чином,

Gk+1 = Gk+(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

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)

Довести, що

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.

Довести, що (11 n+2 +12 2n+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. З методу математичної індукції твердження доведено.

Довести, що 33n-1+24n-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 +2 4k-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 1 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) без залишку

Попередньо доведемо, що 3 3n+3 -1 ділиться на 26 без залишку

1. При n=0
3 3 -1=26 ділиться на 26
2. Припустимо, що з n=k
3 3k+3 -1 поділяється на 26
3. Доведемо, що твердження правильне за 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). На підставі принципу математичної індукції можна стверджувати, що нерівність Бернуллі справедлива для будь-якого n>2

Довести, що справедлива нерівність (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

Перепишемо нерівність у вигляді (3/2) n >2n

1. При n=7 маємо 3 7 /2 7 =2187/128>14=2 ґ 7 нерівність вірна
2. Припустимо, що з n=k (3/2) k >2k
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
2. Припустимо, що з 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) Ы

Ы (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)

З методу математичної індукції нерівність доведено.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рішення.

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

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

Справді,

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

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

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

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

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

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

. ■ 

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

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

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

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

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

Тобто (1+
.■ 

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

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

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

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

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

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

Справді,

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

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

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

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

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

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

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

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

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

при
,

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

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

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

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

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

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

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

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

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

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

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

p align="justify"> Метод доказу, заснований на аксіомі Пеано 4, використовують для доказу багатьох математичних властивостей і різних тверджень. Основою цього служить наступна теорема.

Теорема. Якщо твердження А(n)з натуральною змінною nістинно для n = 1 і з того, що воно істинно для n = kслід, що воно істинно і для наступного числа n=k,те твердження А(n) n.

Доведення. Позначимо через Мбезліч тих і лише тих натуральних чисел, для яких твердження А(n)істинно. Тоді з умови теореми маємо: 1) 1 М; 2) k MkM. Звідси, на підставі аксіоми 4, укладаємо, що М =N, тобто. затвердження А(n)істинно для будь-якого натурального n.

Метод доказу, що ґрунтується на цій теоремі, називається методом математичної індукції,а аксіома – аксіомою індукції. Такий доказ складається із двох частин:

1) доводять, що затвердження А(n)істинно для n = А(1);

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

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

Доказ методом математичної індукції можна починати не тільки з підтвердження істинності твердження для n = 1, але і з будь-якого натурального числа m. У цьому випадку затвердження А(n)буде доведено для всіх натуральних чисел nm.

Завдання. Доведемо, що для будь-якого натурального числа істинна рівність 1 + 3 + 5 … + (2 n- 1) = n.

Рішення.Рівність 1 + 3 + 5 … + (2 n - 1) = nє формулою, за якою можна знаходити суму перших послідовних непарних натуральних чисел. Наприклад, 1 + 3 + 5 + 7 = 4 = 16 (сума містить 4 доданків), 1 + 3 + 5 + 7 + 9 + 11 = 6 = 36 (сума містить 6 доданків); якщо ця сума містить 20 доданків зазначеного виду, вона дорівнює 20= 400 тощо. Довівши істинність цієї рівності, отримаємо можливість знаходити за формулою суму будь-якого числа доданків зазначеного виду.

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

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

Розглянемо ліву частину останньої рівності.

За припущенням, сума перших kдоданків дорівнює kі тому 1 + 3 + 5 + … + (2 k- 1) + (2(k + 1) - 1) = 1 + 3 + 5 + … + (2k- 1) + (2k+ 1)=

= k+(2k + 1) = k+ 2k + 1. Вираз k+ 2k + 1 тотожно дорівнює виразу ( k + 1).

Отже, істинність даної рівності для n = k + 1 доведено.

Таким чином, дана рівність істинна для n = 1 і з істинності його для n = kслід істинність для n = k + 1.

Тим самим доведено, що ця рівність є істинною для будь-якого натурального числа.

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

Завдання. Довести, що , де nN.

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

Припустимо, що нерівність вірна при n = k,тобто. - Справжня нерівність. Доведемо, виходячи з припущення, що воно правильне і при n = k + 1, тобто. (*).

Перетворимо ліву частину нерівності (*), враховуючи, що : .

Але , значить і .

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

Тим самим, використовуючи аксіому 4, ми довели, що ця нерівність є істинною для будь-якого натурального числа.

Методом математичної індукції можна довести інші твердження.

Завдання. Довести, що з будь-якого натурального числа істинно твердження .

Рішення. Перевіримо істинність затвердження при n = 1: -Справжнє висловлювання.

Припустимо, що це твердження правильне при n = k: . Покажемо, використовуючи це, істинність затвердження при n = k + 1: .

Перетворимо вираз: . Знайдемо різницю kі k+ 1 членів. Якщо виявиться, що отримана різниця кратна 7, а за припущенням віднімається ділиться на 7, то і кратно, що також зменшується 7:

Твір кратно 7, отже, і .

Таким чином, це твердження є істинним для n = 1 і з істинності його для n = kслід істинність для n = k + 1.

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

Завдання. Довести, що для будь-якого натурального числа n 2 істинно твердження (7-1)24.

Рішення. 1) Перевіримо істинність затвердження при n= 2: - Справжнє висловлювання.