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.

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

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.