Principiul Inductiei Matematice

Principiul inductiei matematice constituie un mijloc important de demonstratie in matematica a propozitiilor (afirmatiilor) ce depind de argument natural.

Metoda inductiei matematice consta in urmatoarele:

O propozitie (afirmatie) oarecare P(n), ce depinde de un numar natural n, este adevarata pentru orice n natural, daca:

1. P(1) este o propozitie (afirmatie) adevarata;
2. P(n) ramane o propozitie (afirmatie) adevarata, cand n se majoreaza cu o unitate, adica P(n+ 1) este adevarata.

Asadar, metoda inductiei presupune doua etape:

1. Etapa de verificare:   se verifica daca propozitia P(1) este adevarata;
2. Etapa de demonstrare: se presupune ca propozitia P(n) este adevarata si se demonstreaza justetea afirmatiei P(n + 1) (n a fost majorat cu o unutate).

Nota 1. In unele cazuri metoda inductiei matematice se utilizeaza in urmatoarea forma:

Fie m un numar natural, m > 1 si P(n) o propozitie ce depinde de n, n і m.

Daca

1. P(m) este adevarata;
2. P(n) fiind o propozitie justa implica P(n + 1) adevarata pentru n і m, atunci P(n) este o propozitie adevarata pentru orice numar natural n і m.

In continuare sa ilustram metoda inductiei matematice prin exemplu.

Exemplul 1. Sa se demonstreze urmatoarele egalitati

unde n О N.

Rezolvare. a) Pentru n = 1 egalitatea devine  1=1, prin urmare P(1) este adevarata. Presupunem ca egalitatea din enunt este adevarata, adica are loc egalitatea

, si urmeaza sa verificam daca P(n + 1), adica
este justa. Cum (se tine seama de egalitatea din enunt)
se obtine
adica P(n + 1) este afirmatie justa.

Asadar, conform principiului inductiei matematice egalitatea din enunt este justa pentru orice nnatural.

Nota 2. Mentionam ca acest exemplu poate fi rezolvat si fara utilizarea inductiei matematice. Intr-adevar, suma 1 + 2 + 3 + ... + n reprezinta suma primilor n termeni ai progresiei aritmetice cu primul termen a₁ = 1 si ratia d = 1. In baza formulei cunoscute  se obtine

b) Pentru n = 1 egalitatea devine 2·1 - 1 = 1² sau 1=1, astfel P(1) este justa. Presupunem justa egalitatea

1 + 3 + 5 + ... + (2n - 1) = n² si urmeaza sa verificam daca are loc P(n + 1):
1 + 3 + 5 + ... + (2n - 1) + (2(n + 1) - 1) = (n + 1)² sau
1 + 3 + 5 + ... + (2n - 1) + (2n + 1) = (n + 1)².

Se tine seama de egalitatea din enunt si se obtine

1 + 3 + 5 + ... + (2n - 1) + (2n + 1) = n² + (2n + 1) = (n + 1)².

Asadar P(n + 1) este adevarata si, prin urmare, egalitatea din enunt este adevarata.

Nota 3. Similar exemplului precedent, se rezolva si fara a aplica metoda inductiei matematice.

c) Pentru n = 1 egalitatea este justa  1=1. Se presupune justa egalitatea

si se arata ca
adica P(n) adevarata implica P(n + 1) adevarata. In adevar

si cum 2n² + 7n + 6 = (2n + 3)(n + 2) se obtine

si, prin urmare, egalitatea este adevarata.

d) Pentru n = 1 egalitatea este justa:  1=1. Se presupune ca are loc egalitatea

si se arata ca are loc egalitatea

In adevar, tinand seama de ipoteza

e) Propozitia P(1) este justa  2=2. Se presupune ca egalitatea

este adevarata si se arata ca ea implica egalitatea
In adevar

Asadar, egalitatea enuntata este justa pentru orice n natural.

f) P(1) este adevarata:  ¹/₃ = ¹/₃. Se presupune ca are loc P(n):

si se arata ca aceasta egalitate implica egalitatea

In adevar, tinand seama de justetea afirmatiei P(n), se obtine

Prin urmare, egalitatea este demonstrata.

g) Pentru n = 1 egalitatea devine a + b = b + a, si deci este adevarata.

Fie formula binomului Newton este justa pentru n = k, adica

Atunci
Tinand seama de egalitatea  se obtine

Exemplul 2. Sa se demonstreze inegalitatile

a) inegalitatea Bernuolli: (1 + a)n і 1 + na, a > -1,     n О N.

b) x1 + x2 + ... + xn і n,   daca   x1x2· ... ·xn = 1   si   xi > 0,   .

c) inegalitatea Cauchy relativa la media aritmetica si geometrica        unde   xi > 0, , n і 2.

