Inducție matematică

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.

Inducţia matematică poate fi asemănată efectului căderii pieselor de domino.

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.^[1][2]

În cadrul matematicii indiene, o metodă similară se găsește la matematicianul Bhaskara, așa-numita metodă chakravala.^[3]

În jurul anului 1000 d.Hr., se regăsește, la matematicianul persan Al-Karaji^[4] (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).^[5] 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 ${\displaystyle P(n)\,}$ pentru orice ${\displaystyle n\in \mathbb {N} }$ se compune din doi pași:

1. Cazul inițial: demonstrarea faptului că propoziția este valabilă pentru ${\displaystyle n=0\,}$ .
2. Pasul de inducție: Se dovedește că, pentru orice ${\displaystyle n\,}$ natural, ${\displaystyle P(n)\,}$ implică ${\displaystyle P(n+1)\,}$.

Exemple

Exemplul 1

Să demonstrăm formula utilizată pentru suma primelor n numere naturale:

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

• Inițializare:

pentru  ${\displaystyle n=1\,}$   avem:   ${\displaystyle 1={\frac {1(1+1)}{2}}={\frac {2}{2}}=1}$ .

Formula este verificată în cazul inițial.

• Iterare:

Trebuie să arătăm că, dacă formula este valabilă pentru ${\displaystyle n=m\,}$ , atunci este valabilă și pentru   ${\displaystyle n=m+1\,}$.

Să presupunem formula valabilă pentru ${\displaystyle n=m\,}$ :

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

Adăugând la ambii membri ${\displaystyle m+1\,}$ , obținem:

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

Calculând, obținem:

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

Astfel am arătat că:

${\displaystyle P(m)\Longrightarrow P(m+1)}$ .

Exemplul 2

Să calculăm suma primelor numere impare:

${\displaystyle 1=1\,}$

${\displaystyle 1+3=4\,}$

${\displaystyle 1+3+5=9\,}$

${\displaystyle 1+3+5+7=16\,}$.

${\displaystyle 1+3+5+7+9=25\,}$.

Ajungem la presupunerea: Suma primelor numere impare, de la 1 până la ${\displaystyle 2n-1\,}$ este ${\displaystyle n^{2}\,}$,   adică:

${\displaystyle \sum _{i=1}^{n}(2i-1)=n^{2}}$ .

Pentru a dovedi acest lucru prin metoda inducției complete, trebuie să demonstrăm că:

1. ${\displaystyle \sum _{i=1}^{1}(2i-1)=1^{2}}$

2. Dacă ${\displaystyle \sum _{i=1}^{n}(2i-1)=n^{2}}$ , atunci ${\displaystyle \sum _{i=1}^{n+1}(2i-1)=(n+1)^{2}}$.

Primul punct e simplu de dovedit. Pentru cel de-al doilea folosim identitățile:

${\displaystyle \sum _{i=1}^{n+1}(2i-1)=\sum _{i=1}^{n}(2i-1)\;+\;\;(2(n+1)-1)=n^{2}+2(n+1)-1=n^{2}+2n+1=(n+1)^{2}}$ .

Note

1. (1994) "Could the Greeks Have Used Mathematical Induction? Did They Use It?" Physis XXXI. p. 253-265.
2. Ungure, S. (1991) "Greek Mathematics and Mathematical Induction" Physis XXVIII, p. 273-289.
3. Metoda consta într-un algoritm ciclic de rezolvare a ecuațiilor pătratice nedeterminate.
4. Rashed, Roshdi (1972). "L'induction mathématique: al-Karajī, as-Samaw'al". Archive for History of Exact Science 6, p. 237-248. Vezi și^{[nefuncțională]}
5. Vezi The Maurolico Project

Vezi și

• Binomul lui Newton
• Șirul lui Fibonacci
• Inegalitatea lui Jensen
• Factorial

Legături externe

• en Metoda inducției la Wolfram MathWorld.
• en Inducția la Cut-the-Knot.
• fr Fabio Acerbi (2000) A Proof by Complete Induction Arhivat în 26 noiembrie 2006, la Wayback Machine., Archive for History of Exact Sciences
• de Inducție completă
• ro Exemple de exerciții rezolvate.