Скільки випадків для сильної індукції?
Сильна індукція часто використовується там, де існує рекурентне співвідношення, тобто an=an−1−an−2. У цій ситуації, оскільки для роботи з заданою формулою потрібні 2 різні кроки, вам потрібно мати не менше 2 базових випадків щоб уникнути будь-яких дірок у вашому доказі.
Сильна індукція вимагає: якщо ми маємо, що [∀k∈N,k<n,P(k)]→P(n) виконується, то P(n) є істинним для всіх n∈N. Аргумент для P(0) справедливий, оскільки [∀k∈N,k<0,P(k)] завжди хибне (тобто немає натуральних чисел, менших за нуль), тому ми маємо, що [∀k∈ N,k<0,P(k)]→P(0).
У звичайній індукційній аргументації ви припускаєте, що P(n) істинне, і намагаєтеся довести, що P(n+1) також істинне. У сильній індукційній аргументації ви можете припустити, що всі P(0), P(1), … і P(n) істинні, коли ви збираєтеся довести P(n+1). Таким чином, ви можете припустити більш сильний набір гіпотез, які можуть полегшити вашу роботу.
Індукція з кількома базовими випадками дуже важлива для роботи з рекурсивно визначеними послідовностями, такими як послідовність Фібоначчі, де кожен член залежить від більш ніж одного з попередніх термінів.
Все те саме, що доведення індукції, просто базовий випадок не дорівнює 1.
Індукція має три етапи:
- Базовий випадок – це те, що твердження є істинним для певного числа. Зазвичай це невелике число, наприклад 1…
- Індуктивна гіпотеза передбачає, що твердження є істинним для k.
- Індуктивний крок/доказ полягає в тому, що ви показуєте, що тоді твердження має бути істинним для k + 1.