asyan.org
добавить свой файл
1
МЕТОД МАТЕМАТИЧНОЇ ІНДУКЦІЇ
Математична індукція — це спосіб доведення нескінченної кількості занумерованих натуральними числами тверджень Т(n) за два ходи:

  1. база індукції: доводимо Т(1);

  2. крок індукції: доводимо, що для довільного k з істинності твердження
    Т(к) випливає істинність Т(k+1).





  1. Відомо, що а1 = 1, ап+1 = п + 1 при п1. Знайдіть ап.

Розв'язання

а2 = 3, а3 =7, а4 = 15, а5 = 31.

Помічаємо, що а1 = 21 – 1, а2 =22 – 1, а3 = 23 – 1, а4 = 24 – 1, а5 = 25 – 1.

Ви­никає гіпотеза аk = 2k – 1.

Перевіримо крок індукції: аk+1 2аk + 1 = 2(2k – 1) + 1 = 2k+1 – 1.

Отже, на основі принципу математичної індукції для кожного натурального n ап = 2n – 1.


  1. Доведіть, що при кожному натуральному п стверджується рів­ність

1 + 3 + 5 + ... + (2n – 1) = n2.

Розв'язання

Якщо п = 1, то1 = 12.

Припустимо, що при n = k, рівність 1 + 3 + 5 + ... + (2k – 1) = k2 правильна.

Якщо n = k + 1, то 1+3+...+(2k–1)+2(k+1)–1=k2+2(k+1)–1=(k+1)2.

Індуктивний перехід правильний, а тому рівність доведено.


  1. Доведіть, що для кожного натурального п вираз ділиться на 19.

Розв'язання

Якщо п = 1, то 53 – 22 + 33 – 23 ділиться на 19.

Нехай при п = k 52k+1 – 2k+1 + 3k+2 22k+1 ділиться на 19.

Доведемо, що при п = k+1 твердження також правильне, тобто, що

52k+3 2k+2 + 3k+3 – 22k+3 ділиться на 19.

52k+3 2k+3 + 3k+3 – 22k+3 = 50∙52k+1∙2k+1 + 12∙3k+222k+1 =

= 12(52k+1∙2k+1 +3k+22k+1) + 38∙52k+1∙2k+1.

Перший доданок суми ділиться на 19 за припущенням, другий дода­нок, очевидно, ділиться на 19, тому вся сума ділиться на 19. Отже, твер­дження задачі справедливе для всіх натуральних п.


  1. Доведіть, що для всіх натуральних п виконується нерівність .

Розв'язання

База індукції: при п = 1 маємо правильну нерівність .

Припустимо тепер, що нерівність справедлива при п = k, тобто .

Доведемо тепер, що нерівність справедлива при п = k + 1, тобто, що .

З урахуванням припущення індукції для цього досить довести нерівність .

Оскільки k > 1, то достатньо довести, що . Піднесемо цю нерівність до квадрата (ліва і права частини додатні): (2k+1)(2k+3) < 4k2 +8к+4.

Ця нерівність еквівалентна нерівності 3 < 4. На основі принципу математичної індукції робимо висновок, що твердження задачі справедливе для всіх натуральних п.


  1. Доведіть для кожного натурального п нерівність .

Розв'язання

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

За припущенням індукції, маємо: .

Доведемо, що або , що рівносильне

. Остання нерівність є очевидною, тому можна зробити висновок, що твердження задачі справджується для всіх натуральних п.
Є різні варіанти індукції. Іноді як крок треба перевірити, що твер­дження Т(п) справедливе, якщо справедливі всі попередні.


  1. Відомо, що ціле число. Доведіть, що при будь-якому натураль­ному п число теж ціле.

Розв'язання

ціле.

Припустимо, що при всіх пк ціле. Доведемо, що також ціле.

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


  1. Знайдіть цілу частину числа (2004 знаки кореня).

Розв'язання

Розглянемо цю задачу для випадку п радикалів. Позначимо задане число через ап. Нехай п = 2k+1.

База індукції: 1 < а 2к+1 < 2. Тоді при п =2k+3 маємо: .

Звідки або 1 < а2k+1 < 2. Таким чином, [а2k+3] = 1, а тому для непарних п маємо: [аn ] = 1.

Нехай тепер п = 2k.

База індукції: .

Крок індукції: припустимо, що 0 < а2k < 1. Тоді , звідки , 0 < а2k+2 < 1. Отже, [a2k+2] = 0.

Згідно з припущенням математичної індукції,

Тому [а2004] = 0.
Задачі для самостійного розв'язування

  1. Доведіть, що при всіх натуральних п:

а) ;

б) ;

в) ;

г) ;

д) .


  1. Доведіть, що при всіх натуральних п:

а) n3 + (n + 1)3 + (n + 2)3 ділиться на 9;

б) 4n + 6n – 1 ділиться на 9;

в) 32n+2 + 8n – 9 ділиться на 16;

г) 11n+2 + 122n+1 ділиться на 133;

д)2n ділиться на 3n+1.



  1. Обчисліть суми: а) 13 + 23 + ... +(2n)3; б) 13 + 33 + ... + (2n – 1)3.




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




  1. Доведіть, що для всіх п ≥ 2 виконується нерівність .




  1. Доведіть, що кожне натуральне число дорівнює сумі кількох (мож­ливо, одного) різних чисел Фібоначчі.




  1. Доведіть, що для довільного натурального п > 3 число п! можна розкласти на множники, відношення яких буде не менше від і не більше за .




  1. Доведіть, що для довільних додатних чисел х1, х2, ... , хn справедли­ва нерівність (нерівність Коші).


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