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

Умова. Спробуємо підмітити закономірність у «поведінці» сум $n$ перших непарних натуральних чисел. Позначимо символом $S_n$ суму $n$ перших непарних чисел.

Розв’язання.

Числа 1, 4, 9, 16, 25 — квадрати послідовних натуральних чисел. Тепер можна зробити таке припущення (індуктивний висновок): для будь-якого натурального $n$

Умова. Розглянемо значення многочлена $f(n) = n^2 - n + 41$ при значеннях $n$, які дорівнюють 1, 2, 3, 4, 5.

Розв’язання.

$f(1) = 41$ — просте число; $f(2) = 43$ — просте число; $f(3) = 47$ — просте число; $f(4) = 53$ — просте число; $f(5) = 61$ — просте число.

Можна зробити припущення: для будь-якого натурального $n$ значення виразу $f(n)$ є простим числом. Однак це припущення хибне: $f(41) = 41^2 - 41 + 41 = 41^2$ — складене число.

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

Доведення факту методом математичної індукції складається з двох частин (теорем):

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

Було б помилковим вважати, що доведення теореми «база індукції» є менш суттєвим. Покажемо, як, користуючись лише теоремою «індуктивний перехід», можна, наприклад, «довести», що при будь-якому натуральному $n$ число $2n + 1$ є парним. Нехай це правильно при $n = k$, тобто $2k + 1$ є парним. Тоді $2(k+1) + 1 = (2k+1) + 2$. Сума двох парних чисел — число парне. Отже, ми довели теорему «індуктивний перехід», але при цьому не виявили, що теорема «база індукції» є неправильною (при $n = 1$ число $2 \cdot 1 + 1 = 3$ є непарним).

Умова. Виведіть формулу для обчислення значення суми

Розв’язання. Для $n = 1$: $S_1 = \dfrac{1}{1 \cdot 3} = \dfrac{1}{3}$.

Для $n = 2$: $S_2 = \dfrac{1}{1 \cdot 3} + \dfrac{7}{3 \cdot 5} = \dfrac{4}{5}$.

Для $n = 3$: $S_3 = \dfrac{1}{1 \cdot 3} + \dfrac{7}{3 \cdot 5} + \dfrac{17}{5 \cdot 7} = \dfrac{9}{7}$.

Для $n = 4$: $S_4 = \dfrac{1}{1 \cdot 3} + \dfrac{7}{3 \cdot 5} + \dfrac{17}{5 \cdot 7} + \dfrac{31}{7 \cdot 9} = \dfrac{16}{9}$.

Тепер можна зробити таке припущення: для всіх $n \in \mathbb{N}$ виконується рівність

Доведемо цю гіпотезу методом математичної індукції. Вище ми перевірили справедливість формули для $n = 1$, тим самим довели теорему «база індукції».

Нехай формула є правильною при $n = k$, тобто $S_k = \dfrac{k^2}{2k+1}$.

Маємо:

Отже, формула є правильною і при $n = k + 1$.

Відповідь: $S_n = \dfrac{n^2}{2n+1}$.

Умова. Доведіть, що $1 + 2 + 3 + \ldots + n = \dfrac{n(n+1)}{2}$, де $n \in \mathbb{N}$.

Розв’язання. Користуючись методом математичної індукції, доведіть цю рівність самостійно.

Умова. Виведіть формулу для обчислення суми $1^3 + 2^3 + 3^3 + \ldots + n^3$, де $n \in \mathbb{N}$.

Розв’язання. Для $n = 1$: $S_1 = 1^3 = 1$.

Для $n = 2$: $S_2 = 1^3 + 2^3 = 9 = (1 + 2)^2$.

Для $n = 3$: $S_3 = 1^3 + 2^3 + 3^3 = 36 = 6^2 = (1 + 2 + 3)^2$.

Для $n = 4$: $S_4 = 1^3 + 2^3 + 3^3 + 4^3 = 100 = 10^2 = (1 + 2 + 3 + 4)^2$.

Ураховуючи приклад 2, гіпотезу можна записати в такій формі:

Справедливість цієї формули при $n = 1$ було встановлено вище.

Нехай формула є правильною при $n = k$, тобто $S_k = \left(\dfrac{k(k+1)}{2}\right)^2$.

Маємо:

Отже, формула є правильною при $n = k + 1$.

Відповідь: $1^3 + 2^3 + \ldots + n^3 = \left(\dfrac{n(n+1)}{2}\right)^2$.

Умова. Доведіть, що для будь-якого $n \in \mathbb{N}$ значення виразу $5^n - 3^n + 2n$ кратне 4.

Розв’язання. При $n = 1$ отримуємо: $5^1 - 3^1 + 2 \cdot 1 = 4$. Оскільки $4 \mathrel{\vdots} 4$, то теорему «база індукції» доведено.

Нехай при $n = k$ твердження є правильним, тобто $(5^k - 3^k + 2k) \mathrel{\vdots} 4$.

Доведемо, що тоді це твердження є правильним при $n = k + 1$, тобто

Для доведення достатньо показати, що різниця $(5^{k+1} - 3^{k+1} + 2k + 2) - (5^k - 3^k + 2k)$ кратна 4.

Перепишемо цю різницю так:

Оскільки $(3^k - 1) \mathrel{\vdots} 2$, то значення отриманого виразу кратне 4.

Отже, твердження, що доводиться, є правильним.

Умова. Доведіть нерівність (нерівність Бернуллі):

Розв’язання. При $n = 1$ маємо правильну нерівність $1 + x \geqslant 1 + x$.

Нехай нерівність, що доводиться, є правильною при $n = k$, тобто $(1 + x)^k \geqslant 1 + kx$, $k \in \mathbb{N}$. Оскільки $1 + x > 0$, то $(1 + x)^{k+1} \geqslant (1 + kx)(1 + x)$.

Маємо: $(1 + kx)(1 + x) = 1 + (k+1)x + kx^2 \geqslant 1 + (k+1)x$.

Звідси $(1 + x)^{k+1} \geqslant 1 + (k+1)x$.

Отже, припустивши, що нерівність, яка доводиться, є правильною при $n = k$, ми довели її справедливість при $n = k + 1$. Теореми «база індукції» та «індуктивний перехід» доведено. Таким чином, нерівність, що доводиться, є правильною.

1. Доведіть, що при будь-якому натуральному $n$ виконується рівність: $1^2 + 2^2 + 3^2 + \ldots + n^2 = \dfrac{n(n+1)(2n+1)}{6}$.

2. Доведіть нерівність $2^n > 2n + 1$, де $n \in \mathbb{N}$, $n \geqslant 3$.

3. Доведіть, що для будь-якого натурального $n$ значення виразу $(5^n - 3^n + 2n)$ кратне 4.