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

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

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

Првиот познат доказ за математичката индукција се појавува во 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}}$