Inducție matematică — definiție, metodă și exemple

Inducția matematică este o tehnică fundamentală de demonstrare folosită pentru a arăta că o proprietate este adevărată pentru toate numerele naturale (sau pentru toate numerele întregi pozitive începând dintr-un anumit punct). Ideea de bază este simplă: dacă putem demonstra că o afirmație este adevărată pentru primul caz (cazul de bază) și dacă din adevărul pentru un caz urmează adevărul pentru cazul următor (pasul inductiv), atunci afirmația este adevărată pentru toate cazurile succesive.

Structura unei demonstrații prin inducție

Precizare: Se spune clar că demonstrația se face prin inducție pe n {\displaystyle n} (aceasta este variabila de inducție).
Cazul de bază: Se arată că afirmația este adevărată pentru primul număr pentru care dorim să o demonstrăm (de obicei = 1 sau alt punct de start specificat).
Ipoteza de inducție: Presupunem că afirmația este adevărată pentru un număr arbitrar, dar fix, .
Pasul inductiv: Arătăm că, sub ipoteza că afirmația e adevărată pentru , rezultă că este adevărată și pentru următorul număr, $n+1$ . Dacă acest pas este corect, atunci, deoarece este adevărată pentru primul număr, va fi adevărată pentru al doilea, apoi pentru al treilea și așa mai departe.

Varianta riguroasă (formularea logică)

Mai formal: fie P(n) o propoziție dependentă de un număr natural n. Dacă demonstrăm:

P(n0) este adevărată pentru un punct de plecare n0 (cazul de bază);
pentru orice k ≥ n0, P(k) ⇒ P(k+1) (pasul inductiv);

atunci P(n) este adevărată pentru toate n ≥ n0.

Exemple concrete

1) Suma primelor n numere naturale

Afirmație: 1 + 2 + ... + n = n(n + 1)/2 pentru orice n ≥ 1.

Cazul de bază: n = 1: 1 = 1(1+1)/2 = 1 — adevărat.
Ipoteza de inducție: presupunem 1 + 2 + ... + n = n(n + 1)/2 pentru un n arbitrar.
Pasul inductiv: atunci 1 + 2 + ... + n + (n + 1) = n(n + 1)/2 + (n + 1) = (n(n + 1) + 2(n + 1))/2 = (n + 1)(n + 2)/2, ceea ce înseamnă că formula este valabilă și pentru n + 1. Prin urmare se aplică pentru orice n ≥ 1.

2) Divizibilitate

Afirmație: 2^n − 1 este divizibil cu 3 pentru orice n impar (n = 1, 3, 5, ...).

Cazul de bază: n = 1: 2^1 − 1 = 1, nu este divizibil cu 3 — deci aici e nevoie să alegem corect enunțul. Un enunț corect ar fi: 2^n − 1 este divizibil cu 3 pentru orice n impar ≥ 1 nu este adevărat; în schimb, 2^{2k+1} − 1 este divizibil cu 3 pentru orice k ≥ 0 poate fi verificat arătând periodicitatea modulului 3. (Exemplu: 2^1 ≡ 2 (mod 3), 2^2 ≡ 1 (mod 3), 2^3 ≡ 2 (mod 3) ș.a.m.d.)
Acest exemplu arată importanța formulării corecte a enunțului și a alegerii unui punct de plecare adecvat.

3) Inegalitate

Afirmație: pentru orice n ≥ 1, 2^n ≥ n + 1.

Cazul de bază: n = 1: 2^1 = 2 ≥ 2 — adevărat.
Ipoteza: presupunem 2^n ≥ n + 1.
Pasul: 2^{n+1} = 2·2^n ≥ 2(n + 1) = n + 1 + (n + 1) ≥ n + 2 pentru n ≥ 1, deci 2^{n+1} ≥ (n + 1) + 1 = (n + 1) + 1 — se obține 2^{n+1} ≥ (n + 1) + 1, ceea ce dovedește afirmația pentru n + 1. (Detaliile pot fi ajustate pentru o demonstrație mai fină.)

Inducție puternică (sau completă)