d) sin2na + cos2na Ј 1,     n О N.

e)

f) 2n > n3,     n О N, n і 10.

Rezolvare. a) Pentru n = 1 inegalitatea este adevarata

1 + a і 1 + a. Se presupune ca are loc inegalitatea enuntata

(1 + a)n і 1 + na

(1)

si se arata, ca in asa ipoteza are loc si
(1 + a)^{n + 1} і 1 + (n + 1)a.

In adevar, cum a > -1 implica a + 1 > 0, multiplicand ambii membri ai inegalitatii (1) cu (a + 1) se obtine

(1 + a)ⁿ(1 + a) і (1 + na)(1 + a) sau
(1 + a)^{n + 1} і 1 + (n + 1)a + na² Cum na² і 0, rezulta
(1 + a)^{n + 1} і 1 + (n + 1)a + na² і 1 + (n + 1)a.

Asadar P(n) adevarata implica P(n + 1) adevarata, prin urmare, conform principiului inductiei matematice inegalitatea Bernoulli este adevarata.

b) Pentru n = 1, se obtine x₁ = 1, si, prin urmare x₁ і 1, adica P(1) este o afirmatie justa. Se presupune ca P(n) este adevarata, adica, x₁,x₂,...,x_n sunt n numere pozitive, prodususul carora este egal cu unu, x₁x₂·...·x_n = 1, si x₁ + x₂ + ... + x_n і n.

Sa aratam, ca aceasta ipoteza implica justetea urmatoarei afirmatii: daca x₁,x₂,...,x_n,x_n+1 sunt (n + 1) numere pozitive cu x₁x₂·...·x_n·x_n+1 = 1  atunci  x₁ + x₂ + ... + x_n + x_{n + 1} і n + 1.

Se disting urmatoarele doua cazuri:

1) x₁ = x₂ = ... = x_n = x_n+1 = 1 si atunci suma lor este (n + 1), inegalitatea fiind justa,

2) cel putin un numar este diferit de unu, fie mai mare ca unu. Atunci, dat fiind x₁x₂· ... ·x_n·x_{n + 1} = 1, rezulta ca exista cel putin inca un numar diferit de unu, mai exact, mai mic ca unu. Fie x_{n + 1} > 1 six_n < 1. Consideram n numere pozitive

x₁,x₂,...,x_n-1,(x_n·x_n+1). Produsul lor este egal cu unu, iar conform ipotezei
x₁ + x₂ + ... + x_n-1 + x_nx_{n + 1} і n. Ultima inegalitate se scrie astfel
x₁ + x₂ + ... + x_n-1 + x_nx_n+1 + x_n + x_n+1 і n + x_n + x_n+1 sau
x₁ + x₂ + ... + x_n-1 + x_n + x_n+1 і n + x_n + x_n+1 - x_nx_n+1.

Cum

n + x_n + x_n+1 - x_nx_n+1 = n + 1 + x_n+1(1 - x_n) - 1 + x_n =
= n + 1 + x_n+1(1 - x_n) - (1 - x_n) = n + 1 + (1 - x_n)(x_n+1 - 1) і n + 1 deoarece
(1 - x_n)(x_n+1 - 1) > 0, rezulta
x₁ + x₂ + ... + x_n + x_n+1 і n+1, adica P(n) adevarata implica P(n + 1) adevarata. Inegalitatea este demonstrata.

Nota 4. Se observa, ca semnul egalitatii are loc daca si numai daca x₁ = x₂ = ... = x_n = 1.

c) Fie x₁,x₂,...,x_n numere pozitive arbitrare. Se considera n numere

Cum aceste numere sunt pozitive si produsul lor este egal cu unu
conform inegalitatii b) demonstrate anterior rezulta
de unde rezulta

Nota 5. Semnul egalitatii are loc daca si numai daca x₁ = x₂ = ... = x_n.

d) P(1) este o afirmatie justa: sin²a + cos²a = 1. Se presupune ca P(n) este o afirmatie adevarata:

sin²ⁿa + cos²ⁿa Ј 1 si se arata ca P(n + 1) are loc. In adevar
sin^{2(n + 1)}a + cos^{2(n + 1)}a = sin²ⁿa·sin²a + cos²ⁿa·cos²a < sin²ⁿa + cos²ⁿa Ј 1 (se tine seama ca daca sin²a Ј 1 atunci cos²a < 1 si reciproc daca cos²a Ј 1 atunci sin²a < 1). Asadar, pentru orice n О N    sin²ⁿa + cos²ⁿ Ј 1 si semnul egalitatii se atinge doar pentru n = 1.

e) Pentru n = 1 afirmatia este justa:      1 < ³/₂.

Se presupune ca  si urmeaza de a demonstra ca

