Математичка индукција

Математичката индукција може неформално да се илустрира со повикување на секвенцијален домино-ефект

Математичката индукција е метод на математички доказ обично користен за докажување дека одредена изјава е точна за сите природни броеви или почнувајќи од некој природен број, или пак е точен за сите членови од една бесконечна низа.

Првиот познат доказ за математичката индукција се појавува во Arithmeticorum libri fuo (1575) на Франческо Мауролико, каде тој докажува дека сумата на првите n непарни броеви е $n^{2}$.

Најупростената и најкористена форма на математичка индукција докажува дека одредена изјава е точна за сите природни броеви n и се состои од два чекора:

1. Основа: се покажува дека изјавата е точна за n = 1 или за некоја почетна вредност.
2. Индуктивен чекор или индуктивна претпоставка: се претпоставува дека тврдењето во основата важи за n = m.
3. Заклучок: се докажува дека тврдењето важи за n = m + 1, од каде следи и точноста на тврдењето во општ случај, за било кој број n

Овој метод работи на тој начин што, прво се докажува дека изјавата е точна за некоја почетна вредност, а потоа докажување дека процесот користен да оди од една вредност до друга е валиден. Ако овие две работи се докажани, тогаш секоја вредност може да се добие со изведување на процесот повторно. Како на пример, при домино-ефектот, ако има долга низа од домино-плочки кои стојат на работ тогаш можеме да бидеме сигурни дека:

1. Првата домино-плочка ќе падне.
2. Кога едно домино ќе падне, и наредното ќе падне исто така.

потоа можеме да заклучиме дека сите домино-плочки ќе паднат.

Примери

За да се изведе формума за пресметување на збирот на првите n природни броеви се користи принципот математичка индукција. Така на пример, ако со S_n го означиме збирот на првите n природни броеви имаме:

$\ S_{1}=1$

$\ S_{2}=1+2=3$

$\ S_{3}=1+2+3=6$

$\ S_{4}=1+2+3+4=10$

.

.

$\ S_{n}=1+2+3+\cdots +(n-2)+(n-1)+n$

Најважно е да се забележи дали постои поврзаност помеѓу, во овој случај, бројот на броеви коишто ги собираме и нивниот збир. Може да увидиме дека:

$S_{2}={\frac {2\cdot 3}{2}}={\frac {6}{2}}=3$

$S_{3}={\frac {3\cdot 4}{2}}={\frac {12}{2}}=6$

$S_{4}={\frac {4\cdot 5}{2}}={\frac {20}{2}}=10$

Имајќи ги предвид горните равенства (кои формално го чинат првиот чекор - основата), претпоставуваме дека за некој број m бараниот збир би бил:

$S_{m}={\frac {m(m+1)}{2}}$

што претпоставува индуктивна претпоставка, односно формално тоа е вториот чекор.

Останува уште да се провери точноста на тврдењето за следниот природен број: m + 1. Се добива следново:

$\ S_{m}+_{1}=S_{m}+(m+1)={\frac {m(m+1)}{2}}+(m+1)={\frac {m(m+1)+2(m+1)}{2}}$

од каде конечно се добива:

$\ S_{m}+_{1}={\frac {(m+1)(m+2)}{2}}$

со што се потврдува точноста на тврдењето за m + 1, од каде следи точноста за било кој природен број, што значи дека збирот на првите n природни броеви изнесува:

$\ S_{n}={\frac {n(n+1)}{2}}$