Faceți căutări pe acest blog

joi, 4 septembrie 2014

Inducția matematică


Inducția matematică este o formă de raționament prin care se poate demonstra frumos o formulă ce depinde de un număr natural. De regulă, când vi se cere să demonstrați o formulă care conține un număr natural sub forma unei litere (de exemplu, cu $n$), ar cam trebui să aplicați inducția matematică.

Pentru a demonstra o formulă prin inducție matematică va trebui să parcurgeți două etape, ambele etape fiind necesare pentru o demonstrație riguroasă:
-prima este etapa de verificare;
-a doua este etapa de generalizare.



Cea mai simplă este prima etapă. E simplă deoarece constă într-un calcul simplu, cu numere concrete. Mai greu este să știi ce numere concrete să alegi pentru a nu ieși din domeniul de definiție al formulei.

Această etapă de calcul se împarte în alte două sub-etape:
-sub-etapa în care faceți calculul cu numărul concret.
-sub-etapa în care faceți înlocuirea cu numărul concret.

Apoi comparați cele două rezultate, iar dacă ele coincid, înseamnă că ați trecut cu succes de etapa de verificare. Dacă nu coincid, atunci ori ați ales greșit numărul, ori ați greșit la calcul sau la înlocuire, ori formula este pur și simplu greșită.




În schimb, al doilea pas, ce reprezintă etapa de generalizare, conține niște ciudățenii care trebuie bine explicate. Spre deosebire de etapa de verificare, ce folosea numere concrete, această etapă folosește litere (deci, numere generale) și se împarte și ea la rândul ei în trei sub-etape:

-Sub-etapa de presupunere, care constă în a presupune că numărul concret pe care l-am fi putut alege în etapa de verificare putea fi oricare număr până la numărul $k$ inclusiv. Cu alte cuvinte, în această sub-etapă presupunem că am parcurs etapa de verificare pentru toate numerele mai mici sau egale cu numărul oarecare $k$.

Pe baza acestei presupuneri, obținem dreptul să considerăm că formula ce se cere a fi demonstrată este adevărată măcar pentru toate numerele mai mici sau egale cu $k$. Vom avea mare nevoie de această presupunere în sub-etapa de calcul care urmează, deoarece această presupunere constituie un stâlp solid pe care ne vom putea clădi raționamentul final.

-Sub-etapa de calcul cu numărul general $k+1$ în care veți determina cât trebuie să fie expresia finală conform calculului cu numărul general. În această sub-etapă vă veți folosi cu brio de presupunerea făcută la sub-etapa anterioară.

-Sub-etapa de înlocuire cu numărul general $k+1$, în care veți determina cât trebuie să fie expresia finală prin simpla înlocuire a lui $n$ cu numărul general $k+1$.

În final, veți compara rezultatul obținut în sub-etapa a doua cu rezultatul obținut în sub-etapa a treia. Dacă cele două rezultate coincid, atunci ați trecut cu succes și de etapa de generalizare și puteți considera că formula dată este complet demonstrată prin inducție matematică. Dacă apar probleme, atunci ele trebuie să vă pună pe gânduri.





Vreau să lucrăm acum pe două exemple ușoare.

Întâi, să demonstrăm prin inducție matematică egalitatea banală și evidentă:
$2+2+2+...+2$ de $n$ ori este $2\cdot n$, valabilă pentru orice număr natural.

1. Așa cum ați văzut mai sus, prima etapă este cea în care verificăm dacă există vreun număr natural pentru care să fie adevărată această formulă. De regulă, e bine să alegem numere mici pentru verificare, deoarece nu este util să facem calcule laborioase cu numere mari. Nu vom alege ca număr de verificare numărul $n=1000$, ci vom alege, să zicem, $n=3$, pentru claritate, deși puteam alege tocmai numărul $n=1$ sau, de ce nu, chiar $n=0$. Noi îl vom alege totuși pe $n=3$ pentru ca începătorul să vadă mai clar cum se desfășoară etapa de verificare.