Cum
se tine seama de P(n) si se obtine

f) Se tine seama de nota 1 si se verifica P(10): 2¹⁰ > 10³, 1024 > 1000, asadar pentru n = 10 inegalitatea este justa. Se presupune ca 2ⁿ > n³    (n > 10) si trebuie de demonstrat P(n + 1), adica 2ⁿ⁺¹ > (n + 1)³.

Cum pentru n > 10 avem  sau  rezulta

2n³ > n³ + 3n² + 3n + 1   sau   n³ > 3n² + 3n + 1. Se tine seama de ipoteza (2ⁿ > n³) si se obtine
2ⁿ⁺¹ = 2ⁿ·2 = 2ⁿ + 2ⁿ > n³ + n³ > n³ + 3n² + 3n + 1 = (n + 1)³.

Asadar conform principiului inductiei pentru orice n О N,     n і 10 avem 2ⁿ > n³.

Exemplul 3. Sa se demonstreze ca pentru orice n О N

a) n(2n2 - 3n + 1)   se divide cu 6,

b) 62n-2 + 3n+1 + 3n-1   se divide cu 11.

Rezolvare. a) P(1) este o propozitie adevarata ( 0 se divide cu 6). Fie P(n) are loc, adica n(2n² - 3n + 1) = n(n - 1)(2n - 1) se divide cu 6. Se arata, ca are loc P(n + 1) adica (n + 1)n(2n + 1) se divide cu 6. In adevar, cum

n(n + 1)(2n + 1) = n(n - 1 + 2)(2n - 1 + 2) = (n(n - 1) + 2n)(2n - 1 + 2) =

= n(n - 1)(2n - 1) + 2n(n - 1) + 2n(2n + 1) = n(n - 1)(2n - 1) + 2n·3n =

= n(n - 1)(2n - 1) + 6n2

si cum atat n(n - 1)(2n - 1) cat si 6n² se divid cu 6, rezulta ca si suma lor, adica n(n + 1)(2n + 1) se divide cu 6.

Asadar P(n + 1) este o afirmatie justa, si n(2n² - 3n + 1) se divide cu 6 pentru orice n О N.

b) Se verifica P(1): 6⁰ + 3² + 3⁰ = 11, prin urmare P(1) este justa. Urmeaza sa se arate, ca daca 6^2n-2 + 3ⁿ⁺¹ + 3^n-1 se divide cu 11 (P(n)), atunci 6²ⁿ + 3ⁿ⁺² + 3ⁿ de asemenea se divide cu 11 (P(n + 1)). In adevar, cum

6²ⁿ + 3ⁿ⁺² + 3ⁿ = 6^2n-2+2 + 3ⁿ⁺¹⁺¹ + 3^n-1+1 = = 6²·6^2n-2 + 3·3ⁿ⁺¹ + 3·3^n-1 = 3·(6^2n-2 + 3ⁿ⁺¹ + 3^n-1) + 33·6^2n-2 si atat 6^2n-2 + 3ⁿ⁺¹ + 3^n-1, cat si 33·6^2n-2 se divid cu 11, rezulta ca si suma lor, adica 6²ⁿ + 3ⁿ⁺² + 3ⁿ se divide cu 11.

Inductia in geometrie.

Exemplul 1. Sa se calculeze latura  a unui poligon regulat cu 2ⁿ laturi inscris intr-o circumferinta de raza R.

Rezolvare. Pentru n = 2 poligonul regulat cu 2² laturi reprezinta un patrat, si in acest caz a₄ = R.

Fie  si sa determinam . Daca AB = aў, atunci AE = ^aў/₂; BD = aўў. Din triunghiulDEB, conform teoremei Pitagora

La randul sau DE = R-EC si
Asadar  si deci,
Astfel s-a obtinut o formula de trecere de la n la n + 1. In cazuri particulare:
Natural apare ipoteza

(2)

Cum a fost arata anterior, pentru n = 1 aceasta formula este adevarata.

Fie (2) adevarata pentru n = k. Sa calculam . Conform formulei de trecere se obtine

Nota. Din (2) rezulta ca lungimea circumferintei este egala cu

si cum l = 2pR, se obtine

Exercitii pentru autoevaluare

I. Sa se demonstreze egalitatile:

II. Sa se demonstreze inegalitatile

III. Sa se demonstreze, ca pentru orice numar natural, numarul a_n se divide cu b

a) an = 5n+3 + 113n+1,    b = 17,

b) an = 11n+2 + 122n+1,    b = 133,

c) an = 2n3 + 3n2 + 7n,    b = 6,

d) an = 10n + 18n - 28,    b = 27,

e) an = n5 - n,    b = 30.

IV. Sa se arate, ca    (Formula lui Viete).