thumb|right|300px|Inducţia matematică poate fi asemănată efectului căderii pieselor de domino. Inducția matematică („raționamentul prin recurență” sau „inducția completă infinită”) este o modalitate de demonstrație utilizată în matematică pentru a stabili dacă o anumită propoziție este valabilă pentru un număr nelimitat de cazuri, contorul cazurilor parcurgând toate numerele naturale.
Istoric Primele semne de utilizare a acestei metode pot fi găsite în demonstrația lui Euclid care încearcă să arate că numărul numerelor prime este infinit.(1994) "Could the Greeks Have Used Mathematical Induction? Did They Use It?" Physis XXXI. p. 253-265.Ungure, S. (1991) "Greek Mathematics and Mathematical Induction" Physis XXVIII, p. 273-289.
În cadrul matematicii indiene, o metodă similară se găsește la matematicianul Bhaskara, așa-numita metodă chakravala.Metoda consta într-un algoritm ciclic de rezolvare a ecuațiilor pătratice nedeterminate.
În jurul anului 1000 d.Hr., se regăsește, la matematicianul persan Al-KarajiRashed, Roshdi (1972). "L'induction mathématique: al-Karajī, as-Samaw'al". Archive for History of Exact Science 6, p. 237-248. Vezi și (c. 953 - c. 1029), aplicarea metodei inducției la determinarea coeficienților binomiali (la ceea ce mai târziu avea să se numească binomul lui Newton), la studiul triunghiului lui Pascal.
Matematicianul islamic Ibn Al-Haytham (965 - 1039) aplică această metodă la calculul unor puteri cu exponent număr întreg.
Musulmanul Al-Maghribī al-Samaw'al (c. 1130 - c. 1180) utilizează inducția, într-o formă asemănătoare celei moderne, ducând mai departe studiile lui Al-Karaji privind triunghiul lui Pascal.
Prima expunere cu adevărat riguroasă a principiului inducției apare la matematicianul italian Francesco Maurolico (1494 - 1575).Vezi The Maurolico Project Acesta, în lucrarea Arithmeticorum libri duo (1575), demonstrează că suma primelor n numere impare este n².
Principiul inducției complete a fost descoperit și de Jakob Bernoulli (1713), Pascal (1653) și Fermat.
Descriere Demonstrația prin inducție că propoziția pentru orice se compune din doi pași:
Cazul inițial: demonstrarea faptului că propoziția este valabilă pentru . Pasul de inducție: Se dovedește că, pentru orice natural, implică .
Exemple
Exemplul 1
Să demonstrăm formula utilizată pentru suma primelor n numere naturale:
Inițializare:
pentru avem: . Formula este verificată în cazul inițial.
Iterare: Trebuie să arătăm că, dacă formula este valabilă pentru , atunci este valabilă și pentru .
Să presupunem formula valabilă pentru :
.
Adăugând la ambii membri , obținem:
.
Calculând, obținem:
.
Astfel am arătat că:
.
Exemplul 2
Să calculăm suma primelor numere impare:
.
.
Ajungem la presupunerea: Suma primelor numere impare, de la 1 până la este , adică:
.
Pentru a dovedi acest lucru prin metoda inducției complete, trebuie să demonstrăm că:
1.
2. Dacă , atunci .
Primul punct e simplu de dovedit. Pentru cel de-al doilea folosim identitățile:
.
Note
Vezi și Binomul lui Newton Șirul lui Fibonacci Inegalitatea lui Jensen Factorial
Legături externe Metoda inducției la Wolfram MathWorld. Inducția la Cut-the-Knot. Fabio Acerbi (2000) A Proof by Complete Induction , Archive for History of Exact Sciences Inducție completă Exemple de exerciții rezolvate.
Categorie:Demonstrații matematice Categorie:Logică matematică