Inducție matematică

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.

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.

În cadrul matematicii indiene, găsim o metodă similară la matematicianul Bhaskara, așa-numita metodă "chakravala".

În jurul anului 1000 d.Hr., regăsim, la matematicianul persan Al-Karaji (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). 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 $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) \,$.

Exemple

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)$ .

Exemplul 2

Să calculăm suma primelor numere impare:

$1 = 1 \,$

$1+3=4 \,$

$1+3+5=9 \,$

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

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

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

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, Archive for History of Exact Sciences
• de Inducție completă
• ro Exemple de exerciții rezolvate.