Inducia matematicNoiunea de deducie i de inducieS considerm urmtoarele propoziii: propozi 1) n orice triunghi lungimea unei laturi este mai mare dect diferena lungimilor celorlalte laturi. diferen 2) In triunghiul ABC (fig.1), lungimea laturii AB este mai mare dect diferena lungimilor laturilor BC i AC. dec diferen 3) Orice numr a crui ultim cifr este 0 sau 5, este divizibil cu 5. 4) Numerele 1980 i 1985 snt divizibile cu 5. s Propoziiile 1) i 3) au un caracter general, iar propoziiile 2) i 4) snt cazuri particulare ale propoziiilor 1) Propozi propozi s propozi respectiv 3). n general, propoziiile pot fi clasificate n propoziii generale i propoziii particulare. propozi propozi propozi particulare. Propoziiile 1) i 3) snt exemple de propoziii generale, iar 2) i 4) sunt exemple de propoziii particulare. Propozi s propozi propozi Procedeul prin care din propoziii generale se obin propoziii particulare se numete deducie. propozi ob propozi nume Una dintre trsturile caracteristice matematicii i altor tiine (de exemplu, mecanicii teoretice, fizicii teoretice, tiin lingvisticii matematice) este construcia deductiv a teoriei, prin care toate afirmaiile decurg, apelnd la construc teoriei, afirma apel deducie, din cteva principii de baz numite axiome. deduc c Dar deducia nu este singura metod de raionament tiinific. deduc ra tiin In acelai timp cu aceasta, n matematic se trece adesea de la propoziii acela propozi particulare la propoziii generale, adic se fac raionamente inductive. propozi ra inductive. Prin inducie se nelege o metod de raionament care conduce de la ra

propoziii particulare la o oarecare propoziie general.

Fig. 1

