Inducția matematică

Inducția matematică este o metodă de demonstrare folosită frecvent în matematică, mai ales când lucrăm cu numere naturale sau cu un alt șir.

Principiul

Principiul de bază este că demonstrăm afirmația dată pentru un prim element; în numerele naturale acesta este cel mai des n = 1 (uneori zero). Aceasta este etapa de verificare și se face prin simplă înlocuire. În a doua etapă, etapa de demonstrație, demonstrăm implicația „dacă afirmația este adevărată pentru n = a, atunci este adevărată și pentru n = a + 1”.

Din aceste două etape putem deduce că expresia dată este adevărată pentru toți n (dintr-o mulțime cu care lucrăm). De ce este așa? La început demonstrăm că expresia este adevărată pentru n = 1. În același timp știm că, dacă expresia este adevărată pentru n = a, este adevărată și pentru n = a + 1. Alegem deci a = 1. Știm că pentru a = 1 expresia este adevărată și știm și că este adevărată pentru a + 1 = 2. În acest moment știm că expresia este adevărată pentru a = 2. Dar, deoarece este adevărată și pentru a + 1, trebuie să fie adevărată și pentru 2 + 1 = 3. Și așa mai departe.

Primul exemplu

Primul exemplu va fi banal. Demonstrăm că, dacă la orice număr par adunăm doi, obținem din nou un număr par. Deoarece ne aflăm în numerele naturale, scriem un număr par oarecare ca 2n, unde n este număr natural nenul. Dacă îl înlocuim pe n cu orice număr natural nenul, obținem un rezultat par, se vede imediat. Divizibilitatea se notează cu bara verticală astfel:

$$2\mid 2n$$

Această scriere înseamnă că doi îl divide exact pe 2n. Acum că știm să scriem divizibilitatea, putem scrie și ceea ce avem de demonstrat prin inducție matematică.

$$2\mid 2n+2;n\in {\mathbb{N}}^{\ast }$$

Aceasta este cerința primului exemplu, adică doi divide expresia 2n + 2 – corespunde exact enunțului inițial în cuvinte „dacă la orice număr par adunăm doi, obținem din nou un număr par”.

În etapa de verificare demonstrăm afirmația pentru primul element, pentru unu. Înlocuim în expresie n = 1:

$$\begin{array}{rcl}2& \mid & 2\cdot 1+2\\ 2& \mid & 4\end{array}$$

Doi îl divide exact pe patru, deci pentru primul element afirmația este adevărată. Urmează etapa de demonstrație, în care trebuie să demonstrăm că, dacă afirmația este adevărată pentru al a-lea element, atunci este adevărată și pentru al (a + 1)-lea element. La început presupunem că ipoteza noastră este adevărată, adică n = a:

$$2\mid 2a+2$$

Despre această expresie presupunem că este adevărată – o vom folosi la construirea demonstrației. Vrem acum să demonstrăm că

$$2\mid 2(a+1)+2.$$

Ce am făcut? În locul lui a am scris (a + 1). Parantezele sunt importante, această expresie ar fi greșită: 2a + 1 + 2. Nu adunăm unu la întreaga expresie, ci chiar facem din a o expresie cu unu mai mare, adică (a + 1). Transformăm expresia desfăcând paranteza.

$$\begin{array}{rcl}2& \mid & 2(a+1)+2\\ 2& \mid & 2a+2+2\end{array}$$

Acum o mică paranteză despre divizibilitate. Dacă avem două numere, să zicem p și q, divizibile cu un număr, fie el r, atunci și suma lor este divizibilă cu r. Are loc deci:

$$(r\mid p\wedge r\mid q)\Rightarrow r\mid (p+q)$$

Putem înlocui aici, de exemplu, numerele p = 8, q = 20 și r = 4. Vedem că patru îl divide și pe opt, și pe douăzeci. Și, la fel, divide și suma lor 8 + 20 = 28.

Cum folosim asta în exemplul nostru? Împărțim membrul drept în numerele p și q astfel:

$$p=2a+2;q=2$$

Numărul q, adică doi, este în mod banal divizibil cu doi. Iar expresia p este și ea divizibilă cu doi, deoarece ne spune acest lucru ipoteza de inducție. Expresia p corespunde exact ipotezei noastre, despre care presupunem că este adevărată. Iar dacă p este divizibil cu doi și, în același timp, q este divizibil cu doi, atunci și suma lor este divizibilă cu doi.

Încă o dată despre ipoteză. La început am spus că presupunem adevărat că

$$2\mid 2a+2.$$

De aceea, când în timpul construirii demonstrației am întâlnit expresia 2a + 2, am putut spune despre ea că este divizibilă cu doi. Tocmai pentru că este ipoteza noastră. Acesta este de obicei cel mai greu pas al inducției matematice – să înțelegi când și de ce poți folosi ipoteza de inducție.

