Застосування методу математичної індукції
3) Крок індукції: доведемо, що твердження вірне для n = k + 1, т. Е.
1 + 3 + 5 +. + (2k - 1) + (2k + 1) = (k + 1) 2. За припущенням, сума перших k доданків в лівій частині рівності дорівнює k 2. Значить, те, що потрібно довести, можна записати так:
k 2 + (2k + 1) = (k + 1) 2.
але це очевидно.
Приклад 15. Довести, що для будь-якого натурального n число n 3 + 5n ділиться на 6.
Доведення. База індукції є: при n = 1 число n 3 + 5n = 6 ділиться на 6. Припускаємо, що для деякого k число k 3 + 5k ділиться на 6. Використовуючи це, постараємося довести, що тоді і (k + 1) 3 + 5 (k + 1) ділиться на 6. Проведемо перетворення:
(K + 1) 3 + 5 (k + 1) = k 3 + 3k 2 + 3k + 1 + 5k + 5 = = (k 3 + 5k) + (3k 2 + 3k) + 6 = (k 3 + 5k ) + 3k (k + 1) + 6.
Перший доданок в цій сумі ділиться на 6 за припущенням, другий доданок теж ділиться на 6, так як з чисел k, k + 1 одне обов'язково парне. Значить, вся сума ділиться на 6, що й треба було довести.
В якості ще одного прикладу доведемо теорему про кількість підмножин кінцевого безлічі.
Теорема 4. Безліч, що складається з n елементів, має 2 n різних підмножин.
Доведення. Застосуємо індукцію по числу n. Якщо множина A = складається з одного елемента, то його підмножини - це 0,. Їх 2, тому теорема при n = 1 вірна (база індукції). Припускаємо, що будь-яка множина з k елементів має 2k підмножин. Розглянемо безліч
Всі його підмножини розділимо на 2 види. До першого виду віднесемо підмножини, що не містять ак + 1. За припущенням, таких підмножин 2к. Решта підмножини містять ак + 1, їх кількість також одно 2к, тому що кожне з них можна отримати додаванням ак + 1 до одного з підмножин першого виду. Всього підмножин множини A є:
2к + 2к = 2 x 2к = 2к + 1,
що й потрібно було довести.