S dm cteva exemple: c 1. S calculm sumele succesive de numere natural impare: impare: 1, 1+3, 1+3+5, 1+3 + 5 + 7, 1+3 + 5 + 7+9. Obinem, respectiv, numerele 1 = l2, 4 = 22, 9 = 32, 16 = 42, 25 = 52. Ob Observm c n toate cazurile considerate suma este egal cu ptratul numrului termenilor sumei. n mod numrului natural, se poate presupune c aceast proprietate ar putea s aib loc pentru orice astfel de sum (avnd orict poate (av oric de muli termeni). mul Presupunerea (ipoteza) noastr se poate formula astfel: (ipoteza) noastr astfel: Pentru orice numr natural n > 1, are loc egalitatea: 1 + 3 + 5 + ... + (2n - 1) = n2. (1) Astfel cele cinci cazuri particulare ne-au sugerat o ipotez care, dup cum vom arta n continuare este adevrat. necare, dup adevrat. 2. Fie trinomul f(x) = x2 + x + 41. nlocuind pe x cu numerele naturale n = 0, 1, 2, 3, 4, 5, obinem: ob f(0) = 41, f(1) = 43, f(2) = 47, f(3) = 53, f(4) = 61, f(5) = 71. 71. Observm c toate valorile trinomului obinute mai nainte snt numere, prime. Se poate emite ipoteza c valoarea ob s poate trinomului f(x) este numr prim pentru orice numr natural x. Totui, aceast ipotez este fals, deoarece, de exemplu Totu fals, f(40) = 402 + 40 + 41 = 40(40 + 1) + 41 = 41(40 + 1) = 412,care nu este numr prim. prim. De fapt, x = 40 este primul numr natural pentru care f(x) nu este prim. 40 este

Exemplele de mai sus arat c aceeai metod de raionament conduce n unele cazuri la propoziii aceea ra propozi adevrate, iar n altele la propoziii false. adevrate, propozi Deoarece prin aceast metod concluzia se trage dup considerarea ctorva exemple, i nu a tuturor considerarea c cazurilor posibile, aceast metod de raionament se numete inducie incomplet. aceast ra nume induc incomplet. Inducia incomplet, dup cum am vzut, nu conduce mereu la propoziii adevrate, dar este folositoare, Induc incomplet, dup vzut, propozi adevrate, dar deoarece permite s se formuleze o presupunere, care dup aceea poate fi confirmat sau infirmat. presupunere, care infirmat. Cteodat ns, o astfel de metod de raionament poate s conduc, studiind un numr finit de ns, ra conduc, studiind cazuri, la epuizarea tuturor posibilitilor. epuizarea posibilit Iat dou exemple n acest sens: 1. S se demonstreze c fiecare numr natural par n, unde 4 n 20, se poate scrie ca suma a dou 20, se numere prime (care pot fi i egale). Pentru demonstraie s considerm fiecare din numerele pare cuprinse ntre 4 i 20. demonstra Avem: 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 3 + 7, 12 = = 5 + 7, 14 = 7 + 7, 16 = 5 + 11, 18 = 7 + 11, 20 = 7 + 13. 2. S se demonstreze c pentru orice poliedru regulat este ndeplinit relaia V - M +F = 2, unde V este rela numrul vrfurilor, M este numrul muchiilor, iar F este numrul feelor. v muchiilor, fe Pentru demonstraie, este suficient s considerm numai cinci cazuri, i anume: tetraedru, octoedru, cub, demonstra este cazuri, dodecaedru, icosaedru, deoarece nu exist alte poliedre regulate. icosaedru, deoarece regulate. Pentru aceste cinci cazuri afirmaia se verific direct, afirma direct, deoarece pentru tetraedru: V = 4, M = 6, F = 4; pentru octoedru: V = 6, M = 12, F = 8; pentru cub: V = 8, M =12, F = 6; pentru dodecaedru: V = 2a; M = 30; F = 12; pentru icosaedru: V = 12, M = 30, F = 20. ntr-adevr, pentru toate cele cinci poliedre avem: V M + F = 2 ntr-adevr, O astfel de metod de raionament, n care concluzia rezult pe baza cercetrii tuturor ra

cazurilor, se numete inducie complet.

Metoda induciei matematice

Inducia complet are un domeniu restrns de aplicabilitate n matematic. Induc restr matematic. De regul, propoziiile matematice se refer la o mulime infinit de elemente regul, propozi mul (de exemplu, mulimea numerelor naturale, mulimea numerelor prime, mulimea mul mul mul poliedrelor .a.m.d.) i nu este posibil de considerat, pe rnd, toate aceste elemente. r toate Exist ns o metod de a raiona, care nlocuiete analiza, de altfel imposibil de realizat ra nlocuie n practic, a unei mulimi infinite de cazuri practic, mul cu demonstrarea faptului c, dac o propoziie este adevrat ntr-un caz, atunci c, ea se dovedete a fi adevrat i n cazul care succede acestuia. O astfel de metod de raionament se numete inducie matematic. ra nume

S relum presupunerea (ipoteza) fcut n paragraful precedent . Pentru orice numr natural n 1 are loc egalitatea: 1 +3 + 5 + ... + (2n-l) = n2 ,notat: P(n) (propoziie care depinde de n) (1) (2n,notat: (propozi Atunci, faptul c P(l), P(2), P(3), P(4), .P(5) sunt adevrate, nseamn c egalitatea (1) are loc respectiv pentru n = 1, n faptul P(l), adevrate, = 2, n = 3, n = 4, n = 5. ntruct P(5) este adevrat: 1+3 + 5 + 7+9 = 52, avem 1+3 + 5+7+ 9 + 11 = 52 + 25 + 1 = (5 + l)2 = 62, adevrat: 2 adic este adevrat P(6). P(6). Astfel, am demonstrat c dac P(5) este adevrat, rezult c este adevrat P(6). demonstrat P(5) adevrat, rezult P(6). S demonstrm, n acelai mod., c pentru un numr natural oarecare k 1, avem P(k) => P(k + 1). demonstrm, acela mod., Aceasta nseamn c din egalitatea 1 + 3 + 5 + ... + (2k - 1) = k2 s rezulte egalitatea 1 + 3 + 5 + ... + (2k + 1) = (k + l)2. ntr-adevr, ntr-adevr, 1 + 3 + 5 + ... + (2k - 1) + (2k + 1) = [1 + 3 + 5 + .... + (2k - 1)]+ (2k + 1) = k2 + 2k + 1 = (k + l)2. Astfel, egalitatea P(n) este adevrat pentru n = 1, iar din faptul c ea este adevrat pentru n = k, rezult c ea este 1, iar adevrat i pentru n = k + 1. Atunci P(1) => P(2), deoarece 2 = 1 + 1; P(2) => P(3), deoarece 3 = 2 + 1; P(3) => P(4), deoarece 4 = 3 + 1; P(4) => P(5), deoarece 5 = 4+1 .a.m.d.

Pare natural c n modul acesta se poate ajunge pn la orice numr n, adic P(n) este adevrat p pentru orice n 1; deci raionamentul fcut pare convingtor. ra convingtor. Acest raionament este riguros din punct de vedere matematic, deoarece este un caz particular al ra este unui principiu de baz al matematicii, numit principiul induciei matematice (primul principiu de matematicii, induc inducie). induc Acesta se formuleaz astfel: astfel:

Dac o propoziie P(n), n fiind un numr natural, este adevrat pentru n = 0, i, din aceea c ea este adevrat pentru n = k (unde k este un numr natural oarecare) rezult c ea este adevrat i pentru numrul natural n = k + 1, atunci propoziia P(n) este adevrat pentru orice numr natural n.Acest principiu ne d metoda de demonstraie numit metoda induciei matematice. demonstra Fie P(n) o propoziie care depinde de un numr natural n m, m fiind un numr natural fixat. propozi fixat. Demonstraia prin metoda induciei matematice a propoziiei P(n), const din dou etape: Demonstra induc propozi etape: 1 Se verific mai nti c P(m) este adevrat. nt adevrat. 2 Se presupune c P(k) este adevrat i se demonstreaz c P(k + 1) este adevrat, k fiind un numr natural m adevrat, (adic P(k) => P(k + 1), k m). (adic Dac ambele etape ale demonstraiei slnt verificate, atunci propoziia P(n) este adevrat pentru orice numr demonstra propozi P(n) este natural n

Cele dou etape ale demonstraiei prin metoda induciei matematice sunt la fel de importante. demonstra induc Nu nseamn c prima etap este mai puin important dect a doua pu dec

Metoda induciei matematice are o larg utilizare n matematic. induc matematic. Ea poate fi folosit la calcularea de sume i produse, la demonstrarea unor egaliti i inegaliti, egalit inegalit n probleme de divizibilitate a numerelor. numerelor.

Suma primelor n numere naturale (Gauss)S se calculeze suma: suma: Demonstraie. Demonstra

S n = 1 + 2 + 3 + ... + n

S n = 1 + 2 + 3 + ... + (n 1) + n S n = n + ( n 1) + ... + 2 + 1Adunnd relaiile membru cu membru ,obinem: rela ,ob

2 S n = (n + 1) + (n + 1) + ...(n + 1) + (n + 1)Sn = n(n + 1) 2

De unde : 2Sn=n(n+1) i deci presupunem c : P(n): P(n):

Folosim inducia matematic: induc matematic: 1.) P(1): S1=1 evident adevrat. P(1): =1 adevrat. 2.) Artm implicaia: P(k) adevarat =>P(k+1) adevarat implica Scriem P(k): 1+2+3+...+k= k (k + 1) ,relaie care se presupune a fi adevrat i care se va folosi la momentul potrivit. P(k): 1+2+3+...+k= ,rela 2 k +1 k + 2 Scriem P(k+1): 1+2+3+...+k+(k+1)= ,relaie care trebuie dovedit prin calcul. 1+2+3+...+k+(k+1)= ,rela

(

)(

)

2

k (k + 1) k (k + 1)(k + 2) + ( k + 1) = (k + 1) + 1 = Membrul stng este : 1+2+3+...+k+(k+1)= egal cu membrul drept din P(k+1). 1+2+3+...+k+(k+1)= 2 2 2

Prin urmare ,conform metodei induciei ,am demonstrat c : suma primelor n numere naturale este : induc

1 + 2 + 3 + ... + n =

n (n + 1 ) 2

Exemple:1) S se calculeze suma: suma:

Sn =

Demonstraie.

1 1 1 1 + + + ... + 1 2 2 3 3 4 n(n + 1)

Ca s stabilim expresia sumei Sn, calculm suma n cteva cazuri particulare: S1 ,S2, S3, S4 . c Considernd aceste numere formulm ipoteza i dup aceea, pentru demonstrarea ei, folosim metoda induciei aceea, induc matematice.

1 1 S1 = = 1 2 2

1 1 2 S2 = + = 1 2 2 3 3

1 1 1 3 S3 = + + = 1 2 2 3 3 4 41 1 1 1 4 S4 = + + + = 1 2 2 3 3 4 4 5 5Cercetnd aceste sume observm c numrtorul este indicele sumei cutate, iar numitorul este succesorul su Cercet cutate, iar n acest mod, formulm urmtoarea ipotez: P(n): Pentru orice numr natural n I, are loc egalitatea: egalitatea:

1 1 1 n + + ... + = 1 2 2 3 n(n + 1) n + 1

Demonstrm c P(n) este adevrat prin metoda induciei matematice induc

Etapa 1.) P(1) este adevarat ( este chiar S1,care este adevrat) adevrat) Etapa 2.) Demonstrm c: P(k) => P(k + 1) Demonstrm c:

