Inducţie matematică

De la Wikipedia, enciclopedia liberă

Salt la: Navigare, căutare
Inducţia matematică poate fi asemănată efectului căderii pieselor de domino.

Inducţia matematică ("raţionamentul prin recurenţă" sau "inducţia completă") este o modalitate de demonstraţie utilizată în matematică pentru a stabili dacă o anumită propoziţie este valabilă pentru toate numerele naturale.

Cuprins

[modifică] 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, găsim o metodă similară la matematicianul Bhaskara, aşa-numita metodă "chakravala".[3]

În jurul anului 1000 d.Hr., regăsim, 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 integrale.

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 matemaicianul 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.

[modifică] Descriere

Demonstraţia prin inducţie că propoziţia P(n) \, pentru orice n \in \mathbb{N} se compune din doi paşi:

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

[modifică] Exemple

[modifică] Exemplul 1

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

1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}
  • Iniţializare:
pentru  n = 1 \,   avem:   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 n= m \, , atunci este valabilă şi pentru   n= m+1 \,.

Să presupunem formula valabilă pentru n = m \,  :

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

Adăugând la ambii membri m +1 \, , obţinem:

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

Calculând, obţinem:

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

Astfel am arătat că:

P (m) \Longrightarrow P (m+1) .


[modifică] Exemplul 2

Să calculăm suma primelor numere impare:

1 = 1 \,


1+3=4 \,


1+3+5=9 \,


1+3+5+7=16 \,.


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

\sum_{i=1}^{n}(2i-1) = n^2 .

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

1. \sum_{i=1}^{1}(2i-1)= 1^2
2. Dacă \sum_{i=1}^{n}(2i-1)= n^2 , atunci \sum_{i=1}^{n+1}(2i-1)= (n+1)^2 .

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

\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 .


[modifică] 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
  5. ^ Vezi The Maurolico Project

[modifică] Vezi şi

[modifică] Legături externe

Adus de la http://ro.wikipedia.org/wiki/Induc%C5%A3ie_matematic%C4%83
Unelte personale