Așadar, pentru $n=3$, vom parcurge etapa de verificare. Aceasta va consta în parcurgerea primei sub-etape, urmată apoi de cea de-a doua sub-etapă. În prima sub-etapă vom face calculul cu numărul concret $n=3$. Asta înseamnă că vom determina $2+2+2$ de 3 ori, deci vom determina cât este membrul din stânga egalității ce trebuie demonstrată. Avem, desigur, $2+2+2=2\cdot 3=\color{blue}{6}$. Punct.

Trecem la a doua sub-etapă a primei etape și vom face înlocuirea cu numărul concret $n=3$. Asta înseamnă că în membrul drept al egalității care trebuie demonstrată vom înlocui litera $n$ cu numărul nostru concret 3. Așadar, în expresia $2\cdot n$ îl vom înlocui pe $n$ cu 3. Obținem atunci după înlocuire $2\cdot 3=\color{blue}{6}$.

Acum comparăm cele două rezultate obținute în cele două sub-etape. Desigur, în ambele sub-etape am obținut același număr, 6. Asta înseamnă că etapa de verificare s-a încheiat cu succes și putem trece mai departe la etapa de generalizare. Desigur, am fi putut să mai încercăm etapa de verificare și pentru alte numere, nu doar pentru numărul 3. Puteam face verificare și pentru numărul 4, apoi pentru numărul 5, apoi pentru numărul 6 și așa mai departe. Nu contează câte verificări facem, dar important este să facem măcar una. În plus, nu e obligatoriu să faceți mai multe verificări, ci ajunge numai una.

În etapa de generalizare avem de parcurs cele trei sub-etape. Etapa de presupunere în cazul nostru constă în a presupune că etapa de verificare s-ar fi încheiat cu succes nu doar pentru numărul 3, ci și pentru numărul 4, pentru numărul 5, pentru numărul 6 și așa mai departe până la numărul $k$, oricare ar fi acesta. Ce rost are să le încercăm pe toate pe rând? Mai bine folosim litera $k$ și ne-am scăpat de o grămadă de muncă „mințind” astfel că am încercat în etapa de verificare toate numerele până la $k$. Asta înseamnă că noi ne putem încrede în formula $2+2+2+...+2$ de $k$ ori este $2\cdot k$, care, după cum puteți observa, nu este altceva decât tocmai formula inițială, numai că în loc de $n$ apare $k$.

Trecem mai departe la sub-etapa de calcul cu numărul $k+1$. Asta înseamnă că trebuie să calculăm ce valoare obținem pentru membrul stâng al egalității dacă îl adunăm pe 2 cu el însuși de $k+1$ ori, știind că putem să ne folosim de presupunerea anterioară că suma a $k$ de 2 este $2\cdot k$. Așadar, vom avea $2+2+...+2+2$ de $k+1$ ori este $2+2+...+2$ de $k$ ori, plus încă un 2. Prin urmare, $2+2+...+2+2$ de $k+1$ este $\color{blue}{2\cdot k+2}$. Acesta este rezultatul calculului.

Să vedem acum cât este rezultatul înlocuirii. Suntem acum în sub-etapa a treia. În această sub-etapă îl înlocuim pe $n$ din membrul drept al formulei de demonstrat cu $k+1$ și vedem cât ne dă. Astfel, înlocuim $2\cdot n$ cu $\color{blue}{2\cdot(k+1)}$. Coincid cele două rezultate „albastre”? Desigur. Căci $2\cdot(k+1)=2\cdot k+2\cdot 1=2\cdot k+2$. Coincidența acestor două rezultate ne-a adus la finalul demonstrației. Putem fi liniștiți acum că am demonstrat complet relația cerută.






Să luăm un alt exemplu, puțin mai complex, dar în care veți observa mai clar desfășurarea și rolul inducției matematice. Exemplul folosit va fi suma lui Gauss. 

Poate știți că
$$1+2+3+4+...+98+99+100=\frac{100\cdot 101}{2}.$$

În general, ar trebui să fie adevărat că
$$1+2+3+...+n=\frac{n(n+1)}{2}$$.

Haideți să demonstrăm că este adevărat acest lucru. Demonstrăm aceasta prin inducție matematică, așa cum am învățat aici.