S k +1 =

1 1 1 1 + + ... + + = 1 2 2 3 k (k + 1 ) (k + 1 )(k + 2 )Sk

k 1 k 2 + 2k + 1 k +1 k +1 Sk + = + = = = (k + 1)(k + 2 ) k + 1 (k + 1)(k + 2 ) (k + 1)(k + 2 ) k + 2 (k + 1) + 1 1Ambele etape ale demonstraiei prin metoda induciei matematice sunt verificate. demonstra induc verificate. Prin urmare egalitatea (2) este demonstrat. demonstrat.

2) S se demonstreze c pentru orice n 1, avem:

1 1 1 1 1 1 1 1 1 + + ... + = + + ... + 2 3 4 2n 1 2 n n + 1 n + 2 2n

Demonstraie.Notm cu P(n) egalitatea. 1 Pentru n = 1, egalitatea (3) devine: 1- = i deci P(l) este adevrat. 1P(l) adevrat. 2 Demonstrm c P(k) => P(k + 1). Avem:

1 1 1 1 1 1 1 P(k ) : 1 + + ... + = + ... + (*) 2 3 4 2k 1 2k k + 1 2k1 1 1 1 1 1 1 + = P(k + 1) = 1 + + ... + 2 3 4 2k 1 2k 2k + 1 2(k + 1) 1 1 1 1 + ... + + + (**) k+2 2k 2k + 1 2(k + 1)Scznd membru cu membru, prima egalitate din a doua, obinem egalitatea membru, ob