În inducția puternică, ipoteza de inducție presupune că afirmația este adevărată pentru toate cazurile ≤ n și folosește această ipoteză pentru a dovedi cazul n + 1. Aceasta este utilă când pentru a demonstra P(n+1) ai nevoie nu doar de P(n), ci și de P(n−1), P(n−2) etc. Structura rămâne aceeași: caz de bază (uneori mai multe cazuri de bază) și pasul inductiv (care utilizează ipoteza pentru toți k ≤ n).

Sfaturi și capcane frecvente

Verificați întotdeauna cazurile de bază. Uneori sunt necesare mai multe cazuri de bază (de exemplu, când pasul inductiv folosește P(n−1)).
Formularea enunțului trebuie să precizeze clar pentru ce valori ale lui n se face inducția (de exemplu, n ≥ 0 sau n ≥ 1 sau n ≥ 5 etc.).
Nu confundați ipoteza de inducție (presupunem P(n)) cu concluzia (trebuie dovedit P(n+1)). Trebuie folosită doar ca ipoteză, nu ca premisă deja dovedită.
Când demonstrați inegalități sau proprietăți de ordinul algebric, manipulați expresiile astfel încât să folosiți direct ipoteza de inducție.

Când nu se aplică inducția?

Inducția este potrivită pentru proprietăți care au o structură „pas cu pas” pe numerele naturale. Nu este un instrument pentru a demonstra afirmații care nu au această structură recurentă sau pentru mulțimi care nu sunt ordonate natural. În plus, dacă enunțul nu implică un pas clar de la n la n+1, poate fi nevoie de altă metodă (contradicție, argument combinatoric, analiză matematică etc.).

În concluzie, inducția matematică este o metodă elegantă și foarte puternică, indispensabilă în aproape toate ramurile matematicii discrete și nu numai. Exersarea mai multor exemple (sumă, produs, divizibilitate, inegalități, proprietăţi ale șirurilor recurente) ajută la stăpânirea tehnicii și la recunoașterea cazurilor în care se aplică cel mai bine.

Exemple de dovezi prin inducție

Suma primelor n numere naturale

Demonstrați că pentru toate numerele naturale n:

1 + 2 + 3 + . . . . + ( n - 1 ) + n = 1 2 n ( n + 1 ) {\displaystyle 1+2+3+....+(n-1)+n={\tfrac {1}{2}}}n(n+1)} $1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)$

Dovada:

În primul rând, afirmația poate fi scrisă sub forma:

2 ∑ k = 1 n k = n ( n + 1 ) {\displaystyle 2\sum _{k=1}^{n}k=n(n+1)} $2\sum _{k=1}^{n}k=n(n+1)$ (pentru toate numerele naturale n)

Prin inducție pe n,

În primul rând, pentru n=1:

2 ∑ k = 1 1 k = 2 ( 1 ) = 1 ( 1 + 1 ) {\displaystyle 2\sum _{k=1}^{1}k=2(1)=1(1+1)} $2\sum _{k=1}^{1}k=2(1)=1(1+1)$ ,

deci acest lucru este adevărat.

În continuare, să presupunem că pentru un anumit n=n₀ afirmația este adevărată. Adică,:

2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)} $2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)$

Atunci, pentru n=n₀ +1:

2 ∑ k = 1 n 0 + 1 k {\displaystyle 2\sum _{k=1}^{{{n_{0}}+1}k}k} $2\sum _{k=1}^{{n_{0}}+1}k$

poate fi rescrisă sub forma

2 ( ∑ k = 1 n 0 k + ( n 0 + 1 ) ) {\displaystyle 2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)} $2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)$

Deoarece 2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) , {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),} $2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),$

2 ∑ k = 1 n 0 + 1 k = n 0 ( n 0 + 1 ) + 2 ( n 0 + 1 ) = ( n 0 + 1 ) ( n 0 + 2 ) {\displaystyle 2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)} $2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)$

Prin urmare, dovada este completă prin inducție.

Suma unghiurilor interioare ale unui poligon