Cu aceasta inducția se încheie, demonstrația a fost făcută cu succes, afirmația este adevărată.

Dacă ai vrea, ai putea să descompui altfel și să nu folosești ipoteza. p = 2n și q = 2 + 2. Numărul q = 4 este în mod banal divizibil cu doi și la fel p = 2n, deoarece după împărțirea la doi ne rămâne numărul n, care este natural, adică întreg. Am obținut din nou două expresii care sunt ambele divizibile cu doi, deci și suma lor este divizibilă cu doi.

În ambele cazuri am demonstrat însă că

1. expresia dată este adevărată pentru n = 1,
2. dacă expresia este adevărată pentru n, atunci este adevărată și pentru n + 1.

De aici putem deduce:

• Știm că expresia este adevărată pentru n = 1.
• Dacă este adevărată pentru n, trebuie să fie adevărată și pentru n + 1, adică și pentru 1 + 1, deci expresia este adevărată și pentru n = 2.
• Dacă este adevărată pentru n, trebuie să fie adevărată și pentru n + 1, adică și pentru 2 + 1, deci expresia este adevărată și pentru n = 3.
• Dacă este adevărată pentru n, trebuie să fie adevărată și pentru n + 1, adică și pentru 3 + 1, deci expresia este adevărată și pentru n = 4.
• Dacă este adevărată pentru n, trebuie să fie adevărată și pentru n + 1, adică și pentru 4 + 1, deci expresia este adevărată și pentru n = 5.
• …

Al doilea exemplu

Mai departe demonstrăm prin inducție matematică o afirmație simplă:

$$2^n\ge 2n;n\in {\mathbb{N}}^{\ast }.$$

Mai întâi etapa de verificare: aflăm dacă afirmația este adevărată pentru n = 1, ca prim element al numerelor naturale nenule din care alegem pe n.

$$\begin{array}{rcl}{2}^1& \ge & 2\cdot 1\\ 2& \ge & 2\end{array}$$

Aceasta este în mod banal adevărată. Acum trecem la etapa de demonstrație, în care trebuie să aflăm dacă, atunci când afirmația este adevărată pentru n = a, este adevărată și pentru n = a + 1. Ipoteza noastră este deci că are loc

$$2^a\ge 2a$$

și vrem să demonstrăm:

$$2^{a+1}\ge 2(a+1)$$

Membrul stâng îl scriem mai întâi cu ajutorul regulilor de calcul cu puteri, iar membrul drept îl desfacem simplu.

$$2\cdot 2^a\ge 2a+2$$

În membrul stâng folosim adunarea în loc de înmulțire, iar membrul drept îl lăsăm neschimbat.

$$2^a+2^a\ge 2a+2$$

Acum folosim ipoteza. Ipoteza este o afirmație despre care presupunem că este adevărată. În inegalitate avem în ambii membri câte doi termeni adunați. În același timp știm că

$$\begin{array}{rcl}{2}^a& \ge & 2a\\ 2^a& \ge & 2.\end{array}$$

Prima linie ne-o spune ipoteza, iar a doua afirmație este banală (cel mai mic 2^a este pentru a = 1 și acesta este egal tocmai cu doi). Deci știm că în membrul stâng ambii termeni sunt mai mari sau egali cu ambii termeni din membrul drept. Am demonstrat astfel prin inducție că, dacă expresia este adevărată pentru a, atunci este adevărată și pentru (a + 1) și, deoarece expresia este adevărată și pentru unu, expresia dată este adevărată.

Al treilea exemplu

Încercăm să demonstrăm următoarea afirmație:

$$3\mid n\Rightarrow 3\mid n^2;n\in {\mathbb{N}}^{\ast }$$

În cuvinte: dacă n este divizibil cu trei, atunci și n² este divizibil cu trei. Dacă n nu este divizibil cu trei, atunci afirmația este în mod banal adevărată (din definiția implicației), așa că ne ocupăm de cazurile în care n este divizibil cu trei. Acest lucru ne generează șirul de numere naturale a_i=3, 6, 9, 12, 15… Din acest moment ne mișcăm în acest șir a_i.

Demonstrația prin inducție începe cu etapa de verificare, adică verificăm dacă afirmația este adevărată pentru primul element. Îți amintesc că ne aflăm în șirul a_i, deci luăm primul element al acestui șir, adică elementul a₁, care este trei. Pentru trei expresia este adevărată:

$$3\mid 3\Rightarrow 3\mid 3^2$$

