Рекомендую матеріали від Йозефа Райніка з великим списком задач.
Що таке математична індукція?
Одним з перших (і одним з найважливіших) інструментів у математичних доказах ми зустрічаємо математичну індукцію. Базується математична індукція на достатньо простій увазі:
Якщо твердження правдиве для \(x=0\) та правдивість твердження для \(x=k+1\) випливає з правдивості твердження для \(x=k\) (для будь-якого \(k\)), то твердження правдиве для всіх \(x\in \mathbb{N}\).
Що це значить на практиці? Нехай у нас є предикат (Predicate, výroková forma) \(P\). Нехай ми знаємо, що твердження \(P(0)\) правдиве. Нехай ми теж знаємо, що з правдивості \(P(k)\) випливає правдивість \(P(k+1)\) для будь-якого \(k\).
Тоді для \(k=0\) з правдивості \(P(0)\) випливає правдивість \(P(0+1)\). А оскільки \(P(0)\) правдиве, то правдиве й \(P(1)\).
Потім для \(k=1\) з правдивості \(P(1)\) випливає правдивість \(P(1+1)\). А оскільки \(P(1)\) правдиве, то правдиве й \(P(2)\).
Потім для \(k=2\) з правдивості \(P(2)\) випливає правдивість \(P(2+1)\). А оскільки \(P(2)\) правдиве, то правдиве й \(P(3)\).
\[\vdots\]Тобто, таким чином ми бачимо, що можна отримати, що твердження правдиве для будь-якого \(x\): як доміно, з попереднього твердження буде завжди випливати наступне.
В логічних формулах математична індукція записується як:
\[P(0) \wedge (\forall x\in\mathbb{N}: P(x) \implies P(x+1)) \implies \forall y\in\mathbb{N}: P(y)\]Зауважимо, що необов’язково починати математичну індукцію з нуля. Наприклад, якщо ми вкажемо, що правдиве твердження \(P(3)\) та що для всіх натуральних \(k\geq 3\) виконується твердження \(P(k)\implies P(k+1)\), то ми за допомогою математичної індукції вкажемо що твердження \(P(x)\) є правдиве для всіх \(x\in \mathbb{N}\), \(x\geq 3\).
Як її використовувати?
Спочатку треба побачити, де використовувати матіндукцію і задуматися, чи в цій конкретній задачі матіндукцію можна розумно застосувати. Основні 2 властивості, які варто зауважити:
- В задачі треба довести, що якесь твердження виконується для будь-якого \(n\) (часто саме буквою \(n\) позначають Натуральне число).
- В задачі можна “більше” твердження (тобто твердження з більшим \(n\)) можна звести до меншого (тобто твердження з меншим \(n\)).
Якщо ми вирішили довести твердження математичною індукцією, то рішення треба розбити на 2 кроки:
- Довести базу індукції — найменше значення \(n\), для якого треба твердження довести, що зазвичай буде \(0\) або \(1\) (але деколи може бути і більше число, наприклад \(3\) чи \(4\)). Зазвичай, але не завжди, це легший з 2 кроків.
- Довести індуктивний крок — довести для будь-якого \(k\) з правдивості твердження для \(k\) буде випливати правдивість твердження для \(k+1\). Зазвичай, але не завжди, це складніший з 2 кроків. Зазвичай доведення є типовим для імплікацій: припускаємо правдивість лівої сторони, доводимо правдивість правої.
Задачі
Розберемо типові задачі.
Суми
Задача 1. Доведіть, що для всіх додатніх цілих чисел:
\[ 1\cdot2+2\cdot3+3\cdot4+\dots+n\cdot(n+1) = \frac{n(n+1)(n+2)}{3} \]Зауваження: Зазвичай суми такого вигляду достатньо легко вирішуються математичною індукцією.
Доказ: Доведемо за допомогою математичної індукції:
- База індукції: Найменше додатне ціле число це \(1\). Доведемо твердження для \(n=1\): \[ \begin{aligned} 1\cdot 2 &= \frac{1\cdot2\cdot3}{3}\\ 2 &= 2 \end{aligned} \] Твердження доведено.
- Крок індукції: Тепер доведемо, що якщо твердження виконується для якогось \(n\), то виконується і для \(n+1\). Нехай твердження правдиве для \(n\). Тобто: \[ 1\cdot2+2\cdot3+3\cdot4+\dots+n\cdot(n+1) = \frac{n(n+1)(n+2)}{3} \]
Ми хочемо з цього довести:
\[ 1\cdot2+2\cdot3+3\cdot4+\dots+n\cdot(n+1)+(n+1)\cdot((n+1)+1) = \frac{(n+1)((n+1)+1)((n+1)+2)}{3} \]Якщо спростимо, то хочемо довести:
\[ 1\cdot2+2\cdot3+3\cdot4+\dots+n\cdot(n+1)+(n+1)\cdot(n+2) = \frac{(n+1)(n+2)(n+3)}{3} \]Би вже знаємо, що:
\[ 1\cdot2+2\cdot3+3\cdot4+\dots+n\cdot(n+1) = \frac{n(n+1)(n+2)}{3} \]Тоді ми можемо спробувати додати щось на ліву сторону, щоб отримати те, що хочемо довести. В нашому випадку це було б число \((n+1)\cdot(n+2)\):
\[ \begin{aligned} (1\cdot2+2\cdot3+3\cdot4+\dots+n\cdot(n+1)) + (n+1)\cdot(n+2) &= \left(\frac{n(n+1)(n+2)}{3}\right) + (n+1)\cdot(n+2)\\ \end{aligned} \]Окей, на лівій стороні ми отримали бажаний вираз. Чи можна перетворити вираз вправо на той, що ми хотіли?
\[ \begin{aligned} (1\cdot2+2\cdot3+3\cdot4+\dots+n\cdot(n+1)) + (n+1)\cdot(n+2) &= \left(\frac{n(n+1)(n+2)}{3}\right) + (n+1)\cdot(n+2)\\ 1\cdot2+2\cdot3+3\cdot4+\dots+n\cdot(n+1) + (n+1)\cdot(n+2) &= \left(\frac{n(n+1)(n+2)}{3}\right) + \frac{3(n+1)(n+2)}{3}\\ 1\cdot2+2\cdot3+3\cdot4+\dots+n\cdot(n+1) + (n+1)\cdot(n+2) &= \frac{n(n+1)(n+2) + 3(n+1)(n+2)}{3}\\ 1\cdot2+2\cdot3+3\cdot4+\dots+n\cdot(n+1) + (n+1)\cdot(n+2) &= \frac{n((n+1)(n+2)) + 3((n+1)(n+2))}{3}\\ 1\cdot2+2\cdot3+3\cdot4+\dots+n\cdot(n+1) + (n+1)\cdot(n+2) &= \frac{(n+3)((n+1)(n+2))}{3}\\ 1\cdot2+2\cdot3+3\cdot4+\dots+n\cdot(n+1) + (n+1)\cdot(n+2) &= \frac{(n+1)(n+2)(n+3)}{3}\\ \end{aligned} \]Ми отримали твердження що хотіли довести. \(\square\)
У майбутньому на цій сторінці з’являться й подальші задачі з рішеннями. Задачі можна знайти у Йозефа Райніка.