Inducția matematică este deseori enunțată cu valoarea inițială 0 (și nu 1). De fapt, ea va funcționa la fel de bine cu o varietate de valori de pornire. Iată un exemplu în care valoarea de pornire este 3: "Suma unghiurilor interioare ale unui poligon cu n {\displaystyle n} laturi este ( n - 2 ) 180 {\displaystyle (n-2)180} $(n-2)180$ grade."

Valoarea inițială de pornire este 3, iar unghiurile interioare ale unui triunghi sunt ( 3 - 2 ) 180 {\displaystyle (3-2)180} $(3-2)180$ grade. Să presupunem că unghiurile interioare ale unui poligon cu n {\displaystyle n} laturi sunt ( n - 2 ) 180 {\displaystyle (n-2)180} $(n-2)180$ grade. Adăugați un triunghi care face ca figura să fie n + 1 {\displaystyle n+1}. $n+1$ cu 180 de grade ( n - 2 ) 180 + 180 = ( n + 1 - 2 ) 180 {\displaystyle (n-2)180+180=(n+1-2)180} $(n-2)180+180=(n+1-2)180$ grade. Deoarece sunt tratate atât cazul de bază, cât și cazul inductiv, demonstrația este acum completă.

Există un număr mare de obiecte matematice pentru care funcționează demonstrațiile prin inducție matematică. Termenul tehnic este "set bine ordonat".

Definiție inductivă

Aceeași idee poate funcționa pentru a defini un set de obiecte, precum și pentru a demonstra afirmații despre acel set de obiecte.

De exemplu, putem defini n {\displaystyle n} vărsta de gradul al treilea după cum urmează:

Un văr de gradul 1 {\displaystyle 1} $1$ de gradul 1 este copilul unui frate al unui părinte.
Un văr de gradul n + 1 {\displaystyle n+1} $n+1$ st este copilul unui văr de gradul n {\displaystyle n} th al unui părinte.

Există un set de axiome pentru aritmetica numerelor naturale care se bazează pe inducția matematică. Acestea se numesc "Axiomele lui Peano". Simbolurile nedefinite sunt | și =. Axiomele sunt

| este un număr natural.
Dacă n {\displaystyle n} este un număr natural, atunci n | {\displaystyle n|} $n|$ este un număr natural.
Dacă n | = m | {\displaystyle n|=m|} $n|=m|$ atunci n = m {\displaystyle n=m} $n=m$ .

Se pot defini apoi operațiile de adunare și înmulțire și așa mai departe prin inducție matematică. De exemplu:

m + | = m | {\displaystyle m+|=m|} $m+|=m|$
m + n | = ( m + n ) | {\displaystyle m+n|=(m+n)|} $m+n|=(m+n)|$

Pagini conexe

Dovada matematică
Dovada prin contradicție

Întrebări și răspunsuri

Î: Ce este inducția matematică?

R: Inducția matematică este un mod special de a demonstra un adevăr matematic care poate fi utilizat pentru a demonstra că ceva este adevărat pentru toate numerele naturale sau numerele pozitive începând cu un anumit punct.

Î: Cum se procedează la demonstrarea prin inducție?

R: Demonstrația prin inducție procedează de obicei prin precizarea că demonstrația se va face pe n, arătând că afirmația este adevărată atunci când n este 1, presupunând că afirmația este adevărată pentru orice număr natural n și apoi arătând că este adevărată pentru următorul număr (n+1).

Î: Ce înseamnă să presupui ceva într-o etapă inductivă?

R: A presupune ceva într-o etapă inductivă înseamnă a accepta un lucru ca fiind adevărat fără a furniza dovezi sau dovezi. Aceasta servește ca punct de plecare pentru investigații ulterioare.

Î: Ce fel de numere sunt utilizate în inducția matematică?

R: Inducția matematică utilizează în mod obișnuit numere naturale sau numere pozitive de la un anumit punct încolo.

Î: Cum se demonstrează că ceva este adevărat pentru următorul număr (n+1)?

R: Pentru a demonstra că ceva este adevărat pentru următorul număr (n+1), trebuie mai întâi să demonstrați că este adevărat atunci când n=1 și apoi să utilizați ipoteza din etapa inductivă pentru a demonstra că este adevărat și pentru n+1.