Parcurgem prima etapă, de verificare. Să alegem ca număr concret numărul $n=2$. Să verificăm atunci dacă formula lui Gauss este adevărată măcar pentru $n=2$.

În prima sub-etapă calculăm membrul din stânga egalității, adică vom calcula $1+2$, care este evident $\color{blue}{3}$.

În a doua sub-etapă a etapei de verificare înlocuim în membrul drept al egalității pe $n$ cu 2. Obținem deci în loc de $\frac{n(n+1)}{2}$ valoarea $\frac{2(2+1)}{2}$ care este $\frac{2(2+1)}{2}=\frac{2\cdot 3}{2}=\color{blue}{3}$.

Am obținut, așadar, coincidența celor două rezultate și ne putem declara eliberați de etapa de verificare. Trecem atunci la etapa e generalizare.




Prima sub-etapă a etapei e generalizare va fi să presupunem că am verificat formula lui Gauss pentru o grămadă de numere naturale, inclusiv pentru numărul $k$, așa încât putem să ne bazăm liniștiți pe formula
$$1+2+3+...+k=\frac{k(k+1)}{2}.$$


Cu această presupunere în minte, vom trece la sub-etapa a doua, prin care vom determina prin calcul membrul stâng al formulei lui Gauss în care facem adunarea până la $n=k+1$ inclusiv. Acest membru stâng devine atunci
$$1+2+3+...+k+(k+1).$$
Dar presupunerea extraordinară de la sub-etapa anterioară ne permite să ne folosim de faptul că $1+2+3+...+k=\frac{k(k+1)}{2}$. Astfel, membrul nostru stâng devine
$$\color{red}{1+2+3+...+k}+(k+1)=\color{red}{\frac{k(k+1)}{2}}+(k+1).$$
Ținem minte, deci, rezultatul
$$\color{blue}{\frac{k(k+1)}{2}+(k+1)}$$
pentru a-l putea compara cu rezultatul pe care îl vom obține în ultima sub-etapă.

În sub-etapa a treia ne ocupăm de membrul din dreapta al formulei lui Gauss. Mai exact, vom înlocui în membrul drept pe $n$ cu $k+1$. Obținem, deci, în loc de $\frac{n(n+1)}{2}$ expresia
$$\color{blue}{\frac{(k+1)[(k+1)+1]}{2}}.$$

Oare coincid cele două rezultate „albastre” obținute în cele două sub-etape anterioare? Coincid, desigur. Deoarece primul rezultat poate fi adus, după scoaterea factorului comun $k+1$, la forma
$$\frac{k(k+1)}{2}+(k+1)=(k+1)\left(\frac{k}{2}+1\right)=(k+1)\frac{k+2}{2},$$
care este absolut identic cu al doilea rezultat
$$\frac{(k+1)[(k+1)+1]}{2}=(k+1)\frac{k+2}{2}.$$
Această coincidență pune punct demonstrației prin inducție matematică a relației lui Gauss.

Recunosc, n-a fost ușor să stabilim coincidența celor două rezultate albastre. Ba chiar, pentru unii elevi această coincidență este foarte greu de stabilit, atât e greu de stabilit încât poate că ar fi trebuit să-i dedicăm acestei coincidențe o sub-etapă separată pentru etapa de generalizare, admițând astfel că etapa de generalizare ar trebui să fie constituită de fapt din patru sub-etape, ultima sub-etapă constând în stabilirea coincidenței rezultatelor albastre.

Dar ce mai contează acum modul în care ne împărțim lucrul? De voi depinde cum vă organizați pentru a face demonstrația prin inducție matematică a unei formule. Important este să parcurgeți complet cele două etape necesare demonstrației, etapa de verificare și etapa de generalizare.

Dacă ați înțeles și v-a plăcut descrierea pe care v-am oferit-o eu aici pentru inducția matematică, povestiți-le despre aceasta și prietenilor voștri dragi la care țineți voi mai mult, pentru ca și ei să știe de blogul acesta atunci când vor avea nevoie.