1 1 1 1 1 = + 2k + 1 2(k + 1) 2k + 1 2k + 2 k + 1care este evident adevrat. adevrat. nseamn c dac este adevrat egalitatea (*) atunci este adevrat i egalitatea (**) . atunci Conform metodei induciei matematice rezult c egalitatea din enun este ndeplinit induc enun pentru orice numr natural n 1.

3) S se demonstreze c dac: dac: x > 1 inegalitatea : (1 + x)n 1 + nx

(4) este adevrat, oricare ar fi numrul natural n adevrat, oricare

Demonstraie. Demonstra S notm cu P(n) inegalitatea (4), pentru numrul natural n. 1 Pentru n = 0, avem (1 + x)0 1 + 0 x = 1, deci P(0) este adevrat. 0, adevrat. 2 S demonstrm P(k) => P(k + 1). nmulim ambii membri ai inegalitii (1 + x)k 1 + kx cu 1 + x. nmul inegalit Cum 1 + x > 0, semnul inegalitii nu se sehimb, deci: 0, semnul inegalit sehimb, k+1 (1 + kx) (1 + x) = 1 + kx + x + kx2. (1 + x) Deoarece kx2 0, cu att mai mult avem: (l + x)k+1 1 + kx + x = 1 + (k + l)x. at Deci (1 + x)k+1 1 + (k + 1)x. Conform metodei induciei matematice rezult inegalitatea (4), pentru orice numr natural. induc natural.

