Математичка индукција
From Wikipedia, the free encyclopedia
Математичка индукција је метод математичког доказивања који се обично користи да се утврди да је дати исказ тачан за све природне бројеве. Ово се врши
- доказивањем да је први у бесконачном низу исказа тачан, и затим
- доказивањем да ако је неки исказ у бесконачном низу исказа тачан, онда је тачан и њему следећи исказ
Математичку индукцију не треба схватати као облик индуктивног резоновања, које се сматра не-ригорозним у математици (види проблем индукције). У ствари, математичка индукција је облик дедуктивног резоновања, и потпуно је ригорозна.
Метод се може проширити да докаже изјаве о општијим добро утемељеним структурама, као што су стабла; ова генерализација, позната као структурна индукција, користи се у математичкој логици и рачунарству. Математичка индукција у овом проширеном смислу је уско повезана са рекурзијом. Математичка индукција је правило закључивања које се користи у формалним доказима и представља основу већине доказа исправности за компјутерске програме.[3]
Иако њено име може сугерисати другачије, математичку индукцију не треба мешати са индуктивним резоновањем које се користи у филозофији (погледајте проблем индукције). Математички метод испитује бесконачно много случајева да би доказао општу тврдњу, али то чини помоћу коначног ланца дедуктивног закључивања који укључује променљиву , која може узети бесконачно много вредности.[4]