Силната индукция (известна още като „пълна индукция“) е вариант на метода на математическата индукция, който ни дава „по-силно“ предположение, с което да работим.
Докато при обикновената (слаба) индукция допускаме, че твърдението е вярно само за предходното число $n = k$, при силната индукция допускаме, че твърдението е вярно за всички числа от началото до $k$ включително.
Разликата в индукционното предположение
За да докажем, че твърдението $P(n)$ е вярно за всяко $n$:
| Тип индукция | Какво приемаме за вярно (Хипотеза)? | Цел |
| Слаба индукция | Само $P(k)$ | Доказваме $P(k+1)$ |
| Силна индукция | $P(1), P(2), P(3), \dots$ и $P(k)$ | Доказваме $P(k+1)$ |
Аналогия: Стълбата и Доминото
-
Слаба индукция (Домино): За да падне плочка $k+1$, е достатъчно само плочката точно преди нея ($k$) да я удари.
-
Силна индукция (Стълба): Представете си, че за да се качите на стъпало $k+1$, не е достатъчно само да сте на стъпало $k$, а може би трябва да използвате стабилността на всички стъпала под вас (например, ако стълбата е нестабилна). Силната индукция ви позволява да използвате информация от всяко стъпало, което вече сте изкачили.
Кога се използва?
Силната индукция е незаменима, когато твърдението за $n = k+1$ не зависи директно от $n = k$, а от някое по-малко число.
Класически пример: Основна теорема на аритметиката
Всяко естествено число $n > 1$ може да се представи като произведение на прости числа.
Ако искаме да докажем това за числото $k+1$:
-
Ако $k+1$ е просто число – доказано е.
-
Ако $k+1$ е съставно, то се разпада на произведение $a \cdot b$, където $a$ и $b$ са по-малки от $k+1$.
-
Тук слабата индукция не помага, защото $a$ и $b$ не са задължително равни на $k$. Но силната индукция ни позволява да кажем: „Тъй като $a$ и $b$ са по-малки от $k+1$, ние вече сме доказали, че те се разлагат на прости числа“.
Логическа еквивалентност
Интересен факт е, че двете форми на индукция са логически еквивалентни. Всяко доказателство със силна индукция може да се превърне в такова със слаба (чрез промяна на дефиницията на твърдението), но силната индукция често прави доказателството много по-естествено и лесно за разбиране.
Вижте видео за Пример за доказателство чрез силна индукция, което ще ви помогне да разберете как на практика се прилага допускането за всички предходни стойности.
