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

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

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

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

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

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

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

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

${\displaystyle \ S_{1}=1}$ 
${\displaystyle \ S_{2}=1+2=3}$ 
${\displaystyle \ S_{3}=1+2+3=6}$ 
${\displaystyle \ S_{4}=1+2+3+4=10}$ 
.
.
${\displaystyle \ S_{n}=1+2+3+\cdots +(n-2)+(n-1)+n}$ 

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

${\displaystyle S_{2}={\frac {2\cdot 3}{2}}={\frac {6}{2}}=3}$ 
${\displaystyle S_{3}={\frac {3\cdot 4}{2}}={\frac {12}{2}}=6}$ 
${\displaystyle S_{4}={\frac {4\cdot 5}{2}}={\frac {20}{2}}=10}$ 

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

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

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

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

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

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

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

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

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