Inegalitatea (4) se numete inegalitatea lui Bernoulli nume Iacob Bernoulli (16541705) matematician elveian.) (1654 elve

S se demonstreze c: n3 n se divide cu 3, pentru orice numr natural n. Demonstraie. Notm cu P(n) propoziia: dn = n3 n se divide cu 3. Deoarece d0 = 0 0 = 0, atunci pentru n = 0, dn se divide cu 3, adic P(0) este adevrat. S demonstrm P(k) => P(k + 1), adic din: dk se divide cu 3, s rezulte c dk+1 se divide cu 3. ntr-adevr, dk+1 = (k + l)3 - (k + 1) = k3 + 3k2 + 3k + 1 - k - 1 = k3 - k + 3(k2 + k) = = dk + 3(k2 + k). Observm c dk+1 este o sum de doi termeni. Primul termen al acestei sume se divide cu 3, iar al doilea termen este evident divizibil cu 3. Prin urmare, fiecare termen al sumei dk+1 se divide cu 3, de unde i dk+1 se divide cu 3. Propoziia este demonstrat. 4)

5) S se demonstreze c: c: numrul funciilor definite pe o mulime cu n elemente ntr-o mulime cu m elemente este mn. func mul ntr- mul Demonstraie. Demonstra Fie A = {a1, a2 ...,an} i B = {b1, b2, ..., bm) dou mulimi, avnd n, respectiv m elemente. ...,a mul av S artm c numrul funciilor definite pe A. cu valori n B este mn. func Demonstrm prin metoda induciei matematice, dup n. induc dup n. Fie P(n) afirmaia: Numrul funciilor definite pe o mulime cu n elemente ntr-o mulime cu m elemente estemn. afirma func mul ntr- mul 1 P(l) este adevrat, deoarece evident de la o mulime cu un element ntr-o mulime cu m elemente sunt m = ml adevrat, mul ntr- mul funcii. Fiecare astfel de funcie duce unicul element al mulimii A ntr-unul din cele m elemente ale mulimii B. func func mul ntrmul 2 S artm c P(k) => P(k + 1). Fie mulimea A = {a1; a2, ..., ak+1} cu k + 1 elemente. S considerm A' = A {ak+1} = mul elemente. { a1,, ak}.Cum P(k) este adevrat rezult c numrul funciilor definite pe A' cu valori n B este mk. Dac f: A' -> B , func f: este o funcie oarecare, atunci definim fi : A -> B, prin fi(aj) = f(aj) i fi(ak+1) = b, unde 1 i m. Aadar pentru orice func B, funcie de la A' la B se obin m funcii de la A la B. Mai mult, toate funciile de la A la B snt de acest tip. Deci numrul func ob func func funciilor de la A la B este mk m = mk+1, Conform metodei induciei matematice afirmaia este demonstrat. func induc afirma