Acum trecem la etapa de demonstrație. Vedem că șirul a_i s-ar putea scrie ca 3n, unde n este număr natural nenul. Deci al doilea element este cu trei mai mare decât cel precedent și așa mai departe. Presupunem acum că expresia este adevărată pentru n și trebuie să ne asigurăm că este adevărată și pentru (n + 3), adică regula care generează următorul element din șirul în care ne mișcăm. Scriem mai întâi ipoteza:

$$3\mid n\Rightarrow 3\mid n^2$$

și apoi ceea ce vrem să demonstrăm

$$3\mid (n+3)\Rightarrow 3\mid (n+3{)}^2.$$

Desfacem paranteza din partea dreaptă cu ajutorul formulei:

$$3\mid (n+3)\Rightarrow 3\mid n^2+6n+9.$$

Și suntem aproape la țintă. În partea stângă avem o expresie care este sigur divizibilă cu trei, deoarece n este, conform ipotezei, divizibil cu trei (ne mișcăm doar printre numerele din șirul a_i), iar trei este și el divizibil cu trei. În partea dreaptă avem mai întâi n², care, conform ipotezei, este divizibil cu trei. Știm într-adevăr că n este divizibil cu trei, iar ipoteza spune că, dacă n este divizibil cu trei, atunci și n² este divizibil cu trei:

$$3\mid n\Rightarrow 3\mid n^2$$

Urmează expresia 6n, care este în mod banal divizibilă cu trei. Poți să ți-o imaginezi ca pe o simplificare de fracții:

$$\frac{6n}{3}=2n$$

Variabila n este un număr natural, deci și produsul 2n va fi număr natural, adică după împărțirea la trei am obținut un număr natural, deci expresia 6n trebuie să fie divizibilă cu trei. Iar nouă de la sfârșit este din nou divizibil cu trei. Expresia este adevărată pentru primul element și în etapa de demonstrație, deci este adevărată.

Numărul de paranteze dintr-o expresie

Ultimul exemplu va fi puțin atipic. Încercăm să demonstrăm afirmația că numărul de paranteze dintr-o expresie simplă este mereu par, ca să vezi că inducția matematică se poate folosi și într-un context cu totul diferit de numerele naturale. La început trebuie să definim ce este o expresie simplă. O expresie simplă este:

• un număr natural,
• dacă p este o expresie simplă, atunci și (p²) este o expresie simplă,
• dacă p și q sunt expresii simple, atunci și (p + q) este o expresie simplă.

Deci iată ce este o expresie simplă: 12, 54, (5 + 6), (12 + 7), (6²), ((5 + 6)²). Și, dimpotrivă, acestea nu sunt expresii simple:

• 1 + 2 → lipsesc parantezele exterioare,
• (1 + 2 → lipsește paranteza dreaptă,
• 13² → lipsesc parantezele exterioare,
• (1 + 2 + 3) → lipsesc parantezele, scrierea corectă ar trebui să fie (1 + (2 + 3))

O expresie simplă poate apărea, de exemplu, așa. La început alegem o expresie simplă (a + b). Acum în locul lui a punem o expresie simplă a = (c + d), deci obținem ((c + d) + b), iar în locul lui b punem trei: ((c + d) + 3). În locul lui c punem zece: ((10 + d) + 3) și, la final, în locul lui d punem (5²): ((10 + (5²)) + 3). Este important să respecți parantezele, altfel nu va funcționa.

Acum demonstrăm că o expresie simplă conține un număr par de paranteze (printre numerele pare se află și zero).

În etapa de verificare alegem un prim element. În acest caz primul element va fi cea mai banală expresie simplă, adică orice număr natural. Deci punem

$$j=n;n\in \mathbb{N}.$$

Pentru expresia j numărul de paranteze este zero, deci primul element verifică. În etapa de demonstrație presupunem că avem două expresii simple p și q și că ambele au un număr par de paranteze. Apoi trebuie să demonstrăm că și expresiile simple (p + q) și (p²) au un număr par de paranteze.

Mai întâi adunarea. Definim încă o funcție z(q), care returnează numărul de paranteze ale expresiei q. Atunci expresia (p + q) are z(p) + z(q) + 2 paranteze. Deci are cu două paranteze mai mult decât suma parantezelor expresiilor p și q. Conform ipotezei, atât z(p), cât și z(q) sunt pare, deci dacă adunăm trei numere pare, obținem din nou un număr par. Pentru acest caz afirmația este adevărată.

Acum puterea. Din nou are loc ipoteza că expresia simplă p conține un număr par de paranteze. Expresia (p²) conține atunci z(p) + 2 paranteze, deci din nou cu două paranteze mai mult decât expresia p. Și în acest caz adunăm numere pare, rezultatul este deci par.

Afirmația este adevărată pentru primul element și este adevărată și în etapa de demonstrație, de aceea afirmația este adevărată.